키-주소 매핑으로 구현한 사전 ADT
구성요소
[ 해싱 예시 ]
원본 데이터 : abcdef
해시코드맵 : 각 문자의 아스키값을 더한 값을 출력
(97+98+99+100+101+102 = 597)
압축맵 h(k) = k%5
h(597) = 2
해싱 결과(=해시값)은 2, key는 597, 원소는 abcdef
+---+---+---+---+---+
| | | | | | <-- 크기 M=5의 버켓 배열 A
+---+---+---+---+---+
↑
A[2] 버켓에 abcdef 삽입- 버켓 : 키-원소 쌍, 또는 NoSuchKey를 담는 공간. 버켓 배열의 각 셀
- 버켓 배열 : 버켓의 집합. (e.g., 크기 M의 배열)
- 해시 함수(h) : 주어진 키를 고정 범위로 매핑하는 함수
- 해시코드 맵 : 압축 맵을 적용하기 전 주어진 키를 다른 값으로 재해석한 것 (e.g., 메모리 주소, 정수 캐스트, 요소합)
- 압축 맵 : 해시코드 맵 결과를 고정 범위로 매핑하는 함수
- 해시 값 : 해시 함수 적용 결과 나온 값
압축맵
해시 함수의 구성요소인 압축맵을 더 자세히 살펴보자.
흔한 방법으로 나누기, 승합제(MAD)가 있다.
결과적으로 두 방법 모두 버켓배열(해시테이블)의 크기 M으로 나머지연산한다.
이 M은 일반적으로 소수(prime)로 설정한다.
- 나누기 : h(k) = |k| % M
- 승합제 : h(k) = |ak+b| % M
- a,b는 음이 아닌 정수이고 a%M != 0이다.
충돌 해결
Collision resolution
충돌 : 해싱 결과 두 개 이상의 원소(e)가 같은 버켓으로 매핑되는 것
(예시) h(k) = k%7이고, 해싱할 두 개 데이터가 7, 14인 경우
→ A[10]으로 들어갈 자리가 같다. (충돌했다)
→ 아무튼 저장은 해야하니까, 둘 중 하나를 다른자리로 안내해줘야 한다.
해결 방법은 크게 분리 연쇄법, 개방 주소법으로 나뉜다.
- 분리 연쇄법 : 어떻게든 자기 버켓에 저장함
- 개방 주소법 : 다른 버켓에 저장함 (삭제 어렵고 군집화 발생)
- 선형 조사법
- 2차 조사법
- 이중 해싱
아래 예시에서는 간략한 설명을 위해 k=e라고 가정한다.
분리 연쇄법 (separate chaining)
각 버켓 A[i]가 원소를 담는 리스트 의 참조(헤더)를 저장한다.
즉, 충돌이 일어나도 다른 버켓으로 안보내고 자기 버켓에 주렁주렁 달아둔다.
👍 장점 : 단순하다. 빠르다.
😡 단점 : 해시테이블 외 추가 저장공간 필요.
가정 : 테이블크기 5, 해시함수 h(k)=k%5
데이터가 5, 7, 10 순으로 주어짐
1. 데이터 5는 어디로 가나 : h(5) = 0 이므로 A[0]으로 간다.
2. 데이터 7은 어디로 가나 : h(7) = 2 이므로 A[2]로 간다.
★ 3. 데이터 10은 어디로 가나 : h(10) = 0 이므로 A[0]으로 간다.
+---+---+---+---+---+
| L0| L1| L2| L3| L4| <-- 크기 M=5의 버켓 배열 A
+---+---+---+---+---+
↓ ↓
10 7
↓
5알고리즘은 아래와 같다.
Alg initBucketArray()
1. for i ← 0 to M-1
A[i] ← empty list
2. return
Alg findElement_FromHashtable(k)
1. item = A[h(k)].getItem(k)
2. return item.element
Alg insertItem(k, e)
1. A[h(k)].insertItem(k, e)
2. return
Alg removeItem(k)
1. return A[h(k)].removeItem(k)선형 조사법 (linear probing)
충돌이 발생하면 원래 들어갈 자리의 바로 다음 버켓에 저장한다.
저장하기 전 다음 버켓이 비었는지 검사한다. 이 때 검사되는 버켓을 조사라고 한다.
선형 조사법에 따라 아이템을 저장하면 그 양이 많아질수록 가까운 곳에 뭉쳐 저장 된다. 이 상황을 1차 군집화라고 한다.
- 다음 버켓 = A[h(k) + f(i)%M] --- f(i)=i, i=0,1,2,...
- 조사(probe) = 검사되는 각 버켓(테이블 셀)
- 1차 군집화 : 충돌 항목들이 더욱 긴 조사열로 군집하는 것
가정 : 테이블크기 5, 해시함수 h(k)=k%5
e=k인 데이터가 5, 7, 10, 20 순으로 주어짐
데이터 5 : h(5) = 0 --> 삽입
데이터 7 : h(7) = 2 --> 삽입
+---+---+---+---+---+
| 5 | | 7 | | |
+---+---+---+---+---+
데이터 10 : h(10) = 0
--> 엥? 뭐야 A[0]에 이미 뭐가 있잖아. i=0부터 h(k) + f(i)%M을 돌려보자
--> i=0일 때 h(k) + f(i)%M = 0+0 = 0.. 뭐가 있군
--> i=1일 때 h(k) + f(i)%M = 0+1 = 1.. ㅇㅋ 여긴 비었군
--> A[1]에 삽입
+---+---+---+---+---+
| 5 | 10| 7 | | |
+---+---+---+---+---+
데이터 15 : h(15) = 0
--> A[0]에 이미 뭐가 있네.. i=0부터 그 식을 돌려보자
--> i=0일 때 h(k) + f(i)%M = 0+0 = 0.. 뭐가 있군
--> i=1일 때 0+1 = 1.. 또 뭐가 있군
--> i=2일 때 0+2 = 2.. 또있네
--> i=3일 때 0+3 = 3.. 오! 여긴 비었네
--> A[3]에 삽입
+---+---+---+---+---+
| 5 | 10| 7 | 15| |
+---+---+---+---+---+2차 조사법 (quadratic probing)
선형조사법과 유사하다. 다만 조사 셀을 구하는 식이 약간 다르다.
A[ (h(k) + f(i)) %M ], f(i)= 이고 i=0,1,2,3,...,M-1
👍 의의 : 1차 군집화 피할 수 있음
😡 엥 근데ㅋㅋ : 2차 군집화가 발생함
😱 좀 심각한 문제 : M이 소수가 아니거나 버켓 배열이 반 이상 차면, 빈 버켓을 못찾고 그냥 지나쳐버릴 수 있음 (더하는 수 f(i)가 제곱이라서)
가정 : 테이블크기 5, 해시함수 h(k)=k%5
e=k인 데이터가 5, 10, 15, 20 순으로 주어짐
데이터 5 : h(5) = 0 --> 삽입
+---+---+---+---+---+
| 5 | | | | |
+---+---+---+---+---+
데이터 10 : h(10) = 0
--> i=1일 때 해시값 0+1 = 1
+---+---+---+---+---+
| 5 | 10| | | |
+---+---+---+---+---+
데이터 15 : h(15) = 0
--> i=1일 때 해시값 0+1 = 1
--> i=2일 때 해시값 0+4 = 4
+---+---+---+---+---+
| 5 | 10| | | 15|
+---+---+---+---+---+
데이터 20
--> i=1, 2일때 충돌
--> i=3일 때 해시값 (0+9)%5 = 4
--> i=4일 때 해시값 (0+16)%5 = 1
--> 엥 ㅋㅋ 다 봤는데 빈 데가 없네
--> 못 넣음 😱
+---+---+---+---+---+
| 5 | 10| | | 15|
+---+---+---+---+---+이중 해싱 (double hashing)
제 2의 해시함수 h'(k)를 사용한다.
조사 셀을 찾는 식은 ( h(k) + f(i) ) % M이다.
여기서 f(i) = ih'(k), i=0,1,2,...,M-1
함수 h'(k)는 아래 조건을 따른다.
- q는 q<M인 소수
- h'(k)는 M과 서로소이고 0이 아님.
- h'(k) = q - (k%q) 또는 1+(k%q)
가정 : 테이블크기 5, 해시함수 h(k)=k%5, h'(k)=3-(k%3)
e=k인 데이터가 5, 10, 15, 20, 100 순으로 주어짐
조사 셀은 idx
= (h(k) + f(i)) % 5
= ( k%5 + i x (3 - k%3) ) % 5 로 구함
데이터 5 : idx = 0 --> 삽입
+---+---+---+---+---+
| 5 | | | | |
+---+---+---+---+---+
데이터 10 : h(10) = 0이고 h'(10) = 2
--> i=0일 때 idx = 0
--> i=1일 때 idx = 0 + 1*2 = 2
+---+---+---+---+---+
| 5 | | 10| | |
+---+---+---+---+---+
데이터 15 : h(15) = 0이고 h'(15) = 3
--> i=1일 때 idx = 0 + 1*3 = 3
+---+---+---+---+---+
| 5 | | 10| 15| |
+---+---+---+---+---+
데이터 20 : h(20) = 0이고 h'(20) = 1
--> i=1일 때 idx = 0 + 1*1 = 1
+---+---+---+---+---+
| 5 | 20| 10| 15| |
+---+---+---+---+---+
데이터 100 : h(100) = 0이고 h'(100) = 2
--> i=1일 때 idx = 0 + 1*2 = 2
--> i=2일 때 idx = 0 + 2*2 = 4
+---+---+---+---+---+
| 5 | 20| 10| 15|100|
+---+---+---+---+---+개방 주소법 일반
앞서 개방 주소법의 예시로 아래 세 가지를 살펴보았다.
- 선형 조사법
- 2차 조사법
- 이중 해싱
알고리즘
세 알고리즘을 모두 설명할 수 있는 일반적인 알고리즘은 아래와 같다.
다음 조사 셀(버켓)을 구하는 getNextBucket(v, i)만 다르게 구현하면 된다.
Alg initBucket()
1. for i ← 0 to M-1
A[i].isEmpty ← True
2. return
Alg findElement(k)
1. v ← h(k)
i ← 0 # f(i)할 때 그 i 맞음
2. while(i<M)
idx ← getNextBucket(v, i)
if(A[idx].isEmpty) # 그런거 없다 (루프 도는 중에 알았다)
return NoSuchKey
elseif (k == A[idx].key) # 찾았다
return A[idx].element
else # 다음 조사 셀 찾아라
i ← i+1
3. return NoSuchKey # 그런거 없다 (루프 다 돌고 나서야 알았다)
Alg insertItem(k, e)
1. v ← h(k)
i ← 0
2. while(i&<M)
idx ← getNextBucket(v, i)
if(A[idx].isEmpty)
A[idx].key ← k
A[idx].element ← e
return
else
i ← i+1
3. overflowException()
4. return
Alg removeItem(k)
1. v ← h(k)
i ← 0
2. while(i<M)
idx ← getNextBucket(v, i)
if(A[idx].isEmpty)
return NoSuchKey
elseif (k == A[idx].key) # 삭제
A[idx].isEmpty ← False
return A[idx].element
else
i ← i+1
3. return NoSuchKey 비활성화
위 알고리즘의 removeItem은 문제가 있다.
키 k에 해당하는 아이템을 찾은 뒤 isEmpty속성을 False로 바꿔버린다.
이후 find, insert작업을 수행할 때 테이블을 순회할 것이고, isEmpty속성을 통해 이 아이템 이후로 더 볼지 말지를 결정한다. 여기서 문제가 발생한다.
분명 뒤에 유효한 아이템이 더 있을텐데, isEmpty만 믿고 탐색을 끝내버린다. 이 뒤의 아이템은 모두 접근이 불가능해진다.
그래서 각 아이템의 상태는 아래와 같이 3개로 지정해야 한다.
- empty : 아무것도 없음
- active : 유효한 데이터 들어있음
- inactive : active가 됐다가 remove해서 유효한 데이터 없음. 하지만 이 뒤에 active셀들이 있을지도?
알고리즘들은 이 세 개의 상태를 사용하여 탐색하도록 수정해야 한다.
성능
적재율
적재율 a = n / M
잘 설계된 해시함수를 사용했을 때 각 버켓의 기대 크기이다.
적재율은 낮게 유지될 수록 좋다. 성능에 직결되기 때문이다.
해시테이블의 find, insert, remove 작업의 기대실행시간은 이다.
- 분리 연쇄법의 경우
- a>=1일 수 있다. 비효율적으로 작동한다.
- a<1 이면 을 기대할 수 있다. (해시값 구해서 바로 접근하면 되니까)
- 개방 주소법의 경우
- 언제나 a<=1이다.
- a>0.5인데 선형/2차조사법이면 좀 그렇다. ( f(i)많이 돌려야되고.. 군집화되고... )
- a<=0.5이면 을 기대할 수 있다.
재해싱
원소를 삽입할 때 마다 해시테이블 성능을 위해(=적재율을 낮추기 위해) 재해싱 해야한다.
재해싱하기 좋은 때는 아래와 같다.
- 적재율 최적치 초과 시점
- 삽입 실패 시점
- 비활성 셀이 많을 때
재해싱은 아래 과정을 말한다.
- 버켓배열 크기 증가 시키기
- 새 버켓배열 크기에 맞춰 압축맵 수정
- 새 압축맵으로 기존 원소 다시 해싱해서 저장
성능분석
탐색, 삽입, 삭제
- 최악의 경우(키가 싹 다 충돌) : O(n)
- 적재율a가 적당하면 : O(1) 기대실행시간
개방주소법에서 삽입을 위한 기대 조사 횟수는 1 / (1-a)번
이중해싱 프로그램
C언어로 구현한 콘솔 프로그램이다.
/*
[사용법]
p : 해시테이블 상태 출력 (첫 줄 인덱스, 두 번째 줄 키)
i key elem : 해시테이블에 key-elem 쌍 삽입
f key : key에 해당하는 element 출력
r key : key에 해당하는 key-elem 쌍 삭제
q : 종료
=========================================================================================
[입력]
-----------------------------------------------------------------------------------------
p
i 200 90
f 45
i 201 95
r 99
r 200
f 200
i 201 96
f 201
r 10
q
=========================================================================================
[출력]
-----------------------------------------------------------------------------------------
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
. 28 10 38 20 2 30 12 40 22 4 32 14 . 24 6 34 16 . 26 8 36 18
[삽입] 정상적으로 삽입했습니다.
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
90 28 10 38 20 2 30 12 40 22 4 32 14 . 24 6 34 16 . 26 8 36 18
[탐색] 키 45에 대한 원소 : 18
[삽입] 정상적으로 삽입했습니다.
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
90 28 10 38 20 2 30 12 40 22 4 32 14 . 24 6 34 16 95 26 8 36 18
[삭제] 키 99에 대한 원소 : NoSuchKey (키에 대한 Item이 존재하지 않아 삭제할 수 없습니다.)
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
90 28 10 38 20 2 30 12 40 22 4 32 14 . 24 6 34 16 95 26 8 36 18
[삭제] 키 200에 대한 원소 : 90
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
. 28 10 38 20 2 30 12 40 22 4 32 14 . 24 6 34 16 95 26 8 36 18
[탐색] 키 200에 대한 원소 : NoSuchKey (입력한 키에 대한 원소가 존재하지 않습니다.)
[삽입] 이미 존재하는 키입니다. 다른 키를 선택해주세요.
[탐색] 키 201에 대한 원소 : 95
[삭제] 키 10에 대한 원소 : 4
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
. 28 10 38 20 2 30 12 40 22 . 32 14 . 24 6 34 16 95 26 8 36 18
=========================================================================================
*/
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
int findElement(int k);
int insertItem(int k, int e);
int removeItem(int k);
void showHashTable();
typedef struct _ITEM {
int status; // [상태별 값] empty : -2, inactive : -1, active : 0
int key;
int element;
} ITEM;
ITEM H[23]; // 해시테이블
int M = 23; // 해시테이블 전체 크기
int m = 0; // 해시테이블에서 active상태인 버킷의 개수
int q = 19; // 이중해싱에 사용되는 q
int main(){
// 해시테이블 초기화
for(int i=0; i<M; i++)
H[i].status = -2; // empty로 초기화
// 해시테이블에 20개 아이템 기본적으로 넣어주기
for(int i=1; i<=20; i++)
insertItem(i*5, 2*i);
// 명령 받기
char cmd = 0; // 명렁어 : q, i, f, r, p
int k = 0; // 명령어의 인수 (키)
int e = 0; // 명렁어의 인수 (원소)
while(cmd != 'q'){
printf("\n");
scanf("%c", &cmd); getchar();
if(cmd=='i'){ // ====== < 1. 삽입 > ======
// 1-1. 삽입을 수행할 수 있는지 검사 (시도할 가치가 있는지 검사)
scanf("%d%d", &k, &e); getchar();
if(m >= M){
printf("[삽입] 해시테이블이 가득 차서 삽입할 수 없습니다.\n");
continue;
}
if(findElement(k) != -1){
printf("[삽입] 이미 존재하는 키입니다. 다른 키를 선택해주세요.\n");
continue;
}
// 1-2. 삽입
int insertedIdx = insertItem(k, e);
// 1-3. 삽입 성공/실패 여부에 따라 출력
if(insertedIdx==-1)
printf("[삽입] 삽입에 실패했습니다.\n");
else
printf("[삽입] 정상적으로 삽입했습니다.\n");
showHashTable();
}
else if(cmd=='f') { // ====== < 2. 탐색 > ======
// 2-1. 탐색 수행
scanf("%d", &k); getchar();
e = findElement(k);
// 2-2. 탐색 성공/실패 여부에 따라 출력
printf("[탐색] 키 %d에 대한 원소 : ", k);
if(e == -1)
printf("NoSuchKey (입력한 키에 대한 원소가 존재하지 않습니다.)\n");
else
printf("%d\n", e);
}
else if(cmd=='r') { // ====== < 3. 삭제 > ======
// 3-1. 삭제 수행
scanf("%d", &k); getchar();
e = removeItem(k);
// 3-2. 삭제 성공/실패 여부에 따라 출력
printf("[삭제] 키 %d에 대한 원소 : ", k);
if(e == -1) // NoSuchKey이면 삭제하지 않았음을 안내
printf("NoSuchKey (키에 대한 Item이 존재하지 않아 삭제할 수 없습니다.)\n");
else // 삭제할 아이템을 찾았으면 삭제했음을 안내하고 showHashTable() 호출
printf("%d\n", e);
showHashTable();
}
else if(cmd=='p') { // ====== < 4. 출력 > ======
showHashTable();
}
}
return 0;
}
// --------------------
int insertItem(int k, int e) {
int h = k%M; // 첫 번째 해시함수 값
int hp = q-(k%q); // 두 번째 해시함수 값
int idx = h;
int cnt = 0;
while(cnt<M){
if(H[idx].status != 0) {
// 선택한 버킷이 empty 또는 inactive이면 (즉, active가 아니면)
// --> Item을 삽입하고 버킷 상태를 active로 전환
H[idx].status = 0;
H[idx].key = k;
H[idx].element = e;
m++; // 해시테이블 active버킷 개수 증가
return idx;
}
else { // 선택한 버킷의 상태가 active이면 인덱스 점프
idx = (idx+hp)%M;
cnt++;
}
}
return -1; // 삽입 실패
}
int findElement(int k) {
int h = k%M; // 첫 번째 해시함수 값
int hp = q-(k%q); // 두 번째 해시함수 값
int idx = h;
int cnt = 0;
while(cnt<M) {
if( H[idx].status == -2 ) // 버킷 상태가 empty이면 NoSuchKey리턴
return -1; // NoSuchKey
else if ( H[idx].status == 0 && H[idx].key == k ) // 키 k에 해당하는 Active상태의 버킷(Item)을 찾았으면 원소 리턴
return H[idx].element;
idx = (idx+hp)%M; // 아직 키 k에 해당하는 Item을 못찾았으면 인덱스 점프
cnt++;
}
return -1; // NoSuchKey
}
int removeItem(int k){
int h = k%M; // 첫 번째 해시함수 값
int hp = q-(k%q); // 두 번째 해시함수 값
int idx = h;
int cnt = 0;
while(cnt<M) {
if( H[idx].status == -2 ) // 버킷 상태가 empty이면 NoSuchKey리턴
return -1; // NoSuchKey
else if ( H[idx].key == k ) { // key찾았으면 버킷 상태를 inactive로 바꾸고 원소 리턴
H[idx].status = -1;
m--; // 해시테이블 active버킷 개수 감소
return H[idx].element;
}
idx = (idx+hp)%M; // 아직 못찾았으면 또 점프
cnt++;
}
return -1; // NoSuchKey
}
void showHashTable() {
// 첨자(주소) 출력
for(int i=0; i<M; i++)
printf("%d\t", i);
printf("\n");
// 각 첨자별 원소 값 출력
for(int i=0; i<M; i++){
if(H[i].status == 0) // active이면 원소 출력
printf("%d\t", H[i].element);
else
printf(".\t"); // empty 또는 inactive이면 점 출력
}
printf("\n");
}
노는게 제일 좋습니다.