[자료구조] 해시 테이블(Hash Tables)

✅ 해시 테이블(Hash Tables)이란?

데이터를 저장하고 검색하는 데 사용되는 자료구조 중 하나입니다. 해시 테이블은 키(Key)와 값(Value)으로 이루어진 항목(Item)을 저장합니다. 해시 테이블은 배열(Array)과 유사한 구조를 가지고 있지만 배열과는 달리 인덱스(Index)가 정수가 아니라 키(Key)로 구성됩니다. 즉, 순서를 가지지 않습니다. 키(Key)는 해시 함수(Hash function)를 사용하여 배열의 인덱스로 변환됩니다.

해시 함수는 키(Key)를 해시값(Hash value)으로 매핑하는 함수입니다. 해시 함수는 입력이 동일하면 항상 동일한 해시값(Hash value)을 반환해야 합니다. 해시값(Hash value)은 배열의 인덱스와 같이 정수값이어야 합니다.

해시 테이블에서 값을 저장할 때는, 키(Key)를 해시 함수(Hash function)로 변환하여 해당 인덱스(Index)에 값을 저장합니다. 값을 검색할 때도 마찬가지로 키(Key)를 해시 함수(Hash function)로 변환하여 해당 인덱스(Index)에서 값을 검색합니다. 해시 테이블은 검색, 삽입, 삭제에 매우 빠른  속도를 제공합니다.

 

Pyothon - Dictionaries

JS - Objects and Maps

Java, Go, & Scala Maps

Ruby - Hashes

 

🤔 좋은 해시 함수는 무엇인가?

1. 빠름.

2. 일관된 방식으로 분배를 해서 다른 것들과 겹치지 않게 해야 함.

3. 결정론적(같은 입력에 같은 출력)

 

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

간단한 해시 함수로 이대로 호출하면 항상 정확히 같은 출력이 나옵니다. 하지만 몇 가지 문제가 있습니다. 

1. 오직 스트링에 대해서만 해시처리를 합니다.

2. 상수 값의 시간을 가지지 않습니다.

3. 무작위성이 떨어져 데이터가 뭉치기 쉽다. 해시 충돌(Hash collision)

위 해 함수를 개선해 보자.

 

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
}

최대 100개의 글자에만 루프를 돌도록 성능을 높이고 소수를 이용하여 균등하게 분포되도록 했습니다.

Prime Number

해시 함수에서는 키(Key)의 값을 일정한 범위의 해시값(Hash value)으로 변환합니다. 이때, 해시 함수는 다양한 키(Key) 값에 대해 충분히 균일한 분포를 가지는 해시값(Hash value)을 생성하는 것이 중요합니다. 이는 해시 충돌(Hash collision)을 최소화하고, 검색 속도를 높이기 위한 목적입니다.

WEIRD_PRIME이라는 변수는 이러한 목적으로 사용됩니다. WEIRD_PRIME은 일반적으로 소수(prime number) 중 하나를 선택하여 사용합니다. 이유는 소수를 사용하면, 곱셈 연산이 좀 더 균등하게 분포되기 때문입니다. 예를 들어, 2를 곱하면 끝자리가 항상 0, 2, 4, 6, 8 중 하나가 되지만, 31을 곱하면 끝자리가 0부터 30까지의 모든 수가 나올 수 있습니다. 이는 해시 충돌(Hash collision)을 줄이는 데에 도움을 줄 수 있습니다.

또한, WEIRD_PRIME은 보통 큰 소수(prime number) 중 하나를 선택합니다. 이는 해시값(Hash value)의 범위가 크기 때문에, 충돌이 발생할 가능성이 낮아집니다. 예를 들어, 배열의 크기가 100인 경우, 31을 사용해도 충분히 균일한 분포를 가질 수 있지만, 배열의 크기가 1000000인 경우에는 31보다 큰 소수를 사용하는 것이 더 적합합니다.

 

🟢 해시 충돌 다루기

이를 해결하기 위한 전략은 여러 가지가 있지만 두 가지만 다루어봅시다.

1. Separate Chanining - 개별 체이닝

