[Data-Structure] HashTable (해시 테이블)

오늘은 해시 테이블(HashTable)에 대해서 공부했다.

해시 테이블(hash table), 해시 맵(hash map), 해시 표는 컴퓨팅에서 키를 값에 매핑할 수 있는 구조인, 연관 배열 추가에 사용되는 자료 구조이다. 해시 테이블은 해시 함수를 사용하여 색인(index)을 버킷(bucket)이나 슬롯(slot)의 배열로 계산한다. (위키 백과)

해시 테이블에 대해서 알아보기 위해 JS로 간단하게 구현해보았다.

해시 함수 hashFunction()을 따로 만들어주고 JS의 배열 대신 크기를 조절할 수 있는 배열 LimitedArray를 새로 만들어 주었다.

HashTable이라는 클래스를 선언해준 다음에 메서드들을 정의했다. 

정의된 메서드들은 다음과 같다. 

• insert(key, value) : 주어진 키와 값을 저장한다. (이미 해당 키가 저장되어 있다면 값을 덮어 씌운다.)
• retrieve(key) : 주어진 키에 해당하는 값을 반환한다. (없다면 undefined)
• remove(key) : 주어진 키에 해당하는 값을 삭제하고 값을 반환 (없다면 undefined)
• _resize(newLimit) : 해시 테이블의 스토리지 배열을 newLimit으로 리사이징

먼저 해시함수는 다음과 같다.

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;
};

 

다음은 해시 테이블 코드이다.

class HashTable {
  constructor() {
    this._size = 0; // 현재 해시테이블의 크기
    this._limit = 8; // 크기를 8로 제한 
    this._storage = LimitedArray(this._limit); // LimitedArray로 저장소를 생성
  }

  // 주어진 키와 값을 저장 (이미 해당 키가 저장되어 있다면 값을 덮어씌움)
  insert(key, value) {
    const index = hashFunction(key, this._limit); // 해시 함수로 인덱스 생성
    let obj = {}; // 값을 key: value 로 저장하기 위해 객체 생성

    // 해시함수를 거쳐 나온 값이 이미 테이블에 들어 있을 경우
    if (this._storage.get(index) !== undefined && !(key in this._storage.get(index))) { // key 값이 같지 않을 때 -> 튜플
      obj = this._storage.get(index); // obj에 현재 인덱스에 있는 값 저장
    }

    obj[key] = value; // 이미 있는 값은 덮어 씌워주고 없는 값은 추가 됨
    this._storage.set(index, obj); // 해당 값을 스토리지에 저장
    this._size++; // 사이즈 증가 

    // 제한 메모리 값보다 현재 사이즈가 커질경우 -> resize
    if (this._size > this._limit - 2) { // 전체 사이즈의 75% 보다 요소 수가 커지면
      this._resize(this._limit*2); // 값을 두 배로 증가
    }
  }

  // 주어진 키에 해당하는 값을 반환. (없다면 undefined를 반환)
  retrieve(key) {
    const index = hashFunction(key, this._limit); // 해시함수로 인덱스 생성
    const result = this._storage.get(index); // 인덱스 값으로 해당 스토리지에서 값 찾아오기
    if (result !== null) { 
      return result[key]; // 해당 값이 들어 있을 때 
    } else {
      return undefined; // 값이 없을 때
    }
  }

  // 주어진 키에 해당하는 값을 삭제하고 값을 반환. (없다면 undefined를 반환)
  remove(key) {
    const index = hashFunction(key, this._limit); // 해시 함수로 인덱스 생성
    const result = this._storage.get(index); // 인덱스로 스토리지에서 해당 값 가져오기
    if (result !== null) {
      delete result[key]; // 값을 찾았다면 key값에 해당하는 값을 객체에서 제거
      this._size --; // 사이즈 감소
      if(this._limit === 16 && this._size < 4 ){ // size가 너무 작아지면 다시 축소 (25%보다 요소수가 작아지면)
        this._resize(this._limit / 2); // 스토리지의 사이즈를 절반으로 축소
      }
    } else {
      return undefined; // 인덱스를 이용해서 찾은 값이 없다면 -> 해당 스토리지에 값이 없는 경우
    }
  }

  // 해시 테이블의 스토리지 배열을 newLimit으로 리사이징하는 함수.
  _resize(newLimit) {
    // 기존 값 저장
    const old = this._storage;

    // size 초기화
    this._size = 0;
    this._limit = newLimit; // 해시 테이블의 크기를 새 크기로 지정
    
    // 기존 배열 초기화
    this._storage = LimitedArray(this._limit);

    old.each(el => { // 기존의 배열에서 하나씩 꺼내 스토리지에 추가
      if(!el)
        return;
      for(let key in el){
        this.insert(key, el[key]);
      }
    })
  }
}

 

해시는 한 번 해시를 거치면 복호화가 불가능 하지만 key: value 형식으로 객체 형태로 저장하면 키 값을 불러올 수 있다. 

해시를 거친 키 값이 충돌한다면 키 값이 같을 때는 덮어 씌우면 되지만 키 값이 다를 때는 인덱스를 바꿔주거나 튜플 형태로 저장해주어야 한다. (여기서는 튜플처럼 인덱스에 해당하는 obj의 값을 추가해줬다.)