해시 테이블이란? (Hash Table)
키와 값으로 구성된 자료구조이다. 해시 테이블은 인덱스가 해싱 함수에 의해 계산되는 배열과 유사하다. 이때 인덱스는 메모리에서 유일한 공간을 식별하기 위한 것이다.
해시 테이블에는 put()과 get()이라는 두 가지 함수가 있다.
put : 자료를 해시 테이블에 저장한다
get : 해시 테이블로부터 자료를 얻는 데 사용한다.
그리고 해시 테이블에서 가장 중요한 것은 해시 함수인데 해시 함수가 무엇인지 알아보자.
해시 함수(Hash Function)
해시 함수는 특정 키를 자료를 저장하는 배열의 인덱스로 변환한다.
좋은 해시 함수의 세 가지 특징은 다음과 같다.
- 결정성 : 동일한 키는 동일한 해시 값을 생성해야 한다.
- 효율성 : 시간 복잡도가 O(1)이어야 한다.
- 균일한 분배 : 배열 전체를 최대한 활용해야 한다.
[key: 18, value:'eighteen']과 [key: 7, value: 'seven']인 키-값 쌍이 있다. 모듈러 숫자가 11일 때 연산은 다음과 같다
18 mod 11 = 7
7 mod 11 = 7
이므로 테이블에 저장할 때 충돌이 일어난다. 이를 해결할 수 있는 방법으로는 탐사가 있다.
탐사(Probling)
충돌을 방지하기 위해 배열에서 다음으로 사용 가능한 인덱스를 찾아서 사용하는 것이 탐사이다.
선형 탐사는 증분 시도를 통해 다음으로 사용 가능한 인덱스를 찾아서 충돌을 해결한다.
이차 탐사는 점진적으로 증분 시도를 생셩하기 위해 이차 함수를 사용한다.
선형탐사
선형탐사는 한 번에 한 인덱스를 증가시킴으로써 사용 가능한 인덱스를 찾는다.
방금과 같이 18과 7은 7이라는 인덱스를 공유하고 있지만, 18을 빈 해시인 8이라는 인덱스에 해싱할 수 있다. 하지만 get(key)를 통해 원래 해시 결과인 7부터 시작해서 18을 찾을 때 까지 테이블을 순회한다. 그리고 선형 탐사는 데이터가 몰리게 되는 군집이 쉽게 발생한다. 군집은 순회해야 할 자료를 더 많이 생성하기 때문에 좋지 않다.
이차 탐사
이차 탐사는 군집 문제를 해결하는 데 좋은 기법이다. 선형탐사가 인덱스를 1씩 증가시키는 반면에 이차 탐사는 완전 제곱을 통해 인덱스에 키를 균등하게 분배한다.
이중해싱(Dobule Hashing)
키를 균등하게 분배하는 방법으로 이차 해싱 함수를 사용해 원래 해싱 함수로부터 나온 결과를 한 번 더 해싱하는 것이 있다.
- 달라야 함 : 두 번째 해싱 함수가 키를 더 잘 분배하기 위해서는 첫 번째 해싱 함수와 달라야 한다.
- 효율적이어야 함 : 두 번째 해싱 함수의 시간 복잡도가 여전히 O(1)이어야 한다.
- 0이 아니어야 함 : 두 번째 해싱 함수의 결과가 0이 돼서는 안된다. 0은 초기 해시 값을 결과로 내기 때문이다.
Hash2(x) = R - (x % R) ..x는 첫 번째 해싱의 결과이고 R은 해시 테이블의 크기보다 작다. 각 해시 충돌은 i * hash2(x)로 해결된다 i는 반복 시도 횟수
구현해보기
선형탐사
function HashTable(size){
this.size = size;
this.keys = this.initArray(size);
this.values = this.initArray(size);
this.limit = 0;
}
//put을 구현한다. 자료를 해시테이블에 저장하는 함수.
HashTable.prototype.put = function(key, value){
if(this.limit >= this.size) throw 'hash table is full';
var hashedIndex = this.hash(key);
//선형탐사 빈 공간이 아닌 곳을 찾는다.
while(this.keys[hashedIndex != null]){
hashedIndex++;
hashedIndex= hashedIndex % this.size; //size로 모듈러 연산을 한다.
}
this.keys[hashedIndex] = key;
this.values[hashedIndex] = value;
this.limit++;
}
//get을 구현한다. 선형탐사로 해시 테이블에 저장된 key의 value를 찾는다.
HashTable.prototype.get = function(key){
var 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 'must be int';
return key % this.size;
}
//배열을 초기화 한다.
HashTable.prototype.initArray = function(size){
var array = [];
for(var i = 0; i < size; i++){
array.push(null);
}
return array;
}
var exampleTable = new HashTable(13);
exampleTable.put(7, 'hi'); // index 7
exampleTable.put(20, 'greet'); // index 7+1
exampleTable.put(33, 'wow'); // index 7+1+1이차탐사 구현하기
get과 put을 수정하면 된다.
//put을 구현한다. 자료를 해시테이블에 저장하는 함수.
HashTable.prototype.put = function(key, value){
if(this.limit >= this.size) throw 'hash table is full';
var hashedIndex = this.hash(key);
var squareIndex = 1;
//저장공간이 null이 아니라면 제곱한다.
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++;
}
//get을 구현한다. 선형탐사로 해시 테이블에 저장된 key의 value를 찾는다.
HashTable.prototype.get = function(key){
var hashedIndex = this.hash(key);
var squareIndex = 1;
//키의 값이 value가 아닐 경우 제곱을 하면서 찾아간다.
while(this.keys[hashedIndex % this.size] != key){
hashedIndex += Math.pow(squareIndex, 2);
hashedIndex = hashedIndex % this.size;
squareIndex++;
}
return this.values[hashedIndex % this.size];
}이제 선형 탐사와 이차 탐사에 대하여 알게 되었다.
선형 탐사를 활용해 이중 해싱을 하려면 어떻게 해야 할까?
이중 해싱은 hash2(x) = R - (x%R)이라는 내용을 기억한다면 구현할 수 있을 것이다.
HashTable.prototype.secondHash = function(hashedKey){
var R = this.size - 2; //R은 size보다 작다는 것을 기억하자.
return R - (hashedkey % R);
}이상으로 해시테이블에 대하여 알아보았다.
결론: 해시함수를 통해 균등하게 인덱스를 나눠 충돌을 최대한 피하며(선형 탐색과 이차 탐색) 데이터를 저장할 수 있다는 것을 이용하면 O(1)이라는 속도로 데이터를 찾을 수 있다!
