해시 테이블

해시 테이블의 'hash'는 잘게 자른다는 뜻으로, 해시 테이블은 입력받은 key를 잘게 잘라 숫자로 만든다.
즉, key와 값을 받아 key를 해싱하여 나온 index에 값을 저장하는 선형 자료구조가 해시 테이블이다.

삽입은 O(1), 키를 알고있다면 탐색, 삭제도 O(1)로 수행한다.
연결리스트, 배열의 인덱스를 모르는 경우 탐색에 선형시간 O(n)이 걸린다. 따라서 빠르게 값을 찾아야 하는 경우 해시 테이블을 사용하는 것이 좋다.

입력받은 key를 특정 범위 내 숫자로 변경하는 함수를 해시 함수라고 한다. 해시 함수의 결과가 동일하여 겹치는 현상을
hash collision (해시 충돌)이라 한다.

---

해시 충돌 처리 방법

1. 선형 탐사법
   충돌이 발생하면 인덱스를 한 칸 이동한다. 단순하지만 특정 영역에 데이터가 몰릴 수 있으며, 최악의 경우 탐색에 선형시간이 걸린다.

2. 제곱 탐사법
   충돌이 발생하면 충돌이 발생한 횟수의 제곱만큼 옆으로 이동한다.
   

3. 이중 해싱
   충돌이 발생하면 다른 해시 함수를 사용한다.

4. 분리 연결법 (Chaining)
   버킷의 값을 연결 리스트로 연결하여 충돌이 발생하면 리스트에 값을 추가한다. 위 3가지 방법과 다르게 충돌이 발생한 경우 다른 index로 이동하지 않는다. 대신 해시 테이블의 요소를 연결 리스트로 만들어 충돌이 발생한 버킷에 그대로 요소를 추가한다. 최악의 경우 하나의 버킷이 무한정 늘어날 수 있다.
   
   체이닝으로 구현한 해시 테이블에서 시간복잡도는 다음과 같다.
   - 삽입 : 연결리스트에 추가하기 때문에 O(1)
   - 탐색 or 삭제 : 최악의 경우 key의 개수 K에 대해 O(K)
   
   

---

자바스크립트에서 사용법

1. 배열, 객체

자바스크립트의 배열은 실제로는 객체 타입이라 해시 테이블처럼 사용이 가능하다. (올바른 사용법은 아니다.)

자바스크립트의 배열은 해시태이블로 구현된 객체이다. 따라서 index로 숫자 대신 문자열로 된 key를 사용할 수 있는데 이러한 배열을 연관배열이라고 한다. 하지만 이렇게 생성된 배열은 자바스크립트 내부적으로 Array 객체에서 기본 객체로 재선언된다. 따라서 기존 Array 객체에서 사용할 수 있는 메소드와 속성이 정확하지 않은 결과값을 반환하게 된다.

const table = []
table["name"] = "nhs"
table["age"] = 25
console.log(table) // [name: 'nhs', age: 25], [[Prototype]] : Array(0)
console.log(table.length) // 0  

const table = {}
table["name"] = "nhs"
table["age"] = 25
console.log(table) // [[Prototype]] : Object

2. Map

1. map은 set을 이용해 값을 넣고, get을 이용해 값을 찾을 수 있다.
   객체처럼 . or []로 접근할 필요 없이, 메소드만으로 맵 객체 안에 들어있는 프로퍼티들을 수정하거나 조회할 수 있다.
   메소드의 이름(set, get, delete, clear)이 맵 객체를 어떻게 할지 잘 나타내어 명시적이다.

const table = new Map()
table.set("name","혜수")
table.set("age",25)

console.log(table["name"])     // undefined 
console.log(table.get("name")) // 혜수

table.delete("name") // true : true indicates successful removal
console.log(table["name"]) // undefined

table.clear() 
console.log(table) // Map(0) {size: 0}

2. 객체에서는 String or Symbol 만 키로 사용할 수 있다. (정수가 아니면 전부 문자열로 바꾸)
   반면 맵 객체에서는 함수나 객체를 포함한 모든 자료형이 프로퍼티의 키로 쓰일 수 있다.
   
   ex) 종종 키가 문자열이 아니라 숫자(Number)일 때 보기 더 편한 경우가 있다.
   객체의 경우는 문자열을 통해서만 조회가 가능하고, . 뒤에 숫자를 입력하면 에러가 난다.
   하지만 맵 객체에서는 get 메소드의 인자로 숫자를 넘겨줘도 제대로 값을 가져온다.

