Hash Table

키와 값 쌍을 저장하고 있는 자료구조로 Hash Table은 키를 정할 때 메모리 공간을 덜 차지하기 위해 hash function을 이용해 특정 숫자의 값을 인덱스로 변환하여 사용하는데 이 과정을 해싱이라고 한다.
하지만 이 과정에서 키의 값은 다르더라고 해싱을 통해 나온 인덱스가 같은 경우가 있는데 이 경우를 해시 충돌(Hash Collision)이라고 한다.

해시 충돌(Hash Collision)을 해결하는 방법

1. 체이닝

버켓 내에서 연결 리스트를 할당하여, 버켓에 데이터를 삽입하다가 해시 충돌이 발생하면 연결 리스트로 데이터를 연결하는 방식이다.

2. 개방 주소법

해시 충돌이 발생하면 다른 버켓에 데이터를 삽입하는 방식이다.

HashTable 구현

• Hash Table 메서드

  1. insert(key, value) - 주어진 key를 hash function을 이용하여 index로 사용하고, 해당 index에 value를 저장 한다.
  2. retrieve(key) - 주어진 key에 해당하는 value를 반환한다.
  3. remove(key) - 주어진 key에 해당하는 값을 지운다.
  4. _resize(newLimit) - 만약 storage의 공간을 75%이상 사용하거나, 25%이하고 사용 중이라면 resize를 한다.

1. insert(key, value)

  insert(key, value) {
    const index = hashFunction(key, this._limit);
    let bucket = {};
    if (this._storage.get(index) === undefined) { // 해당 index에 값이 없으면 value 할당
      bucket[key] = value;
      this._storage.set(index, bucket);
    } else { // index에 이미 값이 존재한다면 
      bucket = this._storage.get(index);
      bucket[key] = value;
      this._storage.set(index, bucket);
    }
    this._size++;

    const cursize = (this._size / this._limit) * 100;
    if (cursize > 75) { // this.storage 공간을 75%이상 사용시 resize한다.
      this._resize(this._limit * 2);
    }
  }

2. retrieve(key)

retrieve(key) {
  const index = hashFunction(key, this._limit);
  if (
    this._storage.get(index) === undefined ||
    this._storage.get(index)[key] === undefined
  ) { // 해당 index에 값이 없거나 bucket에 key가 존재하지 않으면 undefined를 반환
    return undefined;
  }

  const result = this._storage.get(index)[key];
  return result;
}

3. remove(key)

remove(key) {
    const index = hashFunction(key, this._limit);
    delete this._storage.get(index)[key];

    if ((this._size / this._limit) * 100 < 25) { // this._storage공간의 25% 이하로 사용중이라면 resize한다.
      this._resize(this._limit / 2);
    }
    this._size--;
  }

4. _resize(newLimit)

_resize(newLimit) {
    this._limit = newLimit;
    let curstorage = this._storage;
   
    this._storage = LimitedArray(this._limit);
    this._size = 0;
  
    curstorage.each((bucket) => {
      for (let key in bucket) {
        this.insert(key, bucket[key]);
      }
    });
  }