해시 테이블 (Hash Table)

Hash Table

해시 테이블(Hash Table)은 데이터의 해시 값을 키로 사용한 데이터 집합을 말합니다. 해시는 데이터를 새로운 형태로 변환한다는 의미를 가지고 있으며, 주어진 키를 미리 구현한 해시 함수를 통해 변환합니다. 해시 테이블은 해싱 된 키를 통해 데이터에 바로 접근할 수 있으므로, 매우 빠른 탐색 속도를 갖고 있습니다.

해싱 함수에 일반적으로 사용되는 방법은 다음과 같습니다.

• 나눗셈법: 키 값을 테이블의 사이즈로 나눈 후의 나머지를 주소로 사용하는 방법
• 자릿수 접기: 문자열 키 값의 자리마다 정해진 아스키 코드를 합친 값을 주소로 사용하는 방법

해시 테이블을 사용할 때는 충돌(Collision)과 클러스터링(Clustering)을 방지해야 합니다. 충돌은 말 그대로 동일한 해시 값이 만들어져 충돌이 발생하는 것이고, 클러스터링은 데이터가 한 곳에 몰리는 현상을 말합니다. 본문에서는 충돌을 해결하는 여러 방법 중 하나인 체이닝(Chaining)에 대해서만 소개합니다. 체이닝은 동일한 해시 값이 만들어져 충돌이 발생하면, 해당 위치를 링크드 리스트로 만들어 같은 해시 값을 가진 데이터들이 서로 연결되도록 합니다. 다만 이 경우에 충돌을 해결할 수는 있지만, 리스트가 순차 탐색을 하는 만큼 속도가 느려지게 됩니다.

노드 & 해시 테이블

function Node(key, data) {
  this.key = key;
  this.data = data;
  this.next = null;
}

function HashTable(size) {
  Array.call(this);
  this.size = size;
}
HashTable.prototype = Object.create(Array.prototype);
HashTable.prototype.constructor = HashTable;

해시 테이블을 배열처럼 사용하기 위해 배열의 프로토타입을 상속 받도록 구현했습니다. 그리고 해시 테이블의 크기를 해싱 알고리즘에 사용할 계획이기에 HashTable 생성자에서 매개변수로 size를 받도록 했습니다.

해싱 함수

HashTable.prototype.hash = function (key, keylen) {
  let hash = 0;
  for (let i = 0; i < keylen; i++) {
    hash = hash + key[i].charCodeAt(0);
  }
  return hash % this.size;
};

해싱(Hashing)은 로직을 통해 키(인덱스) 값을 결정하는 작업입니다. 해싱에 사용하는 알고리즘은 다양하지만, 본문에서는 위에서 언급한 자릿수 접기를 사용해 구현했습니다.

데이터 추가 & 획득

HashTable.prototype.set = function (key, value) {
  const addr = this.hash(key, key.length);
  const newNode = new Node(key, value);

  if (this[addr] === undefined) {
    this[addr] = newNode;
  } else {
    let temp = this[addr];
    newNode.next = temp;
    this[addr] = newNode;

    console.log(`충돌 발생: Key(${key}), Address(${addr})`);
  }
};

HashTable.prototype.get = function (key) {
  const addr = this.hash(key, key.length);

  if (this[addr] === undefined) {
    return null;
  }
  let current = this[addr];
  while (true) {
    if (current.key === key) {
      return current.data;
    }
    if (current.next === null) return null;
    else current = current.next;
  }
};

데이터를 추가하고 획득하는 두 함수는 해싱 함수를 통해 참조할 인덱스를 계산합니다. 체이닝은 링크드 리스트를 활용한 것이므로, 코드 자체가 어렵지는 않아 해시 중복(충돌)이 발생한 경우에 대해서만 설명하겠습니다. 중복 발생 시 set 함수에서는 리스트의 헤드를 교체하는 식으로 처리했고, get 함수에서는 순차적으로 리스트를 순회하며 key를 비교해 일치하는 데이터를 뽑을 수 있도록 했습니다.

References 📝

본문의 내용은 GeeksforGeeks의 자료구조 튜토리얼을 참고해 작성했습니다 ❤️