[자료구조] 해시테이블

해시테이블

매우 빠른 평균 삽입,삭제,탐색 연산을 제공하는 자료구조입니다.

만약 해시테이블이 아닌 List에 Key와 Value쌍으로 저장하면 무엇이 문제일까?

중간요소가 삭제된 List의 탐색, 삽입,삭제의 시간복잡도를 생각해보면

탐색: 리스트 전체를 순회하면서 찾아야 하므로 O(N)
삽입: 빈 공간이 존재할 수도 있으므로 다 탐색한다고 하면 O(N)
삭제: 삭제도 탐색을 통해 저장된 위치를 알아야 삭제가 가능하므로 O(N)

모든 연산의 효율성이 좋지 못합니다.

해시테이블은 Key값을 해시함수를 통해서 얻은 결과값을 인덱스로 선택하여 Key와 Value를 저장합니다.

따라서 어떤 위치이던 Key값만 주어진다면 O(1)에 접근할 수 있습니다.

하지만 Key값을 해시함수를 통해서 얻은 결과 값의 위치에 이미 데이터가 저장되어 있다면?

이러한 경우를 Collision이 발생되었다고 하고 이를 해결하는 방법을 Collision Resolution Method라고 합니다.

해시함수

1. Division Hash Function

   $f(k) = (k\bmod p) \bmod m$ , ($k:$ 키값, $p:$ 굉장히 큰 소수, $m$: 해시테이블의 총 슬롯 수)

   키 값을 해시테이블의 총 슬롯수로 나눈 값을 인덱스로 사용

2. Perfect Hash Function

   이상적인 해시함수로 Key값을 해시하여 나온 값이 해시테이블의 각 Slot과 1:1로 매핑 되게 하는 함수입니다.

3. Universal Hash Function

   $p(f(x)==f(y)) = 1/m$

   Collision 발생확률이 1/총 슬롯수인 해시함수를 의미합니다.

   슬롯의 공간이 충분히 많으면 Collision 발생 확률이 크게 줄어들게 됩니다.

4. C-Universal Hash Function

   $p(f(x)==f(y)) = C/m$

   Universal Hash Function은 설계하기 어려우므로 이를 보완하기 위해 사용되는 해시함수입니다.

그 외에 Multiplication Hash Function, Folding Hash Function, Mid-Squres Hash Function, Extraction Hash Function이 존재합니다.

만약 Key 값이 정수가 아니라 문자열 타입인 경우?

1. Additive Hash Function
   $f(k) = \displaystyle\sum_{i=0}^nStr[i]AsciiCode$ $\bmod$ $m$

   문자열 각 문자의 아스키코드 합을 슬롯개수로 나누어 결과값을 구하는 해시함수

2. Rotating Hash Function

    h = initial-value
    for i in range(len(key)):
    	h = (h<<4)^(h>>28)^key[i]
    return h%p%m

3. Universal Hash Function

   $h= ((h*a)+key[i]) \bmod p$
   $return\ h \bmod m$

결국 좋은 해시함수는
1. 적은 충돌
2. Fast Computation (1과 2는 trade-off)
을 만족하는 해시함수입니다.

하지만 해시함수가 이상적인 1:1 관계가 아닌이상 충돌은 무조건 발생됩니다.

Collision Resolution Method

Open Addressing

1. Linear Probing

   Collisioin이 발생된 위치의 바로 다음 위치의 슬롯에 데이터를 저장하는 방법입니다.

   만약 다음 위치의 슬롯이 비어있지 않을 경우, 비어있는 공간을 찾을 때 까지 아래로 이동 후 해당 위치에 저장합니다.

  find-slot(key): # key 값이 있으면 slot 번호 리턴, 없으면 key값이 삽입될 slot 번호 리턴
    i = f(key)
    start = i
    while(H[i] == occupied) and H[i].key noeq key
      i = (i+1)%m
      if i == start : return Full
    return i

결국 복잡도는 Cluster의 길이에 비례합니다.

Cluster의 길이는 해시함수의 분산값에 따라

linear probing은 클러스터의 길이를 증가시키는데 큰 역할을 하므로 좋은 collision resolution method가 아닙니다.

2. Quadratic Probing
   k -> k+1^2 -> k+2^2
   linear probing보다 클러스터의 길이가 늦게 증가됨
   대신, remove연산시 더 복잡해짐
3. Double Hashing
   f g 두개의 해시 함수 사용
   f(key) -> f(key) + g(key) -> f(key) + 2g(key_ -> f(key) +3g(key)
   해시함수를 두번 하므로 오버헤드가 한번보다 크지만 성능상에 큰 부작용 야기x

Chaining

하나의 슬롯에 여러개의 아이템 저장
하나의 슬롯이 연결리스트

set O(1)
search O(충돌 key의 평균갯수 = 연결리스트 길이)
remove O(충돌 key의 평균갯수 = 연결리스트 길이) 연결리스트 평균길이 = O(1) -> 성능이 좋은 hash function(C-universal)

open addessing도 c-universal해시 func을 사용할 때 다음과 같은 시간복잡도를 가짐