Hash table이란?
key-value 쌍으로 데이터를 저장하는 자료구조입니다.
key 자체를 특정 index로 저장하기 때문에 데이터 삽입, 삭제, 조회를 빠르게 수행할 수 있습니다.
이때 저장할 위치인 index는 Hash function을 통해 생성하게 됩니다.
Hash function(해시 함수)
해시 함수는 key를 특정한 index로 매핑하며 해당 index는 메모리의 저장 위치가 됩니다.
index를 통해 데이터에 접근하기 때문에 Array loop를 돌며 조회하는 것보다 더 빠르게 데이터 처리가 가능합니다.
해시 함수가 얼마나 key를 균일하게 분산시키느냐에 따라 해시 테이블의 성능이 크게 좌우됩니다.
아래는 hash function의 간단한 pseudocode입니다. 소수를 사용해서 충돌 가능성을 낮추고, 문자열의 길이를 100으로 제한하여 길이에 비례하여 커지는 loop를 제한하였습니다.
function hash(key, arrayLen){
let total = 0;
let WEIRD_PRIME = 31;
for(let i=0; i<Math.min(key.length, 100); i++){
let char = key[i];
let value = char.charCodeAt(0) - 96;
total = (total * WEIRD_PRIME + value) % arrayLen;
}
return total
}
hash function을 최적화한다고 해도 index의 충돌을 완전히 막을수는 없습니다. 그래서 충돌을 해결하는 다양한 방법이 존재합니다.
충돌을 해결하는 방법
1. Separate Chaining
해시 함수로 생성된 동일한 index에 여러 개의 값을 저장해야 하는 경우, 해당 index에 연결 리스트(또는 다른 자료구조)를 만들어 데이터를 체인처럼 연결하는 방법입니다. 이를 통해 동일한 index에 여러 개의 key-value 쌍을 저장할 수 있습니다.
2. Linear Probing
충돌이 발생하면 바로 다음 빈 index에 데이터를 저장하는 방법입니다. 그러나 이 방법은 연속된 index가 채워지는 문제(클러스터링)가 발생할 수 있어 성능 저하를 유발할 수 있습니다. 이를 해결하기 위한 방법으로 Quadratic Probing이나 Double Hashing이 있습니다.
해시 테이블 슈도 코드
class HashTable {
constructor(size=53){
this.keyMap = new Array(size);
}
_hash(key){
let total=0;
let WEIRD_PRIME = 31;
for(let i=0; i<Math.min(key.length, 100); i++){
let char = key[i];
let value = char.charCodeAt(0) - 96;
total = (total * WEIRD_PRIME + value) % this.keyMap.length;
}
return total;
}
set(key, value){
let index = this._hash(key);
if(!this.keyMap[index]){
this.keyMap[index] = []
}
this.keyMap[index].push([key, value])
}
get(key){
const index = this._hash(key);
if(this.keyMap[index]) {
for (let map of this.keyMap[index]) {
if (map[0] === key) return map[1];
}
}
return undefined;
}
}
시간 복잡도
Insert, deletion, access는 평균적으로 O(1)의 시간복잡도를 가집니다. 그러나 최악의 경우 충돌이 많이 발생하면 O(n)까지 될수도 있습니다.
javascript로 Hash table 구현 방법
1. Object
- string, symbol 타입만 키로 사용할 수 있다.
- 간단한 key, value 저장에 유용
- 삽입 순서를 보장하지 않는다.
- Object 프로토타입 체인에서 상속된 속성(toString, hasOwnProperty)들을 포함하기 때문에 해시 테이블로 사용시 예상치 못한 충돌이 발생할 수 있다.
2. Map
- 다양한 타입을 키로 사용할 수 있다.
- 더 최적화된 해시로직과 충돌 알고리즘을 사용하여 데이터를 조회하고, 삽입할 때 속도가 더 빠르다.
- 삽입 순서를 보장
- 프로토타입 체인의 영향을 받지 않기 때문에 해시 테이블 용도로 더 적합
참고
https://www.udemy.com/course/best-javascript-data-structures/?couponCode=KEEPLEARNING