sungyup's.

javascript_algorithm / 데이터 구조 / 4.8 Hash Tables

4.8Hash Tables

키-값 쌍을 저장하는 해시 테이블 데이터 구조 구현하기

TL;DR

Hash Table

해시 테이블(Hash Table, 또는 Hash Map이라고도 불림)은 키-값 쌍(key-value pair)을 저장하는데 쓰이는 데이터 구조다.

해시 테이블은 아주 빠르기 때문에 흔히 쓰이는 데이터 구조로, 대부분의 프로그래밍 언어들은 해시 테이블을 내장하고 있다. 자바스크립트에선 Object가 있고, Map은 일부 제한이 있지만 기본적으로는 해시 테이블이다. 파이썬에는 Dictionary가 있고, Java, Go 등은 Map이 있다.

해시 함수(또는 해시)는 키를 다른 데이터로 매핑하는 단방향 함수이다. 즉, 매핑의 결과로 키를 불러오는 것은 불가능하다. 때문에 해시는 암호화폐 등의 기술에도 쓰인다.

좋은 해시의 조건은 아래와 같다.

  1. 빠르다.(예: constant time)
  2. 데이터를 균일하게 분배해야 한다. 특정 범위에 클러스터가 생기면 안된다.
  3. 하나의 인풋은 늘 같은 결과를 가져와야 한다.

간단한 해시 만들기

위의 조건을 만족시키는 간단한 예시 해시 함수를 만들어보자. 문자열과 배열의 길이를 받아 배열 길이 미만의 숫자를 반환하는 해시 함수를 아래와 같은 방식으로 작성할 수 있다.

  1. 문자열의 각 문자 UTF-16 변환 숫자들을 합친다.
  2. 합친 값을 배열 길이로 나눈 나머지(%)를 구한다.

이렇게 하면 하나의 문자열에 대해선 늘 같은 결과가 나오고, 항상 배열 길이보다는 적고, 결과값에서 역으로 추론할 수는 없는 데이터가 나온다.

javascript
function hash(key, arrayLen){
  let total = 0;
  for (let i = 0; i < key.length; i++){
    let char = key[i];
    let value = char.charCodeAt(0) - 96; // 96을 빼야 a가 1, z가 26 식으로 매핑된다.
    total = (total + value) % arrayLen;
  }
  return total;
}

다만 이렇게 했을 때, 몇가지 문제가 예상된다.

  1. key가 아주 길어지면 루프가 너무 길어진다.
  2. arrayLen 미만의 수들에 골고루 분배가 되는지 어떻게 알 수 있을까?

개선 1. 루프 제한, 소수 활용

1번 문제를 해결하기 위해선 루프의 길이에 제한을 두면 된다.

2번 문제는 사실 해결하기 위해서 수학적 지식이 필요한데, 우리는 "소수(Prime Number)를 로직에 포함하면 좀 더 랜덤하게 데이터들이 잘 분포한다"라는 연구 결과를 받아들이고 소수를 로직에 추가하자.

javascript
function hash(key, arrayLen){
  let total = 0;
  const 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;
}

개선 2. 충돌 다루기(Collision Handling)

해시는 작동 방식의 근본적인 한계로 인해 충돌을 피할 수 없다. 따라서 충돌을 적절한 방식으로 핸들링하는 것이 중요하다. 충돌을 핸들링하는 대표적인 두 가지 방법은 아래와 같다:

1. Separate Chaining

배열의 각 인덱스에 일반적인 노드 하나가 아니라 배열 또는 linked list 같이 복합적인 데이터 구조를 적용하는 것이다. 즉, 하나의 인덱스에 여러개의 키-값 쌍이 있게 된다. 예를 들어, 아래의 경우 salmon이란 값을 찾을때, darkblue도 4라는 같은 인덱스에 있지만 해당 인덱스에서 salmon을 따로 찾아 원하는 값인 #fa8072를 매핑할 수 있다.

separate chaining
이미지 출처 : #
각 인덱스에 여러 데이터를 저장할 수 있는 데이터 구조를 도입함으로 충돌을 핸들링할 수 있는 separate chaining.

2. Linear Probing

충돌을 발견하면, 다음 빈 인덱스에 데이터를 저장하는 방식이다. 이 방법으론 각 인덱스에 하나의 데이터만 저장된다.

linear probing
이미지 출처 : #
충돌이 있으면 다음 인덱스에 데이터를 저장하는 linear probing.

개선 3. 해시 테이블 클래스로 확장

해시 함수를 포함한 해시 테이블 클래스를 만들고, set과 get 메소드를 구현해보자. 우선, 아래는 앞서 만든 해시 함수를 포함한 해시 테이블 클래스다.

javascript
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; // 96을 빼야 a가 1, z가 26 식으로 매핑된다.
      total = (total * WEIRD_PRIME + value) % this.keyMap.length;
    }
    return total;
  }
}

3-1. set 구현하기

수도 코드를 아래와 같이 작성할 수 있다:

  1. 키-값을 받는다.
  2. 키를 해시한다.
  3. separate chaining을 통해 키-값 쌍을 해시 테이블 배열에 추가한다.
javascript
class HashTable {
  constructor(size=53){
    this.keyMap = new Array(size);
  }
  _hash(key){
    // ...해시 메소드
  }
  set(key, value){
    const index = this._hash(key);
    if(!this.keyMap[index]){
      this.keyMap[index] = [];
    }
    this.keyMap[index].push([key, value]);
  }
}

3-2. get 구현하기

수도 코드를 다음과 같이 작성할 수 있다:

  1. 키를 받는다.
  2. 키를 해시한다.
  3. 해시 테이블에서 키-값 쌍을 받는다.
  4. 키가 없으면 undefined를 반환한다.
javascript
class HashTable {
  constructor(size=53){
    this.keyMap = new Array(size);
  }
  _hash(key){
    // ...해시 메소드
  }
  set(key, value){
    // ... set 메소드
  }
  get(key){
    const 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;
  }
}

3-3. keys와 values 메소드 구현하기

해시 테이블의 키들만, 그리고 값들만 반환하는 메소드를 구현해보자. 둘은 사실상 구현 로직이 동일하며, keyMap의 각 요소에 있는 배열들의 0번째 인덱스인지, 1번째 인덱스인지 여부에 의한 차이만 있다.

javascript
class HashTable {
  constructor(size=53){
    this.keyMap = new Array(size);
  }
  _hash(key){
    // ...해시 메소드
  }
  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;
  }
  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;
  }
}

해시 테이블의 Big O

해시 테이블은 평균적으로 삽입, 삭제, 접근이 모두 O(1)이다. 물론 실제 성능은 해시 함수 자체가 얼마나 빠르냐에 달렸지만, 데이터 양에 비해서 해시 테이블은 아주 우수한 성능을 보여준다.

단, 이를 위해선 앞서 언급했듯 해시가 빠르고, 데이터를 균일하게 분배해야 한다. 따라서 이런 조건을 갖춘 해시 함수는 일반적으로 직접 구현하기보단 좋은 해시 함수를 찾아서 쓴다.

🤠 프로그래머스 문제 풀기

프로그래머스에선 해시를 빈출 유형으로 분류하고, 코딩테스트 고득점 Kit이라는 카테고리에 5문제를 모아두었다. 이 문제들은 이 포스팅에 정리한다.

다 풀고 느낀건, Map이라는 강력한 자바스크립트 내장 해시 테이블을 잘 이용하자는 것이다.
PreviousBinary Heaps
Algorithm
NextGraphs
Algorithm