Hashtable 정리

 

Hashtable이란?

key와 value를 받아 hashing하여 나온 index에 값을 저장하는 선형자료구조,

삽입시 시간복잡도는 O(1), key를 알고 있다면 탐색과 삭제도 O(1)로 빠른속도로 수행가능.

 

 

해쉬충돌이란?

서로 다른 input Data 가 같은 hash 함수를 통해 hashing후 결과값이 같을때

해쉬충돌이 일어날 경우, 같은 버킷에 저장되게 되므로 원하지 않는 결과를 불러올 수 있다.

 

 

 

해쉬충돌을 해결하는 4가지 방법

 

1.선형탐사법

충돌이 발생하면 기존 버킷에서 옆으로 한칸 이동하여 Data를 저장한다. 단순하지만 충돌이 여러번 일어날 결우 특정영역에 데이터가 모일 수 있는 단점이 있다. 또한 충돌이 발생하지 않을 때까지 이동해야 하므로 최악의 경우에는 탐색에 선형시간 O(n)이 소요된다.

 

2. 제곱탐사법

충돌이 발생하면 충돌이 발생한 횟수의 제곱만큼을 이동한다. 충돌이 발생할 수록 범위가 커지기 때문에 데이터가 특정영역에 몰리는 것을 방지할 수 있다.

 

3. 이중해싱

충돌이 발생하면 다른 해쉬함수를 사용한다. 만약 이중해쉬를 했는데도 충돌이 발생하면 한번 더 hashing하여 index를 계속 만들어낸다.

 

4. 분리연결법

버킷의 값을 연결리스트 또는 배열로 하고, 충돌이 발생하면 하나의 버킷에서 연결리스트 또는 배열에 값을 추가한다. 

최악의 경우 하나의 버킷이 무한정으로 늘어날 수 있다.

 

 

자바스크립트에서 Hashtable의 구현

자바스크립트는 객체를 사용하여 Hashtable을 간단히 구현 할 수 있다.

 

//1. Map()을 사용한 hashtable구현

const table = new Map();

table.set("key", 100);
table.set("key3", 100);
table.set("key2", 100);
    
const obj = { a: 1 };
table.set(obj, obj); //map은 Object도 key로 쓸 수 있다.

console.log(table); //Map(4) {'key' => 100, 'key3' => 100, 'key2' => 100, { a: 1 } => { a: 1 }}
console.log(table.get("key")); //100
console.log(table.has("key")); //true
console.log(table.has("key999")); //false

console.log(table.keys()); //MapIterator {'key', 'key3', 'key2', { a: 1 }} key만 가져오기
console.log(table.values()); //MapIterator {100, 100, 100, 100, { a: 1 }} value만 가져오기
console.log(table.size); //4
    
console.log(table.delete("key")); //true
console.log(table); //Map(3) {'key3' => 100, 'key2' => 100, { a: 1 } => { a: 1 }}
console.log(table.size); //3
    
table.clear();
console.log(table.size); //0
console.log(table); //Map(0) {size: 0}

//2. Set()을 사용한 hashtable구현

const table2 = new Set();

table2.add("key"); //key와 value가 동일하게 들어간다. Map()과의 차이점!!
console.log(table2.has("key")); //true
console.log(table2.has("key2")); //false

console.log(table2.size); //1
console.log(table2); //Set(1) {'key'}

table2.add("key2");
console.log(table2); //Set(2) {'key', 'key2'}
console.log(table2.size); //2

console.log(table2.delete("key2")); //true
console.log(table2.size); //1


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