Data Structure

Hash Table

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

Hash table method 구현

const LimitedArray = require('./helpers/limitedArray');
const hashFunction = require('./helpers/hashFunction');
// 위 문법은 helpers 폴더에 있는 limitedArray와 hashFunction을 불러오는 문법입니다.


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

  insert(key, value) {
    if(this._size++ / this._limit >= 0.75) {
      this._resize(2 * this._limit);
    }
    const index = hashFunction(key, this._limit);
    let val = this._storage.get(index);
    let obj = {};
    if(val) {
      obj = val;
      obj[key] = value;
      this._storage.set(index, obj);
    } else {
      obj[key] = value;
      this._storage.set(index, obj);
    }
  }

  retrieve(key) {
    //주어진 키에 해당하는 값을 반환합니다. 없다면 undefined를 반환합니다.
    const index = hashFunction(key, this._limit);
    return this._storage.get(index)[key];
  }

  remove(key) {
    //주어진 키에 해당하는 값을 삭제하고 값을 반환합니다. 없다면 undefined를 반환합니다.
    if(this._size / this._limit <= 0.25) {
      this._resize(parseInt(this._limit/2));
    }
    const index = hashFunction(key, this._limit);
    let el = this._storage.get(index);
    let retrieve = el[key];
    delete el[key];
    this._size--;
    return retrieve;
  }

  _resize(newLimit) {
    //해시 테이블의 스토리지 배열을 newLimit으로 리사이징하는 함수입니다. 리사이징 후 저장되어 있던 값을 전부 다시 해싱을 해주어야 합니다. 
    //구현 후 HashTable 내부에서 사용하시면 됩니다.
    this._limit = newLimit;
    this._size = 0;
    let newStorage = this._storage;
    this._storage = LimitedArray(this._limit);

    newStorage.each( (el) => {
      if(el) {
        for(let key in el) {
          this.insert(key, el[key]);
        }
      }
    });
  }
}
module.exports = HashTable;