해시 테이블: 키를 값에 매핑할 수 있는 고정된 크기의 자료구조
특징:
- 자료를 쉽고 빠르게 저장할 수 있다.
- key-value pair를 기반으로 자료를 얻을 수 있다.
자바스크립트 객체와 localStorage가 해시 테이블과 같은 방식으로 동작한다.
해시 함수를 통해 특정 키를 인덱스로 변환하여 해시테이블의 키로 사용할 수 있다.
1. 해시 테이블의 주요 함수
put: 자료를 해시테이블에 저장할 때 사용된다. (O(1))
get: 해시테이블로부터 자료를 얻는 데 사용된다. (O(1))
2. 해싱 기법
좋은 해시 함수의 3가지 요구 사항
1. 결정성(detenimistic): 동일한 키는 동일한 해시 값을 생성해야 한다.
2. 효율성(efficiency): 시간 복잡도가 O(1)이어야 한다.
3. 균일한 분배(uniform distribution): 배열 전체를 최대한 활용해야 한다.
1) 소수 해싱
소수를 사용한 해싱 기법이 가장 널리 알려져 있다. 소수와 모듈러 연산(나머지 연산)을 통해 인덱스의 균일한 분배를 보장할 수 있기 때문이다.
그러나 작은 수에 의한 모듈러는 0부터 자기자신 - 1 까지의 범위에서만 키를 가질 수 있기 때문에 키 충돌이 발생할 확률이 높다.
2) 탐사 (probling)
충돌 발생을 피하기 위해 탐사 해싱 기법을 사용한다. 이 기법은 충돌이 발생할 경우, 그 다음으로 사용 가능한 인덱스를 찾아 키로 사용하기 때문에 충돌을 피한다.
1 선형 탐사 (linear probling)
증분 시도(한 번에 한 인덱스 증가)를 통해 다음으로 사용 가능한 인덱스를 찾는다.
이 기법을 사용하면 get(key) 함수를 사용할 때, 원래 해시 결과부터 실제 사용 인덱스까지 테이블을 순회하는 것이 시간 복잡도 상 단점이다.
또한, 군집 (cluster)이 쉽게 발생하여 순회해야 할 자료가 더 많이 생성된다는 것도 주요 단점이다.
2 이차 탐사 (quadratic probling)
완전 제곱을 사용하여 점진적으로 증분 시도를 생성한다. 군집이 쉽게 발생하지 않고 인덱스에 키를 균등하게 분배할 수 있는 점이 장점이다.
3) 재해싱/이중 해싱
해심 함수로부터 나온 결과를 한 번 더 해싱하는 기법이다.
좋은 이중 해시 함수의 3가지 요구 사항
-
달라야 함: 두 번째 해심 함수가 키를 더 잘 분배하기 위해서는 첫 번째 해싱 함수와 달라야 한다.
-
효율적이어야 함: 두 번째 해심 함수의 시간 복잡도가 여전히 O(1)이어야 한다.
-
0이 아니어야 함: 0은 초기 해시 값을 결과로 내기 때문에 두 번째 해싱 함수의 결과가 0이 되어서는 안 된다.
hash2(x) = R - (x % R)
위는 일반적으로 사용하는 이중 해싱 함수이다. x는 첫 번째 해싱의 결과이고, R은 해시 테이블의 크기보다 작다.
i * hash2(x)
i는 반복 시도 횟수로, 해시 충돌이 위 곱셈을 통해 해결된다.
3. 해시 테이블 구현
key-value pair example
7. "hi"
20. "hello"
33. "sunny"
46. "weather"
59. "wow"
72. "forty"
85. "happy"
98. "sad"1) 선형 탐사 사용
function HashTable(size) {
this.size = size;
this.keys = this.initArray(size);
this.values = this.initArray(size);
this.limit = 0;
}
HashTable.prototype.put = function(key, value) {
if (this.limit >= this.size) throw 'The hash table is full';
let hashedIndex = this.hash(key);
// 선형 탐사
while (this.keys[hashedIndex] != null) {
hashedIndex++;
hashedIndex = hashedIndex % this.size;
}
this.keys[hashedIndex] = key;
this.values[hashedIndex] = value;
this.limit++;
}
HashTable.prototype.get = function(key) {
let hashedIndex = this.hash(key);
while (this.keys[hashedIndex] !== key) {
hashedIndex++;
hashedIndex = hashedIndex % this.size;
}
return this.values[hashedIndex];
}
HashTable.prototype.hash = function(key) {
if (!Number.isInteger(key)) throw 'Key must be integer.';
return key % this.size;
}
HashTable.prototype.initArray = function(size) {
const array = [];
for (let i=0; i<size; i++) {
array.push(null);
}
return array;
}
const exampleTable = new HashTable(13);
exampleTable.put(7, "hi")
exampleTable.put(20, "hello")
exampleTable.put(33, "sunny")
exampleTable.put(46, "weather")
exampleTable.put(59, "wow")
exampleTable.put(72, "forty")
exampleTable.put(85, "happy")
exampleTable.put(98, "sad")
console.log(exampleTable)
/****
HashTable {
size: 13,
keys: [
85, 98, null, null,
null, null, null, 7,
20, 33, 46, 59,
72
],
values: [
'happy', 'sad',
null, null,
null, null,
null, 'hi',
'hello', 'sunny',
'weather', 'wow',
'forty'
],
limit: 8,
__proto__: HashTable {
constructor: ƒ HashTable(),
put: ƒ (),
get: ƒ (),
hash: ƒ (),
initArray: ƒ ()
}
}
****/1) 이차 탐사 사용
function HashTable(size) {
this.size = size;
this.keys = this.initArray(size);
this.values = this.initArray(size);
this.limit = 0;
}
HashTable.prototype.put = function(key, value) {
if (this.limit >= this.size) throw 'The hash table is full';
let hashedIndex = this.hash(key);
let squareIndex = 1;
// 이차 탐사
while (this.keys[hashedIndex % this.size] !== null) {
hashedIndex += Math.pow(squareIndex, 2)
squareIndex++;
}
this.keys[hashedIndex % this.size] = key;
this.values[hashedIndex % this.size] = value;
this.limit++;
}
HashTable.prototype.get = function(key) {
let hashedIndex = this.hash(key);
let squareIndex = 1;
while (this.keys[hashedIndex % this.size] !== key) {
hashedIndex += Math.pow(squareIndex, 2)
hashedIndex = hashedIndex % this.size;
squareIndex++;
}
return this.values[hashedIndex % this.size];
}
HashTable.prototype.hash = function(key) {
if (!Number.isInteger(key)) throw 'Key must be integer.';
return key % this.size;
}
HashTable.prototype.initArray = function(size) {
const array = [];
for (let i=0; i<size; i++) {
array.push(null);
}
return array;
}
const exampleTable = new HashTable(13);
exampleTable.put(7, "hi")
exampleTable.put(20, "hello")
exampleTable.put(33, "sunny")
exampleTable.put(46, "weather")
exampleTable.put(59, "wow")
exampleTable.put(72, "forty")
exampleTable.put(85, "happy")
exampleTable.put(98, "sad")
console.log(exampleTable)
/****
HashTable {
size: 13,
keys: [
null, null, null, 85,
72, null, 98, 7,
20, null, 59, 46,
33
],
values: [
null, null,
null, 'happy',
'forty', null,
'sad', 'hi',
'hello', null,
'wow', 'weather',
'sunny'
],
limit: 8,
__proto__: HashTable {
constructor: ƒ HashTable(),
put: ƒ (),
get: ƒ (),
hash: ƒ (),
initArray: ƒ ()
}
}
****/