해시 테이블(Hash Table)

: 키와 값을 받아서, 키를 해싱(Hashing)하여 나온 index에 값을 저장하는 선형 자료구조

• 해시 함수(Hash Function) : 입력받은 값을 특정 범위 내 숫자로 변경하는 함수

해시 테이블의 연산

Insert, Search, Delete O(1)

• 키를 알고 있다면 삭제, 탐색 모두 상수 시간(O(1))이 소요된다.
  따라서 빠르게 값을 찾아야하는 경우, 해시 테이블을 사용하는 것이 좋다.
• 최악의 경우 탐색에 선형시간(O(N))이 소요될 수 있지만, 연결리스트나 배열보다는 안정적이다.

---

배열로 해시 테이블 구현하기

배열은 실제로는 객체 타입이기 때문에 해시 테이블처럼 사용할 수 있다.
하지만, 배열의 올바른 사용법이 아니므로 사용하지 않는 것이 좋다.

const table = [];
table["key1"] = 100;
table["key2"] = "abc";

console.log(table["key1"]); // 100

delete table["key2"];       // true
console.log(table["key2"]); // undefined

---

객체로 해시 테이블 구현하기

const table = {};
table["key1"] = 100;
table["key2"] = "abc";

console.log(table["key1"]); // 100

delete table["key2"];       // true
console.log(table["key2"]); // undefined

---

Map 객체로 해시 테이블 구현하기

• Map은 set() 메소드로 값을 추가할 수 있다.

const table = new Map(); // Map(0) {size: 0}
table.set("key1", 100);
table.set("key2", "abc");

console.log(table);      // {'key1' => 100, 'key2' => 'abc'}
console.log(table.size); // 2

• get() 메소드로 값을 찾을 수 있다.

console.log(table["key1"]);     // undefined
console.log(table.get("key1")); // 100

• 기존 객체와 다르게, Map은 객체, 배열, 함수도 key로 사용할 수 있다.

const obj = {name: 'jieun'};
table.set(obj, 26);
console.log(table.get(obj)); // 26

• delete() 메소드로 값을 삭제할 수 있다.

console.log(table.delete(obj)); // true
console.log(table.get(obj));    // undefined

• keys(), values() 메소드는 키, 값으로 이루어진 Map Iterator를 반환하며, 이는 for...of문으로 순회할 수 있다.

console.log(table.keys());   // MapIterator {'key1', 'key2'}
console.log(table.values()); // MapIterator {100, 'abc'}

• clear() 메소드로 Map의 모든 요소를 삭제할 수 있다.

table.clear();
console.log(table.values()); // { }

---

Set으로 해시 테이블 구현하기

Set은 키와 값이 동일하게 들어간다.

• Set은 add() 메소드로 값을 추가할 수 있다.

const table = new Set(); // Set(0) {size: 0}
table.add("key1"); 
table.add("key2");

console.log(table);      // Set(2) {'key1', 'key2'}
console.log(table.size); // 2

• has() 메소드로 특정 값이 들어있는지 확인할 수 있다.

console.log(table.has("key1")); // true
console.log(table.has("key3")); // false

• delete() 메소드로 값을 삭제할 수 있다.

table.delete("key2");           // true
console.log(table.has("key2")); // false 

• clear() 메소드로 Set의 모든 요소를 삭제할 수 있다.

table.clear();
console.log(table.size); // 0

---

해시 충돌(Hash Collision)

해시 함수의 결과가 동일할 경우 해시 충돌(Hash Collision)이 발생한다.

1. 선형 탐사법

충돌이 발생하면 옆으로 한 칸 이동한다.
충돌이 또 발생하면, 충돌이 발생하지 않을 때까지 이동한다.

---

2. 제곱 탐사법

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

---

3. 이중 해싱

충돌이 발생하면 기존 해시 함수가 아닌 두 번째 해시 함수를 이용해 다시 해싱한다.

---

4. 분리 연결법

버킷의 값을 연결리스트로 사용하여, 충돌이 발생하면 리스트에 값을 추가한다.
최악의 경우, 하나의 버킷이 무한정 늘어날 수도 있다.