const errorMessage_Obj = {
  404 : "페이지가 없습니다",
  500 : "서버 오류입니다",
  401 : "권한이 없습니다"
}
​
const errorMessage_Map = new Map([
  [404, "페이지가 없습니다"],
  [500, "서버 오류입니다"],
  [401, "권한이 없습니다"],
])

errorMessage_Obj.404 // unexpected number 에러
errorMessage_Obj["404"] // '페이지가 없습니다'
errorMessage_Map.get(404) // '페이지가 없습니다'

Symbol
ECMAScript로 표준화된 이후로 자바스크립트에는 string, number, boolean, null, undefined, object 6개의 데이터 타입이 있었다. 그리고 es6에서 새로운 데이터 타입 Symbol이 추가 되었다.

심볼은 변경 불가능한 원시 타입의 값이며, 다른 값과 중복되지 않는 고유한 값이다. 심볼 값은 충돌 위험이 없는 객체의 유일한 프로퍼티 키를 만들기 위해서 사용할 수 있다.

const symbolA = Symbol('symbol') 
const symbolB = Symbol('symbol')
console.log(symbolA === symbolB) // false

Symbol 값은 Symbol 함수를 호출하여 생성한다. Symbol 함수에 들어가는 문자열 인자는 심볼 값에 대한 description으로서 선택적으로 넣을 수 있다. 이 문자열은 디버깅 용도로만 사용되며 심볼 값 생성에 영향을 주지는 않는다.
Symbol은 내장 객체와 비슷하지만 생성자가 없으므로 new 연산자를 사용하여 Symbol을 생성할 수 없다.

3. 깔끔한 순회
   맵 객체는 그 자체로 for..of 문을 통해 순회가 가능하다. 이때 순회는 맵 이터레이터의 형태로 이루어진다. 맵 이터레이터는 키-값을 쌍으로 묶은 배열이다. entries 메소드로 맵 이터레이터를 확인할 수 있다.
   
   객체는 for..in 문이나 Object.keys를 사용하여 순회한다. 이 방법들은 기본적으로 객체의 키 만을 순회하기 때문에, 그 키를 이용해서 객체의 값을 다시 얻어내야 한다.
   (이런 불편함 때문에 ES2017에 Object.entries 가 등장했다. 이 메소드는 맵 객체처럼 키-값을 쌍으로 묶은 이터레이터를 반환한다.)

const Info = new Map([
  ['name', '혜수'],
  ['age', 25],
  ['major', '동물'],
]);

Info.entries();
// MapIterator { ["name", "혜수"],["age", 25],["major", "동물"]}

for (const [key, value] of Info) {
  console.log(key, value);
}

// "name" "혜수"
// "age" 25
// "major" "동물"

❗맵 객체는 객체의 프로퍼티를 자주 변경해야할 때 빛을 발한다. 메소드 이름들이 예측 가능하여 동작이 명확하고, 기존 객체와 달리 순회도 쉽게 이루어져 데이터를 조작하기 적합하다.

3. Set

set 객체는 중복되지 않는 유일한 값들의 집합이다.

1. 동일한 값을 중복하여 포함할수 없다.
2. 요소 순서에 의미가 없다.
3. 인덱스로 요소에 접근할 수 없다.

이러한 set 객체는 수학적 집합을 구현하기 위한 자료 구조이다. 그래서 set을 통해 교집합, 합집합, 차집합, 여집합 등을 구현할 수 있다.

const table = new Set()
table.add("key")
table.add("key2")
conole.log(table.has("key")) // true

table.delete("key2") 
conole.log(table.size) // 1
table.clear()
conole.log(table.size) // 0

Set을 사용하면 key값과 동일한 value를 테이블에 저장한다.
즉, Map과 가장 큰 차이점으로 Key-Value가 동일한 값으로 저장된다.

add 메소드를 사용해서 추가하고 delete를 사용해서 삭제할 수 있다. 테이블에 요소가 존재하는지 확인하기 위해서는 has 메소드를 사용하면 된다. has는 true or false를 리턴한다.