Hash Table

개요

비효율적이었던 맵을 개선 해보자.

 

맵의 모든 method를 그대로 가지고 있다.

 

추가로 볼만한 건 다음과 같다.

• entrySet(): 맵의 모든 entry를 리스트로 반환한다.
• keySet(): 맵의 모든 key를 리스트로 반환한다. / 파이썬의 dict.keys()
• values(): 맵의 모든 value를 리스트로 반환한다. / 파이썬의 dict.values()

해시 테이블은 해시 함수 h와 크기 N의 배열 (table)로 이루어진다.

 

 

해시 함수

해시 함수 h는 주어진 키 x를 정수 [0, N)에 매핑한다. (예: h(x) = x % N)

 

h(x)는 x에 대한 hash value이고, {키: 값} 쌍을 테이블 index h(키)에 저장하게 된다.

 

일반적으로 Hash code와 Compression function을 같이 사용한다.

 

Hash code는 임의의 타입 T를 정수형으로 변환하고, Compression function은 그 정수를 [0, N) 구간에 맞게 압축한다.

 

 

Hash Code

Integer cast

• 키의 bits를 integer로 읽는다. (int)key 같은 느낌인 것 같다.
• integer보다 작은 자료형의 키에 적합하다. (byte, short, int, float)

Component sum

• 키의 bits를 적당한(16, 32 등) 고정 길이로 쪼개어 더한다. (오버플로우는 무시한다.)
• integer보다 큰 자료형의 키에 적합하다. (long, double)

Polynomial accumulation

• Component sum의 방법처럼 쪼개어 sequence a₀ a₁ ... a_n-1을 얻는다.
• 이를 다항식 p(z) = a₀ + a₁z + a₂z² + ... + a_n-1z^n-1에 대입하여 계산한다. (오버플로우는 무시한다.)
• 특히 문자열에 적합하다.

 

Compression Function

Division

h(y) = y % N, N은 소수

 

Multiply, add and divide (MAD)

h(y) = (ay + b) % N, a, b는 a % N != 0인 음이 아닌 정수

 

 

충돌 처리

Separate Chaining

• 테이블의 각 Cell이 linked list를 가리키게 하여, 여기에 해시값이 같은 entry를 저장한다.
• 간단하고 직관적이나 테이블 이외 추가 메모리가 필요하다는 단점이 있다.

Linear Probing

 

Open addressing

• 충돌한 item을 테이블 내 다른 cell에 저장한다.

Linear probing

• 충돌한 item을 다음 (circularly) available한 cell에 저장하며, 이때 탐색되는 cell들을 probe라 한다.
• 충돌이 일어날 때마다 probe sequence는 길어지게 된다.

아래는 Linear probing을 이용한 find 함수의 예시이다.

 

void put(int k, int v) {
      if (size == cap) { cout << "FULL\n"; return; }
      int prob = 1;
      int H0, H = hashIt(k); H0 = H;

      while (table[H].f == OCCUPIED) {
         H = (H + prob++ * hashIt2(k)) % cap;
         if (H == H0) {
            cout << "BAD\n"; return;
         }
      }
      table[H].set(k, v);
      size++;
  }

 

Linear probing을 이용한 테이블 업데이트

AVAILABLE 객체로 삭제된 item을 대체한다.

• erase(k)는 키가 k인 entry를 찾아 AVAILABLE로 대체한다.
• put(k, o)는 h(k)에서 시작하여 비어있거나 AVAILABLE 상태의 cell을 찾으면 삽입하고, 어디에도 삽입할 수 없다면 예외를 throw한다.

 

Double hashing

2차 해시 함수 h'(k)를 이용해 테이블[(i + j*h'(k)) % N]를 탐색한다. j의 범위는 [0 : N) 이다.

 

N은 소수여야 함을 기억하자.

 

일반적인 2차 해시 함수는 h'(k) = q - (k % q) 이다. (q는 N보다 작은 소수)

 

 

퍼포먼스

최악의 (모든 키의 해시함수가 동일한) 경우 탐색, 삽입, 삭제에 O(N) 이다.

 

하지만 해시 함수를 잘 만들면 O(1)을 기대할 수 있다.

 

즉, load factor α = (실제 사용하는 키의 개수) / N이 100%에 가깝지 않다면 매우 빠른 동작을 기대할 수 있다.

 

좋은 글 ratsgo.github.io/data%20structure&algorithm/2017/10/25/hash

 

 

구현

다음은 Linear probing으로 충돌을 처리한 해시테이블의 구현 예시이다.

 

#include <bits/stdc++.h>
using namespace std;

enum { UNUSED, OCCUPIED, AVAILABLE };

typedef struct pii {
   int k, v, f;
   pii() {
      k = -1, v = -1, f = UNUSED;
   }
   pii(int key, int value) {
      k = key, v = value, f = UNUSED;
   }
   void set(int key, int value) {
      k = key, v = value, f = OCCUPIED;
   }
};

struct hashTable {
   int cap, size;
   vector<pii> table;

   hashTable(int c) {
      cap = c, size = 0;
      table.resize(cap);
   }

   int hashIt(int k) { return k % cap; }
   int hashIt2(int k) { return 17 - (k % 17); }

   void put(int k, int v) {
      if (size == cap) { cout << "FULL\n"; return; }
      int prob = 1;
      int H0, H = hashIt(k); H0 = H;

      while (table[H].f == OCCUPIED) {
         H = (H + prob++ * hashIt2(k)) % cap;
         if (H == H0) {
            cout << "BAD\n"; return;
         }
      }
      table[H].set(k, v);
      size++;
   }
   int get(int k) {
      int prob = 1;
      int H0, H = hashIt(k); H0 = H;

      while (table[H].f != UNUSED) {
         if (table[H].k == k) {
            return table[H].v;
         }
         H = (H + prob++ * hashIt2(k)) % cap;
         if (H == H0) {
            cout << "BAD\n"; return -1;
         }
      }
      return -1;
   }
   void erase(int k) {
      if (size == 0) { cout << "EMPTY\n"; return; }
      int prob = 1;
      int H0, H = hashIt(k); H0 = H;

      while (table[H].f != UNUSED) {
         if (table[H].k == k) {
            table[H].set(-1, -1);
            table[H].f = AVAILABLE;
            size--;
            break;
         }
         H = (H + prob++ * hashIt2(k)) % cap;
         if (H == H0) { cout << "BAD\n"; return; }
      }
   }
};

int main() {
   ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

   cout << "TABLE SIZE: "; int p; cin >> p;
   hashTable H(p);

   while (1) {
      string oper; int k, v;
      cin >> oper;
      if (oper == "put") {
         cin >> k >> v;
         H.put(k, v);
      }
      else if (oper == "get") {
         cin >> k;
         int req = H.get(k);
         if (req == -1) cout << "Such key does not exist.\n";
         else cout << req << "\n";
      }
      else if (oper == "erase") {
         cin >> k;
         H.erase(k);
      }
      else {
         for (auto i : H.table) cout << i.v << " ";
         cout << "\n";
      }
   }
   

   return 0;
}