Separate Chaining은 각각의 해시값(Hash value)이 가리키는 버킷(bucket)에 대해, 해당 버킷이 가리키는 연결 리스트(linked list)에 데이터를 저장하는 방식입니다. 즉, 같은 해시값(Hash value)을 가진 데이터는 하나의 연결 리스트에 저장되는 것입니다.

예를 들어, "apple"과 "banana"라는 두 개의 키(key) 값이 해시 함수에 의해 같은 해시값(Hash value)으로 변환된다면, 이 두 개의 값은 같은 연결 리스트에 저장됩니다. 연결 리스트는 데이터 삽입 시간에 동적으로 생성되며, 동일한 해시값(Hash value)을 가지는 데이터가 많아질수록 해당 연결 리스트의 길이는 더욱 길어질 수 있습니다.

Separate Chaining의 장점은 각 버킷(bucket)이 연결 리스트로 구성되기 때문에, 충돌이 발생해도 새로운 데이터를 쉽게 저장할 수 있다는 것입니다. 또한, 동일한 해시값(Hash value)을 가지는 데이터를 저장하는 연결 리스트의 길이가 짧으면 검색 시간도 빨라지는 장점이 있습니다.

하지만, Separate Chaining의 단점은 해시 테이블(Hash table)의 메모리 사용량이 많아질 수 있다는 것입니다. 동일한 해시값(Hash value)을 가지는 데이터가 많아지면, 해당 연결 리스트의 길이가 길어지기 때문에 메모리 사용량이 증가합니다. 또한, 연결 리스트를 구성하는 포인터(pointer)가 추가되므로, 포인터 오버헤드(pointer overhead)가 발생할 수 있습니다.

 

2. Linear Probing - 직선(선형) 탐색법

Linear Probing은 각각의 해시값(Hash value)이 가리키는 버킷(bucket)에 대해, 해당 버킷에 이미 데이터가 존재한다면, 다음 인덱스의 버킷부터 순차적으로 검사하여 첫 번째 비어있는 버킷에 데이터를 저장하는 방식입니다.

예를 들어, "apple"과 "banana"라는 두 개의 키(key) 값이 해시 함수에 의해 같은 해시값(Hash value)으로 변환된다면, 첫 번째 데이터("apple")는 해당 버킷에 저장되고, 두 번째 데이터("banana")는 다음 인덱스의 버킷부터 순차적으로 검사하여 첫 번째 비어있는 버킷에 저장됩니다.

Linear Probing의 장점은 해시 테이블(Hash table)의 메모리 사용량이 적다는 것입니다. 동일한 해시값(Hash value)을 가지는 데이터가 많아지더라도, 첫 번째 비어있는 버킷을 찾을 때까지 인접한 버킷을 순차적으로 검사하면 되므로, 추가적인 메모리 사용량이 거의 발생하지 않습니다. 또한, 데이터를 검색할 때 연결 리스트를 따라가는 과정이 필요하지 않으므로 검색 속도가 빨라집니다.

하지만, Linear Probing의 단점은 일정한 간격으로 버킷을 검사하기 때문에, 해시 충돌(Hash collision)이 발생할 경우 균등하게 분산되지 않을 수 있다는 것입니다. 이러한 현상을 클러스터링(clustering)이라고 부르며, 클러스터링이 심각해지면 검색 속도가 느려질 수 있습니다. 또한, 삭제 연산을 구현하기 어렵다는 것도 단점 중 하나입니다.

 

해시 테이블을 클래스로 구현해 봅시다. 이 과정은 해시 테이블의 동작 원리를 이해하기 위함입니다.

 

GET/SET

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
      total = (total * WEIRD_PRIME + value) % this.keyMap.length;
    }
    return total;
  }
  set(key,value){
    let index = this._hash(key);
    if(!this.keyMap[index]){
      this.keyMap[index] = [];
    }
    this.keyMap[index].push([key, value]);
  }
  get(key){
    let 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;
  }
}

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")

keys/values

  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;
  }

위 해시 테이블은 기본적이며 제대로 동작하는 코드는 아닙니다.

 

🟢 해시 테이블의 빅오

Insert: O(1)

Deletion: O(1)

Access: O(1)

 

 

참고 자료

https://www.geeksforgeeks.org/separate-chaining-collision-handling-technique-in-hashing/

https://www.hackerearth.com/practice/data-structures/hash-tables/basics-of-hash-tables/tutorial/