Hash Table

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

Object는 hash table로 만들어졌다고 할 수 있습니다.

Hash Table 가져오기, 추가, 삭제

해시 테이블은 값을 해시함수를 통한 특정 인덱스에 저장하기 떄문에 추가, 삭제 뿐 아니라 가져올 때도 O(1)의 시간만 필요합니다!

해싱이란? 🤔

해시 테이블을 이용한 탐색을 해싱이라고 합니다.

해싱은 키 값에 직접 산술적인 연산을 적용하여 항목이 저장되어 있는 테이블의 주소를 계산하여 항목에 접근합니다.

이때 사용되는 연산을 해시함수라고 합니다.

해시함수의 특징

해시함수의 특징은 크게 세가지 입니다.

1. table에 할당 된 크기 안에서 숫자를 리턴해야 합니다.(0 ~ length -1 사이의 값)

2. 언제든지 일정한 값을 출력해야 합니다.

3. 이전에 사용한 storage의 위치나 입력 문자열을 기억하지 않아야합니다.

해시충돌

해시함수에 어떠한 값을 넣었을 때, 이미 저장 되어있는 인덱스의 번호(이전의 값에서 나온 인덱스의 번호)가 또 return이 될 수 있습니다. 이를 해시충돌이라고 합니다.

이 해시충돌을 해결하기 위해서 storage의 bucket이라는 공간을 이용합니다. bucket안에는 [key, value]로 이루어진 tuple이 존재합니다.

해시 테이블에서 용어

• storage - 키와 값들을 저장하고 있는 table을 의미합니다.
• bucket - storage에 값을 가지고 있는 것들을 의미합니다.
• tuple - 각각의 bucket이 담고있는 데이터를 의미합니다.

해시테이블의 최악의 시간복잡도

크게 두가지 경우에 있습니다.

해시 테이블이 커질때, storage안의 값들을 모두 해싱을 다시 해줘야합니다. 그렇기 때문에 insert의 경우 O(n)의 시간 복잡도를 가집니다.

또, 만약 해시 함수의 연산의 결과가 모두같아 한 bucket에 들어가게 된다면 bucket에서는 검색이 O(n)의 시간 복잡도를 가지게 됩니다.

Hash Table 구현 💻

구현한 메소드

• insert(key, value) - 주어진 키와 값을 저장합니다. 이미 해당 키가 저장되어 있다면 값을 덮어씌웁니다.
• retrieve(key) - 주어진 키에 해당하는 값을 반환합니다. 없다면 undefined를 반환합니다.
• remove(key) - 주어진 키에 해당하는 값을 삭제하고 값을 반환합니다. 없다면 undefined를 반환합니다.
• _resize(newBucketNum) - 해시 테이블의 스토리지 배열을 newBucketNum으로 리사이징하는 함수입니다. 해시 테이블에 저장된 key-value 쌍이 bucketNum의 75%를 넘는 경우 bucketNum을 2배로 늘리고, 25%보다 작아지는 경우 bucketNum을 절반으로 줄입니다. 리사이징 후 저장되어 있던 값을 전부 다시 해싱을 해주어야 합니다. 구현 후 HashTable 내부에서 사용하시면 됩니다.

Pesuedo Code

• insert(key, value) - 우선 해시 펑션을 이용해 key와 value가 들어갈 인덱스를 구합니다. 다음 bucket을 생성합니다. 이미 해당 인덱스에 값에 버킷이 생성되어 있다면 그것을 사용하고 아니라면 빈배열을 선언합니다. 버킷안에 [key,value]의 형태로 push합니다.

• retrieve(key) - 해시 펑션을 이용해 인덱스를 구하고 해당 인덱스의 버킷을 조사해 value값을 return하고 존재하지 않는다면 undefined를 return 합니다.

• remove(key) - 이 역시 해시 펑션을 이용해 인덱스를 구하고 해당 인덱스의 버킷을 조사해 일치하는 key값이 존재한다면 삭제하고 value를 return 합니다.

• _resize(newBucketNum) - 새로운 사이즈의 storage를 생성합니다. 그리고 이전 storage안의 키, 값 쌍들을 다시 새로운 storage에 각각 insert 시킵니다.

해시테이블을 구현하기 위해서...

값을 해싱하기 위해서는 별도의 해싱함수가 필요합니다. 사용한 함수는 아래와 같습니다.

const hashFunction = function(str, max) {
  let hash = 0;
  for (let i = 0; i < str.length; i++) {
    hash = (hash << 5) + hash + str.charCodeAt(i);
    hash &= hash; // Convert to 32bit integer
    hash = Math.abs(hash);
  }
  return hash % max;
};

또한, 자바스크립트의 배열은 크기가 제한되어 있지 않은 동적 배열이기 때문에 배열의 크기를 제한시키기 위해 limitedArray(배열크기)라는 주어진 함수를 사용하였습니다.

const LimitedArray = function(limit) {
  const storage = [];

  const limitedArray = {};
  limitedArray.get = function(index) {
    checkLimit(index);
    return storage[index];
  };
  limitedArray.set = function(index, value) {
    checkLimit(index);
    storage[index] = value;
  };
  limitedArray.each = function(callback) {
    for (let i = 0; i < storage.length; i++) {
      callback(storage[i], i, storage);
    }
  };

  var checkLimit = function(index) {
    if (typeof index !== 'number') {
      throw new Error('setter requires a numeric index for its first argument');
    }
    if (limit <= index) {
      throw new Error('Error trying to access an over-the-limit index');
    }
  };

  return limitedArray;
};

Code

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

  insert(key, value) {
    const index = hashFunction(key, this._limit);
    // bucket
    let bucket;
    if(this._storage.get(index)){
      bucket = this._storage.get(index);
    }else{
      bucket = [];
    }
    // 해시 충돌이 없도록 insert
    // 1. 이미 동일한 키값이 있다면 덮어씌운다.
    for(let i of bucket){
      if(i[0] === key) {
        i[1] = value;
        return ;
      }
    }
    // 2. 동일한 키값이 없다면
    let tuple = [key, value];
    bucket.push(tuple);
    this._storage.set(index, bucket);
    this._size++;
    
    //인서트 후 사이즈가 75%를 넘긴다면 리사이즈 
    if (this._size > this._limit * 0.75) {
      this._resize(this._limit * 2);
    }
  }

  retrieve(key) {
    const index = hashFunction(key, this._limit);  
    let bucket = this._storage.get(index);
    
    if(!bucket) return undefined;
    for(let i of bucket){
      if(i[0] === key) return i[1]
    }
    return undefined;
  }

  remove(key) {
    const index = hashFunction(key, this._limit);
    let bucket = this._storage.get(index);
    let result = undefined;

    if(!bucket) return result;
    for(let i = 0; i < bucket.length; i++){
      if(bucket[i][0] === key){
        result = bucket[i][1];
        bucket.splice(i,1);
        this._size--;
        // 리무브 후 사이즈가 25%아래로 내려갔다면 리사이즈
        if (this._size < this._limit * 0.25) {
          this._resize(Math.floor(this._limit / 2));
        }
        return result;
      }
    }    
    return result;
    
  }

  _resize(newLimit) {
    let oldStorage = this._storage;

    this._limit = newLimit;
    this._storage = LimitedArray(this._limit);
    this._size = 0;

    oldStorage.each((bucket) => {
      if(bucket){
        for(let i = 0; i < bucket.length; i++){
          this.insert(bucket[i][0],bucket[i][1]);
        }
      }
    });
  }
}