[자료구조] 해쉬 테이블(Hash Table)

해쉬테이블

해시 테이블은 어떤 특정 값을 받으면 그 값을 해시 함수에 통과시켜 나온 인덱스(index)에 저장하는 자료구조

해싱, 해쉬 함수

• 해싱: 문자를 가져와 숫자로 변환하는 과정
• 해시 함수: 글자를 특정 숫자로 변환하는 데 사용한 코드. 동일한 문자열을 해시 함수에 적용할 때마다 항상 동일한 숫자를 반환해야 함

충돌 해결

이상적으로 해싱 결과로 생성된 index의 중복 없다면 좋겠지만, 만약 index에 해당하는 값이 여러 개인 경우에는 어떻게 해결할 수 있을까?

분리 연결법(Separate Chaining)

해당 인덱스에 들어오는 값들을 연결해서 충돌 체인을 형성한다. 이렇게 되면 해당 해시값에 해당하는 index의 list를 순회하며 내가 원하는 값을 찾을 수 있다.(링크드 리스트(Linked List)나 트리(Tree)로 구현)

개방 주소법(Open Address)

테이블 내의 새로운 주소를 탐사(Probe)한 후, 비어있는 곳에 충돌된 데이터를 입력하는 방식이다. 해시 함수를 통해서 얻은 인덱스가 아니라 다른 인덱스를 허용한다는 의미로 개방 주소(Open Address)라고 한다.

해쉬테이블 크기 재할당(Resizing)

해쉬테이블에 데이터가 과도하게 적재되는 경우, 해쉬 테이블 크기를 늘려주는 작업 또한 필요하다. 보통 기존 해쉬 테이블 크기의 2배 정도의 테이블을 생성하여 테이블을 옮겨 주는 방법으로 재할당을 하나, 충돌 체인을 형성한 경우 해싱작업을 다시 하서 길어진 리스트를 눠서 새로 저장하는 방법을 적용할 수 있다.

해쉬테이블 구현(Javascript)

function hashStringToInt(s, tableSize) {
  let hash = 17;

  for (let i = 0; i < s.length; i++) {
    hash = (13 * hash * s.charCodeAt(i)) % tableSize;
  }

  return hash;
}

class HashTable {
  table = new Array(3333);
  numItems = 0;

  resize = () => {
    const newTable = new Array(this.table.length * 2);
    this.table.forEach(item => {
      if (item) {
        item.forEach(([key, value]) => {
          const idx = hashStringToInt(key, newTable.length);
          if (newTable[idx]) {
            newTable[idx].push([key, value]);
          } else {
            newTable[idx] = [[key, value]];
          }
        });
      }
    });
    this.table = newTable;
  };

  setItem = (key, value) => {
    this.numItems++;
    const loadFactor = this.numItems / this.table.length;
    if (loadFactor > 0.8) {
      // resize
      this.resize();
    }

    const idx = hashStringToInt(key, this.table.length);
    if (this.table[idx]) {
      this.table[idx].push([key, value]);
    } else {
      this.table[idx] = [[key, value]];
    }
  };

  getItem = key => {
    const idx = hashStringToInt(key, this.table.length);

    if (!this.table[idx]) {
      return null;
    }

    // O(n)
    return this.table[idx].find(x => x[0] === key)[1];
  };
}

const myTable = new HashTable();
myTable.setItem("firstName", "bob");
myTable.setItem("lastName", "tim");
myTable.setItem("age", 5);
myTable.setItem("dob", "1/2/3");

참고

• How to Implement a Hash Table in JavaScript
• JavaScript와 함께 해시테이블을 파헤쳐보자