[자료구조] 해슁(Hashing)
1. 해쉬테이블
- dynamic set을 구현하는 효과적 방법 중 하나
- 평균 탐색, 삽입, 삭제 시간은 O(1)
- 최악의 경우 Θ(n)
- 해쉬함수 h를 이용해 키 k를 T[h(k)]에 저장
- h : U -> {0, 1, ..., m-1} (m : 테이블 크기, U : 모든 가능한 키들의 집합)
- 하나의 slot 혹은 bucket으로 사상됨
- 즉, 각 키는 0 ~ m-1의 정수로 mapping
2. 해쉬 함수의 예
- 모든 키를 자연수로 가정
예1) 문자열
ASCII 코드 : C = 67, L = 76, R = 82, S = 83
CLRS = (67 * 128^3) + (76 * 128^2) + (82 * 128^1) + 83 * (128^0)
예2) h(k) = k % m : key를 m으로 나눈 나머지
3. 충돌(Collision)
=> 서로 다른 키가 동일한 slot에 사상된다면?
- 서로 다른 키 k1, k2가 h(k1) = h(k2) 인 경우 즉, 해시값이 동일한 경우
- 정의 구역의 크기가 테이블 크기보다 크기 때문에 항상 발생 가능(단사함수 X)
** 단사함수가 되려면?
: 집합 A의 크기가 U보다 커야함. 즉, 테이블 크기 m이 U보다 크거나 같아야 함.
- 실제로 저장된 키들의 집합 A가 테이블 크기 m보다 큰 경우엔 당연히 발생
=> chaining / open addressing 으로 해결 가능
* 충돌을 해결하는 방법
1) Open Hashing
- Chaining
2) Closed Hasing
- Chaining(open hashing이면서 closed hashing)
- Open addressing
· linear probing
· quardratic probing
· double hashing
1) chaining
: 동일한 slot 으로 해슁된 모든 키를 하나의 연결리스트로 저장
① insert
- 키 k를 리스트 T[h(k)]의 맨 앞에 삽입 : 시간복잡도 O(1)
- 중복 저장이 허용되지 않으면, 삽입 시 리스트를 검색해야 함. => 시간복잡도 ∝ 리스트 길이
② search
- 리스트 T[h(k)]에서 순차검색 => 시간복잡도 ∝ 리스트 길이
③ delet
- 리스트 T[h(k)] 로부터 키를 검색 후 삭제
- 키를 검색해서 찾은 후에는 O(1)에 삭제 가능
- 최악의 경우 : 모든 키가 하나의 slot으로 해슁되는 경우
· 길이가 n인 연결리스트, 탐색시간은 Θ(n) + 해쉬함수 계산시간
- 평균시간복잡도 : 여러 slot에 얼마나 잘 분배되는지에 따라 결정
* SUHA(Simple Uniform Hashing Assumption)
- 각각의 키가 모든 slot에 균등한 확률로 독립적으로 해슁된다는 가정(성능분석을 위함)
-> hash 함수는 deterministic 하므로 현실에서 불가
- Load Factor α = n / m
· n : 테이블에 저장될 키 개수
· m : 해쉬테이블의 크기(연결리스트 개수)
· 각 slot 에 저장된 키의 평균 개수
· 연결리스트 T[j]의 길이를 nj 라고 할 때 E[nj] = α (한 slot으로 배분될 key의 기댓값)
2) open addressing
: 모든 키를 해쉬 테이블 자체에 저장, 테이블 각 slot에는 1개의 키만 저장
① linear probing
- h(k), h(k)+1, h(k)+2,.. 순서로 검사해 처음으로 빈 slot에 저장
- 테이블의 끝이 도달하면 처음으로 circular
- (b) : B5와 A5의 충돌 => 그 다음 slot이 비었으면 저장, 아니라면 다음 slot 이 비었는지 탐색
- (c) : C2와 A2의 충돌 => 최초로 빈 slot이 나올 때까지 탐색
B9와 A9의 충돌 => 테이블의 끝이므로 circular
- 단점
· primary cluster : 키에 의해 채워진 연속된 slot. 즉, 키들이 뭉쳐진 상태
· 클러스터링이 점점 더 커지는 경향 => 원래 저장되어야 할 곳보다 더 먼 곳에 저장. 검색시간 ∝ cluster 길이
/* h(x) 계산 */
/* T[h(k)], T[(h(k)+1)%b], .. , T[(h(k)+j)%b]의 순서로 slot 탐색
1) T[(h(k)+j)%b]에 값이 k인 키 쌍이 있는 경우
=> 원하는 쌍이 발견됨
2) T[h(k)+j]이 비어있는 경우
=> k는 테이블에 존재하지 않음
3) 시작 위치 T[h(k)]에 돌아온 경우
=> 테이블은 꽉 찼고, k는 테이블에 존재하지 않음
*/// 포인터 사용
#include <stdio.h>
int main() {
// 선형 조사법 해시 테이블 T에서 k 탐색
// 이 키를 가진 쌍을 발견하면 포인터 반환
// 그렇지 않으면 0
int i = h(k) // 홈 버킷
int j;
for (j = i; T[j] && T[j] -> first != k;) {
j = ( j + 1 ) % b; // 테이블을 원형으로 간주
if (j==i) // 시작점으로 복구
return 0;
}
if (T[j]->first == k)
return T[j];
return 0;
}
② Quadratic probing
: 검색에 필요한 탐색의 평균 횟수를 줄이는 방법
- 충돌 발생시 h(k), h(k)+1^2, h(k)+2^2, h(k)+3^2, ... 순서로 시도
- B2와 A2의 충돌 => h(B2) + 1^2, h(B2) + 2^2, h(B2) + 3^2 순서로 탐색
- C2와 A2의 충돌 => h(C2) + 1^2, h(C2) + 2^2, h(C2) + 3^2, h(C2) + 4^2 순서로 탐색
- 모든 키에 대한 offset이 동일
③ double hashing
- 클러스터링이 발생하지 않도록 하는 과정
- (h1(k) + i * h2(k)) mod m
- h1(14) = 1, h2(14) = 4 => offset = 4
- h1(15) = 2, h2(15) = 5 => offset = 5
* open addressing 의 단점
- 키를 삭제할 때 문제 발생
- A2, B2, C2가 동일한 해쉬함수값을 가져서 linear probing으로 해결한 후 B2 삭제, C2 검색
- 중간의 B2가 삭제되었기 때문에 C2까지 닿지 못함
- B2를 삭제한 후 C2를 삭제된 B2 자리에 놓아야 함. 즉, 삭제한 후 각 키들을 한 자리씩 이동해야함
* 좋은 해쉬 함수?
- 현실에서는 키가 랜덤하지 않는다.
- 키들이 특정한 패턴을 가지더라도 해쉬함수값이 불규칙적이 되도록 하는 것이 바람직
- 즉, 해쉬함수값이 키의 특정부분에 의해서만 결정되지 않아야 한다.
4. 해쉬함수
1) division 기법
- h(k) = k mod m
- 장점 : 한번의 mod 연산으로 계산하기 때문에 빠르다.
- 단점: 어떤 m 값에 대해서는 해쉬함수값이 키의 특정 부분에 의해 결정된다.
예를 들면, m = 2^p 일 때, 키의 하위 p비트가 해쉬함수값이 된다.
2) multiplication 기법
- 0~1 사이의 상수 a
- ka의 소수부분만 선택해 m을 곱한 후 소수점 아래를 버림
- 두 키가 유사하거나 공통점이 있다고 해도 최종적인 값을 예측하기 어렵다.
참고자료
https://new93helloworld.tistory.com/147
http://egloos.zum.com/itfs/v/9984604
https://www.fun-coding.org/Chapter09-hashtable.html