해쉬 테이블

해쉬테이블은 자바스크립트의 객체, 브라우저 기본객체인 로컬스토리지 등에 사용된 자료구조라 잘 알아야 한다.

해쉬테이블은 key를 해싱(hashing)하여 해쉬 코드로 변환 후 해당 코드의 위치에 값을 저장하는 테이블로,

key를 알면 해싱함수를 통해 삽입, 삭제, 검색을 바로 수행할 수 있어 O(1)의 시간복잡도를 가진다.

해쉬테이블에서 중요한 건 해싱 함수인데 해싱 함수는 다음 세가지 성질을 지녀야 한다.

1. 같은 입력값에 대해 항상 같은 출력값을 계산
2. 시간 복잡도는 O(1)이어야 함
3. 배열 내 인덱스를 고르게 분포할 수 있게끔 계산

 

다른 key라도 해싱함수에 따라 같은 해쉬 코드로 변환될 수 있는데 이를 충돌이라고 한다.

 

충돌을 해결하는 방법으로는 크게 개방 주소법(Open Addressing)과 분리 연결법(Seperate Chaining)이 있다.

 

개방 주소법은 해당 위치에 이미 값이 있으면 비어있는 다른 위치에 값을 저장하는 방식이다.

 

비어있는 위치를 탐사하는 방식에 따라 선형 탐사, 제곱 탐사, 이중 해싱으로 나뉜다.

 

분리 연결법은 해당 위치에 연결 리스트 형태로 값을 저장하는데 연결 리스트의 HEAD에 충돌값을 연결하는 게 삽입 내 시간 복잡도에 좋다.

 

다음은 이중 해싱으로 충돌을 회피한 해쉬 테이블 코드다.

 

이중 해싱 사용시, 저장소의 공간은 소수가 권장되고, 이중 해싱 함수에서 사용하는 숫자또한 공간 크기와 인접한 소수가 좋다.

 

function HashTable (lim) {
  this._limit=lim;
  this._storage = [];
  this._count = 0;
}
 
HashTable.prototype.hashing = function (key) {
  return key % this._limit;
}
 
HashTable.prototype.stepHashing = function (key) {
  return 17 - (key % 17);
}
 
HashTable.prototype.insert = function (key, value) {
  let idx = this.hashing(key);
  let isExist = this._storage[idx];
 
  while(1) {
    if (this._count === this._limit) {
      console.log("full!!")
      return;
    }
    else if (!isExist) {
      this._storage[idx] = {
        key: key,
        value: value
      };
      this._count++;
      return;
    } else {
      idx += this.stepHashing(key);
      idx = idx >= this._limit ? idx - this._limit : idx;
      isExist = this._storage[idx];
    }
  }
}
 
HashTable.prototype.retrieve = function (key) {
  let idx = this.hashing(key);
  let result = this._storage[idx];
 
  let keys = this._storage.map(elem => elem.key);
 
  if (!keys.some(k => k === key)) return;
 
  while (1) {
    if (!result) {
      return;
    }
    else if (result.key === key) {
      return result.value;
    } else {
      idx += this.stepHashing(key);
      idx = idx >= this._limit ? idx - this._limit : idx;
      result = this._storage[idx];
    }
  }
}
 
HashTable.prototype.delete = function (key) {
  let idx = this.hashing(key);
  let result = this._storage[idx];
 
  while (1) {
    if (!result) {
      return;
    } else if (result.key === key) {
      delete this._storage[idx];
      this._count--;
      return;
    } else {
      idx += this.stepHashing(key);
      idx = idx >= this._limit ? idx - this._limit : idx;
      result = this._storage[idx];
    }
  }
}
 
let hashtable = new HashTable(23);
 
// Collision
// hashtable.insert(1, 1);
// hashtable.insert(24, 2);
// hashtable.insert(13, 3);
// hashtable.insert(47, 4);
 
// Full
for (let i=0;i<23;i++) {
  hashtable.insert(i, i+1)
}
 
hashtable.insert(1, 111);

(해쉬 테이블의 공간의 80% 이상이 차면 저장소를 늘려줘야 하는데 아직 늘려주는 방법을 고안하지 못함)