자바스크립트로 해시 테이블에 요소 추가하기

충돌(Collision) 해결이 핵심이다

해시 테이블에 요소를 추가할 때 가장 중요하게 고려해야 할 부분은 바로 충돌(collision) 해결입니다. 서로 다른 키가 동일한 해시 값을 가질 수 있기 때문인데요, 이번 글에서는 대표적인 충돌 해결 기법인 체이닝(chaining) 방식을 사용하겠습니다.

체이닝 외에도 개방 주소법(open addressing) 등 다양한 충돌 해결 알고리즘이 존재합니다. 관심 있는 분들은 아래 위키백과 문서에서 자세히 살펴볼 수 있습니다.
참고: Hash Table - Collision Resolution (Wikipedia)

put 메서드 구현

이제 실제 구현 코드를 살펴보겠습니다. 설명의 단순화를 위해 이 글에서는 정수형 키만 처리하는 해시 함수를 사용합니다. 하지만 더 복잡한 해싱 알고리즘을 적용하면 문자열이나 객체 등 어떤 타입의 데이터도 해싱할 수 있습니다.

아래 put(key, value) 메서드는 먼저 키의 해시 값을 계산한 뒤, 해당 버킷(bucket)에 같은 키가 이미 존재하는지 확인합니다. 키가 존재하면 기존 값을 새 값으로 교체하고, 존재하지 않으면 새로운 키-값 쌍(KVPair)을 버킷 배열의 끝에 추가합니다.

예제 코드

put(key, value) {
  let hashCode = 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));
}

동작 테스트

위에서 구현한 메서드는 다음과 같이 테스트해 볼 수 있습니다.

테스트 코드

let ht = new HashTable();
ht.put(10, 94);
ht.put(20, 72);
ht.put(30, 1);
ht.put(21, 6);
ht.put(15, 21);
ht.put(32, 34);
ht.display();

실행 결과

위 코드를 실행하면 다음과 같은 출력을 얻을 수 있습니다.

0:
1:
2:
3:
4: { 15: 21 }
5:
6:
7:
8: { 30: 1 }
9: { 20: 72 }
10: { 10: 94 } -->{ 21: 6 } -->{ 32: 34 }

결과 해석

출력 결과를 보면 인덱스 10번 버킷에 세 개의 키-값 쌍({ 10: 94 }, { 21: 6 }, { 32: 34 })이 연결 리스트 형태로 저장된 것을 확인할 수 있습니다. 이것이 바로 체이닝 방식으로 충돌을 해결한 결과입니다. 서로 다른 키가 같은 해시 값(버킷)으로 매핑되었지만, 각 버킷 내부에서 리스트로 관리되기 때문에 데이터가 손실되지 않고 모두 정상적으로 저장됩니다.