[Hashing]

해쉬 테이블은 dynamic set을 구현하는 효과적인 방법 중 하나

• 적절한 가정하에서 평균 탐색, 삽입, 삭제시간 o(1)
• 보통 최악의 경우 o(n)

해쉬함수는 h를 사용하여 키 k를 T[h(k)]에 저장

• h  : U -> {0, 1, ... , m-1} 여기서 m은 테이블의 크기, U는 모든 가능한키들의 집합
• 키 k가 h(k)에 해슁되었다고 말함 

각 키에 대한 해쉬 함수값을 그 키를 저장할 배열 인덱스로 저장하는 것입니다.

 

h(x) = x % m 이렇게 하고 search 할 때도 1024라면 24이기에 24에 가서 찾으면 됩니다.  

 

해쉬함수의 예

모든 키들을 자연수라고 가정

 

문자열

• ASCII 코드 : C=67, L=76, R=82, S=83
• 문자열 CLRS는 (67*128^4) + (76 * 128^2) /// 

해쉬 함수의 간단한 예:

• h(k) = k % m
• 항상 0 ~ m-1 사이의 정수가 됨

Collision

두 개 이상의 키가 동일한 위치로 해슁되는 경우

 

즉 서로 다른 두 키 k1과 k2에 대해서 h(k1) = h(k2)인 경우

 

|U| >> m이므로 항상 발생 가능 

|K| > m이라면 당연히 발생 

 

충볼 발생 해결 방법 : chaining , open addressing

 

1. Chaining

- 각각의 슬롯에 하나만 저장한다고 가정하면 충돌이 발생 -> 여러 개 저장 가능하면 문제가 안된다.

- 이칸으로 대응되는 것을 연결리스트로 만들면 되는 것 

 

키의 삽입

- 키 k를 리스트 T[h(k)]의 맨 앞에 삽입 : 시간복잡도 o(1)

- 중복된 키가 들어로 수 있고 중복 저장이 허용되지 않는다면 삽입시 리스트를 검색해야 함. 따라서 시간복잡도는 리스트의 길이에 비례

 

키의 검색

- 리스트 T[h(k)]에서 순차검색

- 시간복잡도는 키에 저장된 리스트의 길이에 비례

 

키의 삭제

- 리스트 T[h(k)]로 부터 키를 검색 후 삭제

- 일단 키를 검색해서 찾은 후에는 o(1) 시간에 삭제 가능

 

최악의 경우 모든 키가 하나의 슬롯으로 해슁되는 경우

• 길이가 n인 하나의 연결리스트가 만들어짐
• 따라서 최악의 경우 탐색 시간은 o(n) + 해쉬함수 계산 시간
• 평균 시간복잡도는 키들이 여러 슬롯에 얼마나 잘 분배되느냐에 의해서 결정

 

SUHA

• 각각의 키가 모든 슬롯에서 균등 확률로 독립적으로 해슁된다는 가정 
• 성능 분석을 위해 주로 하는 가정이며 hash 함수는 deterministic하므로 현실에선 불가능

Load factor 알파 = n/m

• n : 테이블에 저장될 키의 개수
• m : 해쉬테이블의 크기, 연결리스트의 개수
• 각 슬롯에 저장된 키의 평균 개수 

연결리스트 T[j]의 길이를 nj라고 하면 E[nj] = 알파

만약 n = o(m)이면 평균검색시간은 o(1)

 

2. OpenAdressing

모든 키를 해쉬 테이블 자체에 저장

테이블의 각 칸에는 1개의 키만 저장

 

• Linear probing
• Quadratic probing
• Double hashing

Linear probing

순서로 검사하여 처음으로 빈 슬롯에 저장, 테이블 끝에 도달하면 다시 처음으로  circular하게 돌아감

 

단점

-primary cluster : 키에 의해서 채워진 연속된 슬롯들을 의미

-이런 cluster가 생성되면 이 cluster는 점점 더 커지는 경향

 

이것이 왜 단점이냐면 검색 시간이 클러스터의 길이에 비례하는 시간이 걸리기 때문

 

Quadratic probing

-충돌 발생 시 h(k) , h(k) + 1^2 , h(k)+2^2 .. 순서로 시도

 

Double hashing

-서로 다른 두 해쉬 함수 h1 h2를 이용하여 h(k,i) = h1(k) + i*h2(k)) mod m

-즉 key값에 따라서 얼마나 띄워서 하는지가 달라지는 것입니다.

 

Open Addressing 키의 삭제

• 단순히 키를 삭제할 경우 문제가 발생
  • 가령 A_2, B_2, C_2가 순서대로 모두 동일한 해쉬함수값을 거쳐서 linear probing으로 충돌 해결
  • B2를 삭제한 후 C2를 검색 

키를 삭제할 때 그냥 B2를 삭제하면 되는 것이 아니라 C2를 원래 B2자리로 옮겨야 하는 것입니다. 좀 더 정확하게 말하면 그 다음 연속해서 키를 보면 해쉬 함수값을  옮기고 다른 키로 옮기는 것이 필요합니다.

 

 

좋은 해쉬 함수란?

• 현실에서는 키들이 랜덤하지 않음
• 만약 키들의 통계적 분포에 대해서 알고 있다면 이를 이용해서 해쉬 함수를 고안하는 것이 가능하지만 현실적 어려움
• 키들이 어떤 특정한 패턴을 가지더라도 해쉬함수 값이 불규칙적이 되도록 하는 것이 바람직
  • 해쉬함수값이 키의 특정 부분에 의해서만 결정되지 않아야

Division 기법

• h(k) = k mod m 
• 예 : m =20 and k = 91 -> h(k) = 11
• 장점 : 한번의 mod연산으로 계산. 따라서 빠름.
• 단점 : 어떤 m값에 대해서는 해쉬 함수값이 키 값의 특정 부분에 의해서 결정되는 경우가 있음. 가령  m = 2^p 이면 키의 하위 p비트가 해쉬 함수값이 됨

Multiplication

• 0과 1사이의 상수 A 선택 : 0<A<1
• kA의 소수부분만을 선택
• 소수 부분에 m을 곱한 후 소수점 아래 버림
• 예 = m=9. wordsize = w= 5, k = 21
• A= 13/32를 선택 
• kA = 21*13/32 = 273/32 = 8 + 17/32
• m (kA mod 1) = 8  , 17/32 = 17/4 = 4...
• h(21) =4