해시 테이블

해시 테이블

키와 값을 받아 키를 해싱하여 나온 index에 값을 저장하는 선형 자료구조
키를 알고 있다면 삽입시 시간 복잡도는 $O(1)$이 걸리며 삭제, 탐색도 $O(1)$이 걸린다.

해시 함수

입력받은 값을 특정 범위 내 숫자로 변경하는 함수

해시 테이블의 문제점

해시 함수를 통해 동일한 값이 생길 수 있다. (해시 충돌)

해시 충돌 해결

1. 선형 탐사법

해시 충돌이 발생시 해당 값을 옆으로 한 칸 이동

2. 제곱 탐사법

충돌 발생시 발생한 횟수의 제곱만큼 옆으로 이동

3. 이중 해싱

충돌이 발생하면 다른 해시 함수를 이용

4. 분리 연결법

버켓의 값을 연결 리스트로 사용하여 충돌 발생시 리스트에 값을 추가한다.

실습

1. Array (비추천)

const table = [];
table["key1"] = 10;
table["key2"] = "good"
console.log(table["key1"]); // 10
table["key1"] = 25;
console.log(table["key1"]); // 25
delete table["key1"]
console.log(table["key1"]); // undefined

2. Object

const table = {};
table["key1"] = 10;
table["key2"] = "good"
console.log(table["key1"]); // 10
table["key1"] = 25;
console.log(table["key1"]); // 25
delete table["key1"]
console.log(table["key1"]); // undefined

3. Map

const table = new Map();
table.set("key1", 10);
table.set("key2", "good");
console.log(table["key1"]); // undefined
console.log(table.get("key1")); // 10
const object = {a: 1};
table.set(object, "A1"); // Map은 Object도 Key로 쓸 수 있다.
console.log(table.get(object)); // A1
table.delete(object);
console.log(table.get(object)); // undefined
console.log(table.keys()); // {'key1', 'key2'}
console.log(table.values()); // {10, 'good'}
table.clear();
console.log(table.values()); // {}

4. Set

const table = new Set();
table.add("key1");
table.add("key2");
console.log(table.has("key1")); // true
console.log(table.has("key3")); // false
table.delete("key2");
console.log(table.has("key2")); // false
console.log(table.size); // 1
table.clear();