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이라는 강력한 자바스크립트 내장 해시 테이블을 잘 이용하자는 것이다.

1. 완주하지 못한 선수(lv.1)

완주하지 못한 선수는 참가자 목록에는 있는데 완주자 목록에는 없는 1명을 찾아내는 문제다.

자바스크립트에서 지원하는 Map으로 frequency counter를 만들면 효율적으로 풀 수 있다. 즉, 참가자 목록에서 이름 당 몇번 등장했는지 세는 frequency counter를 만들고(동명이인이 있으니), 완주자 목록을 순회하며 frequency counter에서 차감한 후 counter가 여전히 1인 사람의 이름을 반환하면 된다.

그러면 여기서 해시는 어디에 쓰였나?라고 생각할 수 있는데, 자바스크립트에서 지원하는 Object, Map, Set가 기본적으로 해시 구조다. 참고로, Array 역시 인덱스를 문자열 키처럼 해석해서 접근하는 방식이긴 하지만 순차적 데이터라는 측면에서 인덱스 기반이고, 키 기반인 해시 테이블과는 차이가 있다.

javascript
function solution(participant, completion) {
    const map = new Map();
    
    for(const name of participant){
        map.set(name, (map.get(name) || 0) + 1);    
    }
    
    for(const name of completion){
        map.set(name, map.get(name) - 1);
    }
    for(const [name, counter] of map){
        if(counter > 0) return name;
    }   
}

2. 폰켓몬(lv.1)

폰켓몬은 문제 설명은 매우 긴데 생각해보면 그렇게 복잡하지 않은 문제다. 개인적으로는 풀어놓고도 이게 맞는건가, 내가 꼼수를 쓴건가 고심했다.

기본적으로 가장 다양하게 뽑을 수 있는건 n/2가 한계다. 여기서, 중복되는 폰켓몬의 수만큼 뽑을 수 있는 다양성이 줄어드므로 set을 활용해서 풀었다.

javascript
function solution(nums) {
    const set = new Set(nums);
    return Math.min(nums.length / 2, set.size)
}

3. 전화번호 목록(lv.2)

전화번호 목록은 문제 자체는 간단하지만 풀이는 마냥 단순하진 않다. 우선, 게으른 접근 방식인 이중 for문은 효율성 검사에서 탈락이다.

javascript
// 효율성 검사에서 탈락
function solution(pb) {
    for(let i = 0; i < pb.length; i++){
        for(let j = 1; j < pb.length; j++){
            if(i !== j && pb[j].startsWith(pb[i])) return false;
        }
    }
    return true;
}

여기서 가장 효율적인 방법은 내장된 sort를 쓰는 것이다. 자바스크립트의 Array.prototype.sort는 TimSort를 써서 O(n log n)의 시간 복잡도를 가진다. TimSort는 이미 정렬된 구간(run)을 찾고, run이 너무 짧으면 Insertion Sort로, run이 충분하면 정렬된 run들을 Merge Sort처럼 합병한다.

sort는 사전 순으로 정렬하기 때문에, 같은 숫자로 시작되는 데이터들은 인접하게 된다. 따라서 우선 정렬을 해두고, 인접한 두 요소들을 비교해 이전의 문자열이 다음 문자열의 시작 문자열이라면 false를 반환하고, 전부 순회했을 때 이런 케이스가 없다면 true를 반환하면 된다.

javascript
function solution(pb) {
    pb.sort(); 

    for (let i = 0; i < pb.length - 1; i++) {
        if (pb[i + 1].startsWith(pb[i])) {
            return false;
        }
    }
    return true;
}

다만 이 방법은 이 챕터의 주제인 해시를 활용한 방식은 아니다. 해시의 장점인 set과 has가 O(1)이라는 점을 활용하여, Map을 통해 아래와 같이 코드를 쓸 수 있다.

javascript
function solution(pb){
  const map = new Map();
  for(let num of pb){
    map.set(num, true);
  }

  for(let num of pb){
    for(let i = 1; i < num.length; i++){
      const prefix = num.slice(0, i);
      if(map.has(prefix)) return false;
    }
  }
  return true;
}

map.has()는 O(1)의 시간 복잡도를 가지기 때문에, 앞서 본 이중 for문과 비교하면 훨씬 빠르다. 좀 더 구체적인 숫자를 통해 비교해보면, 전화번호 100,000개가 주어진다고 하면 앞선 이중 for문은 100,000 ** 2, 즉 1조번의 연산을 거친다. 반면 해시를 활용한 풀이는 전화번호의 최대 길이(num.length)가 20이라고 가정하면 O(N * M), 즉 100,000 * 20 = 200만번 정도의 연산만 거치면 된다. 이는 map.has가 O(N)이 아니라 O(1)이기 때문에 가능한 것이다.

4. 의상(lv.2)

의상은 약간의 수학적 사고가 필요하다. 각 카테고리별로 해당 카테고리의 옷들 중 하나 또는 아무것도 안 입는 선택을 할 수 있으므로, 조합은 각 카테고리의 옷들 수 + 1을 모두 곱하는 것이다.

다만, 이렇게 하면 모든 옷을 안 입을 경우가 포함되므로 결과에서 그 경우의 수 1개는 빼야한다. 코드를 작성하면 아래와 같다.

javascript
function solution(clothes) {
    const map = new Map();
    for(const [name, type] of clothes){
        map.set(type, (map.get(type) || 0) + 1);
    }
    let result = 1;
    for(const count of map.values()){
        result *= (count + 1);
    }
    return result - 1;
}

5. 베스트앨범(lv.3)

베스트앨범은 3단계 문제답게 지금까지의 문제들보다 복잡하다. 다만, Map과 sort를 충분히 이해하고 있다면 시킨대로만 해도 풀리는 문제다.

많이 들은 장르순으로 세우기 위한 frequency counter용 Map과, 그렇게 줄세운 장르에서 순서대로 많이 들은 곡 제목, 그리고 인덱스 순서(동일 재생수시 인덱스 조건에 의해)를 저장할 수 있는 Map 두 개를 만들면 해결할 수 있다.

javascript
function solution(genres, plays) {
    const genreMap = new Map();
    const songMap = new Map();
    
    for(let i = 0; i < genres.length; i++){
        genreMap.set(genres[i], (genreMap.get(genres[i]) || 0) + plays[i]);
        
        if(!songMap.get(genres[i])){
            songMap.set(genres[i], []);
        }
        songMap.get(genres[i]).push({index: i, plays: plays[i]});
    }
    
    const genreSort = [...genreMap.entries()].sort((a, b) => b[1] - a[1]).map(([genre]) => genre)
    
    const result = [];
    for(const genre of genreSort){
        const songs = songMap.get(genre).sort((a, b) => {
            if(a.plays === b.plays) return a.index - b.index;
            return b.plays - a.plays;
        })
        result.push(...songs.slice(0, 2).map(song => song.index));
    }
    
    return result
}
PreviousBinary Heaps
Algorithm
NextGraphs
Algorithm