해시테이블은 키 값 쌍을 저장하는데에 사용한다. 배열과 다르게 해시 테이블의 키는 순서를 가지지 않는다. 또한 새로운 값을 추가하거나 제거할 때 아주빠르다.

파이썬의 딕셔너리나 자바스크립트의 맵과 객체, 자바, 고, 스칼라의 맵 등이 해시테이블 개념으로 코딩된 것이다. 색상을 저장하고, 그것을 불러 올 때 colors["cyan"]의 형태가 colors[2]보다 나을 것이다.

보통 대부분 언어는 해시테이블이 내장되어 있으나 이 포스트에서는 직접 구현해 볼 것이다.

string만을 사용한 해시함수

기본적으로 해시 함수의 정의는 수천자든 수백만 자든 임의의 크기를 데이터를 입력하면 정해진 크기의 데이터를 출력하는 함수다. 입력값을 측량해서 정해진 크기의 출력값을 내보낸다.

이 원칙을 토대로 구현한 간단한 해시 함수는 아래와 같다.

function hash(key, arrlen) {
  let total = 0;
  for (let char of key) {
    let value = char.charCodeAt(0) - 96;
    total = (total + value) % arrlen;
  }
  return total;
}

이 함수는 key의 길이 만큼 순회하여 값이 너무 커지면 순회를 너무 많이하게 되는 문제, 무작위성이 너무 낮은 문제가 있다.

아래는 소수를 적용하여 이를 약간 더 개선한 코드다. 해시테이블에 소수값의 길이를 적용하면 충돌이 날 확률이 줄어든다고 한다.

function hash(key, arrayLen) {
  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) % arrayLen; // 배열의 길이를 소수로 되도록한다.
  }
  return total;
}

여전히 이 코드는 pink와 kinp를 입력하면 충돌이 발생하는 썩 좋지 못한 코드다.

이를 해결하기 위해선 개별체이닝(Separate Chaining)과 직선 탐색법(Linear Probing)이 있다.

개별체이닝

개별체이닝은 배열이나 연결리스트 등과 같은 것을 활용하여 이중 데이터 구조를 쓰는 것이다.
가령 어떤 값을 해시함수에 통과시킨후 똑같이 4가 나왔을 경우 두 데이터 모두 배열 인덱스 4에 할당한다. 그럼 그 자리에는 2가지의 데이터가 존재하는 상태다. 이렇게 저장된 것을 찾을 땐 우선 4지점에 가서 다시 루프를 돌아 찾을 키-값을 찾아서 출력하게 된다.

직선탐색법

직선 탐색법은 각 위치에 하나의 데이터만 저장한다는 규칙을 그대로 살려서 지키려고 하는 것이다. 충돌이 일단 발생하면 다음 빈 칸이 어디인지 확인한다. 이렇게 하면 데이터가 같은 인덱스에 저장되는 것을 막을 수 있다.

해시테이블 구현하기

class HashTable {
  constructor(size = 53) {
    this.keyMap = Array.from({ length: 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);
    this.keyMap[index].push([key, value]);
  }
  get(key) {
    let index = this._hash(key);
    if (this.keyMap[index].length) {
      for (const a of this.keyMap[index]) {
        if (key === a[0]) return a[1];
      }
    }
    return undefined;
  }
  values() {
    let valuesArr = [];
    for (const el of this.keyMap) {
      if (el.length !== 0) {
        for (const a of el) {
          if (!valuesArr.includes(a[1])) valuesArr.push(a[1]);
        }
      }
    }
    return valuesArr;
  }
  keys() {
    let keysArr = [];
    for (const el of this.keyMap) {
      if (el.length !== 0) {
        for (const a of el) {
          if (!keysArr.includes(a[0])) keysArr.push(a[0]);
        }
      }
    }
    return keysArr;
  }
}

let ht = new HashTable(17);
ht.set("maroon", "#800000");
ht.set("yellow", "#FFFF00");
ht.set("olive", "#808000");
ht.set("salmon", "#FA8072");
ht.set("lightcoral", "#F08080");
ht.set("mediumvioletred", "#C71585");
ht.set("plum", "#DDA0DD");
ht.set("pink", "핑크");
ht.set("kinp", "what?");
ht.set("wwwwwwwww", "what?");

log(ht.get("yellow"), ht.get("pink"), ht.get("kinp"));
// #FFFF00 핑크 what?

log(ht.values());
// [
//   '#DDA0DD', '#FA8072',
//   '#800000', '#FFFF00',
//   '핑크',    '#808000',
//   '#F08080', 'what?',
//   '#C71585'
// ]
log(ht.keys());
//[
//   'plum',
//   'salmon',
//   'maroon',
//   'yellow',
//   'pink',
//   'olive',
//   'lightcoral',
//   'kinp',
//   'wwwwwwwww',
//   'mediumvioletred'
// ]

위 코드는 중복되는 key를 입력할 경우 일단 같은 공간에 저장되고, get을하면 가장 먼저 저장한 것을 받아오고, keys를 통해 key목록을 불러오면 중복을 제거하여 불러올 것이다. 이를 더 개선하면 set을 할 때 기존에 저장된 공간을 순회하여 key존재 여부를 확인 후 push할 수도 있을 것이다. 대부분 프로그래밍 언어는 여러번 삽입하려고 하면 나중에 삽입한 키로 덮어 씌운다.

이 코드는 실제 활용하기에는 정교하지 않아서 실제 적용하기에는 무리가 있다.

Big O

insert : O(1)
Deletion: O(1)
Access: O(1)