자바스크립트로 구현하는 해시테이블(HashTable) 클래스 완벽 가이드

해시테이블(HashTable)은 키(key)와 값(value)을 매핑해 저장하는 대표적인 자료구조입니다. 해시 함수가 키를 배열 인덱스로 변환해 주기 때문에 데이터의 검색·삽입·삭제를 평균 O(1)의 시간 복잡도로 처리할 수 있습니다. 자바스크립트에는 내장 Map 객체가 있지만, 해시테이블의 동작 원리를 깊이 이해하려면 직접 구현해 보는 것이 큰 도움이 됩니다.

아래는 체이닝(chaining) 방식으로 충돌(collision)을 처리하는 HashTable 클래스의 전체 구현입니다. 물론 더 효율적인 자료구조와 충돌 해결 알고리즘을 적용하면 성능을 한층 더 개선할 수 있습니다.

구현 예제

class HashTable {
  constructor() {
    this.container = [];
    // 충돌 발생 시 요소를 추가할 수 있도록
    // 빈 배열들로 컨테이너를 초기화합니다.
    for (let i = 0; i < 11; i++) {
      this.container.push([]);
    }
  }

  display() {
    this.container.forEach((value, index) => {
      let chain = value
        .map(({ key, value }) => `{ ${key}: ${value} }`)
        .join(" --> ");
      console.log(`${index}: ${chain}`);
    });
  }

  put(key, value) {
    let hashCode = this.hash(key);

    for (let i = 0; i < this.container[hashCode].length; i++) {
      // 같은 키가 이미 존재하면 값을 교체합니다.
      if (this.container[hashCode][i].key === key) {
        this.container[hashCode][i].value = value;
        return;
      }
    }

    // 새 키-값 쌍을 체인 끝에 추가합니다.
    this.container[hashCode].push(new this.KVPair(key, value));
  }

  get(key) {
    let hashCode = this.hash(key);
    for (let i = 0; i < this.container[hashCode].length; i++) {
      // 체인에서 해당 키를 찾습니다.
      if (this.container[hashCode][i].key === key) {
        return this.container[hashCode][i];
      }
    }
    return undefined;
  }

  remove(key) {
    let hashCode = this.hash(key);

    for (let i = 0; i < this.container[hashCode].length; i++) {
      // 체인에서 해당 키를 찾아 제거합니다.
      if (this.container[hashCode][i].key === key) {
        this.container[hashCode].splice(i, 1);
        return true;
      }
    }
    return false;
  }

  hash(key) {
    return key % 11;
  }

  forEach(callback) {
    // 각 체인을 순회하며
    // 모든 키-값 쌍에 콜백을 실행합니다.
    this.container.forEach(elem => {
      elem.forEach(({ key, value }) => callback(key, value));
    });
  }

  static join(table1, table2) {
    // 두 인자가 모두 HashTable인지 확인합니다.
    if (!(table1 instanceof HashTable) || !(table2 instanceof HashTable)) {
      throw new Error("Illegal Arguments");
    }

    let combo = new HashTable();
    table1.forEach((k, v) => combo.put(k, v));
    table2.forEach((k, v) => combo.put(k, v));
    return combo;
  }
}

HashTable.prototype.KVPair = class {
  constructor(key, value) {
    this.key = key;
    this.value = value;
  }
};

주요 메서드 살펴보기

생성자(constructor)

컨테이너를 길이 11의 빈 배열로 초기화합니다. 각 슬롯이 배열이기 때문에 서로 다른 키가 동일한 해시값을 가지는 충돌 상황에서도 여러 요소를 함께 저장할 수 있습니다. 이것이 바로 체이닝 방식의 충돌 처리입니다.

hash(key)

키를 11로 나눈 나머지를 반환하는 간단한 해시 함수입니다. 실제 환경에서는 문자열 키도 지원하고 충돌을 줄일 수 있는 더 정교한 해시 함수를 사용하는 것이 좋습니다.

put(key, value)

키의 해시값을 계산한 뒤 해당 버킷(bucket)을 확인합니다. 동일한 키가 이미 존재하면 값을 덮어쓰고, 그렇지 않으면 새로운 KVPair 객체를 체인 끝에 추가합니다.

get(key)

해당 버킷의 체인을 순회하며 키가 일치하는 요소를 찾아 반환하고, 찾지 못하면 undefined를 반환합니다.

remove(key)

키가 일치하는 요소를 찾아 splice()로 제거합니다. 삭제에 성공하면 true, 실패하면 false를 반환합니다.

forEach(callback)

모든 버킷과 체인을 순회하며 저장된 전체 키-값 쌍에 대해 콜백 함수를 실행합니다.

join(table1, table2) — 정적 메서드

두 HashTable을 하나로 병합하는 정적(static) 메서드입니다. 두 인자가 모두 HashTable 인스턴스인지 검사한 후, 각 테이블의 모든 항목을 새 테이블에 복사해 반환합니다. 참고로 원본 코드의 !table1 instanceof HashTable는 연산자 우선순위 때문에 의도대로 동작하지 않으므로, 위 코드처럼 !(table1 instanceof HashTable) 형태로 괄호를 감싸야 올바르게 검사됩니다.

마무리

이 구현은 해시테이블의 핵심 개념인 해싱, 버킷, 체이닝 기반 충돌 처리를 명확하게 보여주는 학습용 예제입니다. 실무 수준으로 발전시키려면 문자열 해싱 지원, 요소 수 증가에 따른 동적 리사이징(rehashing), 균형 트리 기반 충돌 처리 등을 추가해 성능과 안정성을 높일 수 있습니다.