[자료구조] 해시법(hashing) 자바스크립트 구현

해시법

해시법은 데이터를 저장할 위치(인덱스)를 간단한 연산으로 구하여 검색과 추가, 삭제를 효율적으로 수행할 수 있는 방법이다.

 

아래 요소가 13개인 배열에서 앞쪽 10개 요소에 오름차순으로 정렬된 데이터가 저장되어 있다.

a[5, 6, 14, 20, 29, 34, 37, 51, 69, 75, -, -, -]

이 배열에 35를 추가하는 과정은 다음과 같다.

1. 삽입할 위치가 a[5]와 a[6] 사이임을 이진 검색법으로 찾는다.

2. a[6] 이후의 모든 요소를 하나씩 뒤로 이동한다.

3. a[6]에 35를 대입한다.

b[5, 6, 14, 20, 29, 34, 35, 37, 51, 69, 75, -, -]

요소 이동에 필요한 복잡도는 O(n)이므로 비용은 작지 않다. 데이터를 삭제하는 경우에도 똑같은 비용이 발생한다.

 

배열 a의 키값을 배열의 요솟수 13으로 나눈 나머지를 정리하면 다음과 같다.

5	6	14	20	29	34	37	51	69	75
5	6	1	7	3	8	11	12	4	10

이러한 값을 해시값이라 하며 데이터에 접근할 때 사용한다. 

해시값을 인덱스로 하여 원래의 키값을 저장한 배열이 해시 테이블이다. 해시 테이블의 각 요소는 버킷이라 한다. 다음은 위 해시값의 해시 테이블이다.

a[-, 14, -, 29, 69, 5, 6, 20, 34, -, 75, 37, 51]

35를 13으로 나눈 나머지는 9이므로 a[9]에 35를 저장한다. 새로운 값을 추가하더라도 다른 배열 요소를 뒤로 옮기지 않아도 된다. 이렇게 키값(35)을 해시값(9)으로 변환하는 과정을 해시 함수라고 한다.

b[-, 14, -, 29, 69, 5, 6, 20, 34, 35, 75, 37, 51]

충돌

배열에 새로운 값 18을 추가해 보자. 18을 13으로 나눈 값은 5이고 저장할 곳은 버킷 a[5]이다. 하지만 이 버킷은 이미 채워져 있다. 이렇게 저장할 버킷이 중복되는 현상을 충돌이라 한다.

충돌 해결 방법은 2가지가 있다.

• 체인법: 같은 해시 값을 가진 데이터를 연결 리스트로 저장
• 오픈 주소법: 빈 버킷을 찾을 때까지 해시를 반복

구현하기

1. 객체 사용

class HashTable {
  constructor(size = 50) {
    this.table = new Array(size);
  }

  // 키를 받아 해시 값을 생성  
  _hash(key) {
    let hash = 0;
    for (let i = 0; i < key.length; i++) {
      hash += key.charCodeAt(i);
    }
    return hash % this.table.length;
  }

  // 키와 값 저장
  set(key, value) {
    const index = this._hash(key);
    if (!this.table[index]) {
      this.table[index] = [];
    }
    this.table[index].push([key, value]);
  }

  // 키에 해당하는 값을 검색
  get(key) {
    const index = this._hash(key);
    if (!this.table[index]) return undefined;
    for (let pair of this.table[index]) {
      if (pair[0] === key) return pair[1];
    }
    return undefined;
  }

  // 특정 키 삭제
  remove(key) {
    const index = this._hash(key);
    if (!this.table[index]) return false;
    this.table[index] = this.table[index].filter(pair => pair[0] !== key);
    return true;
  }
}

const hashTable = new HashTable();
hashTable.set("name", "Kim");
hashTable.set("age", "20");
console.log(hashTable.get("name")); // Kim
console.log(hashTable.get("age"));  // 20
hashTable.remove("age");
console.log(hashTable.get("age"));  // undefined

2. Map 사용

const hashMap = new Map();
hashMap.set("name", "Kim");
hashMap.set("age", "20");
console.log(hashMap.get("name")); // Kim
console.log(hashMap.has("age"));  // true
hashMap.delete("age");
console.log(hashMap.get("age"));  // undefined