해시 테이블(Hash Table)

해시 테이블은 한정된 배열 공간에 Key를 index로 반환하여 값들을 넣습니다.
그렇다면 index를 어떻게 구할까요?

키와 값을 받아 키를 해싱(Hashing)하여 나온 index에 값을 저장하는 선형 자료구조입니다.
값을 삽입시 O(1)의 시간 복잡도를 가지고 키를 알고 있다면 제거, 탐색도 O(1)를 가집니다.

해시 함수

해시 함수는 입력받은 값을 특정 범위 내의 숫자로 변경하는 함수입니다.
해시 함수는 정해지지 않고 사용자가 원하는대로 구현 가능합니다.

해시 충돌

만약 해시 함수의 결과값이 동일하게 나와서 겹치게된다면 어떻게 해야할까요?

선형 탐사법 제곱 탐사법 이중 해싱 분리 연결법을 이용합니다.

선형 탐사법

해시 충돌이 발생하면 발생 위치의 옆으로 한 칸을 이동합니다.
이는 충돌이 발생하지 않을때까지 계속 진행되므로 최악의 경우 O(n)의 시간복잡도를 갖습니다.
또다른 문제로는 특정 영역에 데이터가 몰릴 수 있습니다.

제곱 탐사법

해시 충돌이 발생하면 발생 위치에서 충돌이 발생한 횟수의 제곱만큼 옆으로 이동합니다.
이는 선형 탐사법의 특정 영역에 데이터가 몰리는 것을 방지할 수 있습니다.

이중 해싱

해시 충돌이 발생하면 또다른 해시 함수를 사용합니다.

분리 연결법

버킷(Bucket)의 값을 연결 리스트로 사용하여 해시 충돌이 발생하면 리스트에 값을 추가합니다.
선형 탐사법 제곱 탐사법 이중 해싱과는 다르게 해시 충돌시 다른 index로 이동하지 않습니다.

해시 테이블의 쇼소를 연결리스트로 만들어 충돌이 발생한 버킷에 그대로 요소를 추가하는 방법이지만,
최악의 경우 하나의 버킷이 무한대로 늘어날 수 있습니다.

JavaScript 구현

Array

간단히 구현할 수 있지만 올바른 사용법은 아닙니다.

const table = [];
table["key1"] = 100;
table["key2"] = "hello";
console.log(table["key1"]); // 100

table["key1"] = 204;
console.log(table["key1"]); // 204
delete table["key1"];
console.log(table["key1"]); // undefined

Object

간단히 구현 가능하고 정석적인 사용법입니다.

const table = {};
table["key1"] = 100;
table["key2"] = "hello";
console.log(table["key1"]); // 100

table["key1"] = 204;
console.log(table["key1"]); // 204
delete table["key1"];
console.log(table["key1"]); // undefined

Map

set과 get 메소드를 이용하여 쉽게 값을 추가하거나 탐색할 수 있습니다.
객체의 경우 들어오는 값이 정수가 아닌경우 문자열로 바꾸기 때문에 다양한 타입을 사용할 수 없지만 Map은 key값으로 배열이나 객체타입도 사용가능하다는 장점이 있습니다.

const table = new Map();
table.set("key1", 100);
table.set("key2", "hello");
console.log(table["key1"]); // undefined
console.log(table.get("key1")); // 100

const object = { a: 1 };
table.set(object, "A1"); // 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()); // { 100, 'hello' }
table.clear();
console.log(table.values()); // {  }

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
table.add("key3");
console.log(table.size); // 2
table.clear();
console.log(table.size); // 0