[Data Structure] Hash Table

해시 테이블(혹은 해시 맵)은 키(Key), 값(Value) 쌍을 저장하고 있는 자료 구조이다. 해시 테이블은 키를 저장할 때에 메모리 공간을 덜 사용할 수 있도록, 키를 "해시 함수"(Hash function)라는 함수를 통해 특정 숫자값의 인덱스로 변환한다. 해시 테이블은 필요할 때에만 메모리 크기를 늘리고, 가능한 작은 크기를 유지한다.

이미지 출처: codestates urclass

해시 테이블이 가장 효율적으로 실행될 때는 값이 저장되는 'tuple'과 일정한 사이즈를 받아 운용되는 'storage'의 비율이 25~75% 사이일 때이다. 가장 효율적인 형태의 해시 테이블 운영을 위해 비율이 75% 이상이 되는 경우에는 storage의 사이즈를 2배로 증가시키고, 25% 이하인 경우에는 storage를 절반으로 줄이는 작업을 진행해야 하는데 이를 Table Resizing이라고 한다.

용어 정리

• storage: 해시 테이블의 테이블. 데이터를 저장하는 공간(배열)
• bucket: 데이터가 들어갈 공간. 데이터 하나당 버킷 하나가 들어감.
• tuple: 데이터들을 담고 있는 곳.

해싱(Hashing)이란?

해싱(Hashing)이란 많은 양의 데이터를 그보다 작은 테이블로 매핑(mapping)시켜 저장할 수 있도록 하는 데이터 관리 기법이다. 해싱은 해쉬 함수를 사용하여 일정한 시간 내에 데이터를 효과적으로 찾을 수 있도록 한다.

해시 함수의 특징

1. 가지고 있는 배열(array)의 크기 안에서 값이 나옴(0 ~ length-1)
2. 항상 일정한 값이 나옴
3. 메모리를 저장할 수 없음(input이 주어질 때마다 값이 나옴)

해시 충돌(Hash Collision)

이미지 출처: https://www.cs.cmu.edu/~rdriley/121/notes/hashtables.html

해시 충돌(Hash Collison)은 하나의 키(Key)에 다른 값(Value)을 가진 데이터가 여러개 존재하는 상황을 의미한다. 이는 특정 키의 버켓에 데이터가 집중되는 것이기 때문에 해시 충돌이 많을 경우 해시 테이블의 성능이 떨어질 수 있다.

해시 충돌을 해결하는 방법으로는 1)Linked List를 사용하여 값을 추가하는 분리 연결법(Separate Chaining)과 2)해시 테이블 Array의 빈 공간을 사용하는 개방 주소법(Open Addressing)이 있다.

JS 코드 구현

class HashTable {
  constructor() {
    this._size = 0;
    this._limit = 8;
    this._storage = LimitedArray(this._limit);
  }

  insert(key, value) {
    const index = hashFunction(key, this._limit);
    let bucket = {};
    if(this._storage.get(index) === undefined){
      bucket[key] = value;
      this._storage.set(index, bucket);
    }else{
      bucket = this._storage.get(index);
      bucket[key] = value;
      this._storage.set(index, bucket);
    }
    this._size++;

    if((this._size / this._limit) * 100 > 75){
      this._resize(this._limit * 2);
    }
    return this._storage;
  }

  retrieve(key) {
    const index = hashFunction(key, this._limit);
    if(this._storage.get(index) === undefined){
      return undefined;
    }
    return this._storage.get(index)[key];
  }

  remove(key) {
    const index = hashFunction(key, this._limit);
    delete this._storage.get(index)[key];
    
    if((this._size / this._limit) * 100 < 25){
      this._resize(this._limit / 2);
    }
    this._size--;
  }

  _resize(newLimit) {
    let oldStorage = this._storage; // 확장 전
    this._size = 0;
    this._limit = newLimit;
    this._storage = LimitedArray(this._limit); // 확장 후

    oldStorage.each((bucket) => {
      for(let key in bucket){
        this.insert(key, bucket[key]);
      }
    });
  }
}