해시테이블(Hashtable)

해시테이블(Hashtable)은 키(Key)를 값(Value)에 매핑하여 데이터를 저장하는 자료 구조입니다. 이를 통해 데이터의 추가, 검색, 삭제 등을 평균적으로 상수 시간(O(1))에 수행할 수 있습니다. 해시테이블의 핵심은 해시 함수(Hash Function)입니다. 해시 함수는 임의 크기의 데이터를 고정된 크기의 유일한 값(해시 코드)으로 변환합니다. 이 해시 코드는 배열의 인덱스로 사용되어, 데이터의 위치를 결정합니다.

해시 충돌(Hash Collision)

두 개 이상의 키가 같은 해시 값을 가지게 되는 경우를 해시 충돌이라고 합니다. 해시테이블 구현 시 충돌을 해결하는 방법은 여러 가지가 있지만, 가장 일반적인 두 가지 방법은 체이닝(Chaining)과 오픈 어드레싱(Open Addressing)입니다.

• 체이닝(Chaining): 각 인덱스에 연결 리스트를 사용하여 여러 개의 요소를 저장할 수 있게 하는 방법입니다. 충돌이 발생하면, 해당 인덱스의 리스트에 요소를 추가합니다.
• 오픈 어드레싱(Open Addressing): 충돌이 발생할 경우, 다른 인덱스를 찾아 데이터를 저장하는 방법입니다. 선형 조사(Linear Probing), 이중 해싱(Double Hashing) 등의 기법이 있습니다.

JavaScript에서 해시테이블 구현하기

JavaScript에서는 객체(Object)나 Map을 사용하여 해시테이블과 유사한 기능을 쉽게 구현할 수 있습니다. 하지만 학습 목적으로 간단한 해시테이블을 직접 구현해보겠습니다. 이 예제에서는 체이닝 방식을 사용합니다.

class HashTable {
  constructor(size = 53) {
    this.keyMap = new Array(size);
  }

  _hash(key) {
    let total = 0;
    let WEIRD_PRIME = 31;
    for (let i = 0; i < Math.min(key.length, 100); i++) {
      let char = key[i];
      let value = char.charCodeAt(0) - 96;
      total = (total * WEIRD_PRIME + value) % this.keyMap.length;
    }
    return total;
  }

  set(key, value) {
    let index = this._hash(key);
    if (!this.keyMap[index]) {
      this.keyMap[index] = [];
    }
    this.keyMap[index].push([key, value]);
  }

  get(key) {
    let index = this._hash(key);
    if (this.keyMap[index]) {
      for (let i = 0; i < this.keyMap[index].length; i++) {
        if (this.keyMap[index][i][0] === key) {
          return this.keyMap[index][i][1];
        }
      }
    }
    return undefined;
  }

  keys() {
    let keysArr = [];
    for (let i = 0; i < this.keyMap.length; i++) {
      if (this.keyMap[i]) {
        for (let j = 0; j < this.keyMap[i].length; j++) {
          if (!keysArr.includes(this.keyMap[i][j][0])) {
            keysArr.push(this.keyMap[i][j][0]);
          }
        }
      }
    }
    return keysArr;
  }

  values() {
    let valuesArr = [];
    for (let i = 0; i < this.keyMap.length; i++) {
      if (this.keyMap[i]) {
        for (let j = 0; j < this.keyMap[i].length; j++) {
          if (!valuesArr.includes(this.keyMap[i][j][1])) {
            valuesArr.push(this.keyMap[i][j][1]);
          }
        }
      }
    }
    return valuesArr;
  }
}

위의 예제는 해시테이블의 기본적인 구현을 보여줍니다. _hash 메소드는 주어진 키에 대한 해시 값을 생성합니다. 이 해시 함수는 간단하게 문자열의 각 문자에 대해 ASCII 값에 일정한 상수(WEIRD_PRIME)를 곱하고, 이를 해시 테이블의 크기로 나눈 나머지를 인덱스로 사용합니다. 이 방법은 충돌을 완전히 방지할 수는 없지만, 충돌의 가능성을 줄이고 해시 테이블 내에서 데이터를 균등하게 분포시키는 데 도움을 줍니다.

set 메소드는 주어진 키와 값을 해시 테이블에 저장합니다. 먼저 키를 해싱하여 인덱스를 얻고, 해당 인덱스에 값이 없으면 새 배열을 할당한 후 키와 값을 배열로 묶어 저장합니다. 만약 이미 해당 인덱스에 데이터가 있다면, 새로운 키와 값을 배열에 추가합니다.

get 메소드는 주어진 키에 해당하는 값을 찾아 반환합니다. 키를 해싱하여 얻은 인덱스로 접근한 후, 배열을 순회하며 키가 일치하는 요소를 찾아 그 값을 반환합니다. 키가 존재하지 않는 경우 **undefined**를 반환합니다.

**keys**와 values 메소드는 각각 해시 테이블 내의 모든 키와 값들을 배열로 반환합니다. 이 때 중복을 제거하기 위해 이미 반환된 키나 값은 다시 추가하지 않습니다.

이러한 구현은 JavaScript에서 객체나 **Map**을 사용하는 것보다 훨씬 더 많은 제어를 가능하게 합니다. 예를 들어, 사용자 정의 해시 함수를 통해 키의 해싱 방법을 조정할 수 있고, 충돌 해결 방법을 변경할 수도 있습니다. 하지만, 대부분의 경우 JavaScript의 내장 객체나 Map 객체가 훨씬 효율적이고 강력한 해시 테이블 기능을 제공하기 때문에, 복잡한 자료 구조를 직접 구현할 필요가 없을 수 있습니다.

그럼에도 불구하고, 해시테이블의 내부 작동 원리를 이해하는 것은 중요하며, 알고리즘 문제 해결이나 특정 애플리케이션에서 최적화가 필요한 경우에 유용하게 활용될 수 있습니다.