이번 포스트에서는 해쉬테이블의 대한 내용과 그 구현에 대해서 설명하도록 하겠습니다.
해쉬테이블
해쉬테이블이란, 해쉬함수에 기반하여 키, 값의 쌍을 저장하는 자료구조 입니다.
삽입, 삭제, 탐색의 연산을 평균적으로 O(1)의 시간복잡도로 처리할 수 있고, 최악의 경우 O(n)의 시간복잡도가 소요됩니다.
키, 값의 쌍을 저장하는 경우 사전의 표현이 가능하고, 키만 저장하는 경우 집합의 표현이 가능합니다.
여기서 말하는 사전이란, 키와 값의 쌍들의 모음을 다루는 추상자료형으로 삽입, 삭제, 탐색의 연산이 가능합니다.
해쉬함수
해쉬함수란, 키를 입력으로 받아 해쉬테이블 내 키와 값이 저장될 위치 인덱스를 출력해주는 함수입니다.
이때 출력 값을 보통 해쉬 값, 해쉬 코드 등으로 부릅니다.
하지만, 해쉬함수를 거쳐서 나온 해쉬 값이 동일한 경우, 이를 충돌이 발생했다고 합니다.
따라서, 해쉬함수를 정의할 때 함수 계산 시간이 빨라야하며, 충돌이 적게 구현하는 것이 좋습니다.
이렇게 키를 해쉬테이블 내 인덱스로 매핑하는것을 해싱이라고 합니다.
정수 키를 해싱하는 방법으로는 제산법과 폴딩법, 중간제곱법이 있습니다.
제산법이란, 해쉬테이블 크기 M과 정수 키 K에 대해, 해쉬함수를 HashFunction(K) = K mod M 으로 작성합니다.
폴딩법이란, 키를 여러 부분으로 나누고 나눈 부분들을 모두 더하거나 배타적 논리합 (XOR) 을 수행합니다.
폴딩법은 크게 이동 폴딩과 경계 폴딩으로 나뉩니다.
먼저 이동 폴딩은 나눈 키의 부분들을 다 더하여 인덱스 값을 도출합니다.
다음으로 경계 폴딩은 나눈 키의 부분들을 더하는데, 이때 앞은 원래 나눠진 키값으로 더하고 그 다음 값은 나눠진 키값에 역을 취하여 더하는 방식입니다.
EX) 123 | 203 | 241 | 112 | 20 ======(나눠진 키값)
123 + 302 + 241 + 211 + 20 = 897(인덱스 값)
마지막으로 중간제곱법은 키 값을 제곱한 결과에서 중간부분을 취하는 방법입니다.
EX) 키 값이 512라고 가정, 중간제곱법을 취하면 512^2 = 262144
따라서 결과값으로 21을 도출함.
다음으로 문자열 키를 해싱하는 방법입니다.
문자열 내 각 문자에 해당하는 정수들의 합(ASCII 값)을 구하여 문자열을 정수로 변환하여 해싱합니다.
이때, 이 방법은 동일문자로 구성되어 순사만 다른 문자열을 구분할 수 없으므로, 단순 합산 대신 문자열 내 문자 위치를 반영한 수를 ASCII값에 곱합 값을 합산합니다.
EX) ABC -> 65 + 66 + 67
CBA -> 67 + 66 + 65 (이 경우, 서로 다른 문자열이지만, 해쉬함수의 결과값이 같아 충돌발생)
ABC -> 65 * 31^2 + 66 * 31^1 + 67 * 31^0
CBA -> 67 * 31^2 + 66 * 31^1 + 65 * 31^0 (각 문자 위치를 반영하여 곱한 값을 합산)
위 처럼 문자열 키를 해싱하는 방법을 호너의 방법을 통해 조금더 간단하게 변환 가능합니다.
호너의 방법은 n차 다항식을 n회의 곱셈과 n회의 덧셈으로 해결하는 방법으로
ax^4 + bx^3 + cx^2 + dx^1 + e = (((ax + b)x + c)x + d)x + e 로 정의됩니다.
이 방법을 통해 계산량을 조금 더 줄일 수 있습니다.
충돌해소방법
해쉬테이블 내에 매핑하는 과정에서 충돌이 발생한 경우, 이를 해소하는 방법이 크게 두가지가 있습니다.
먼저 개방주소법입니다. 개방주소법은 충돌이 발생했을 때, 비어있는 다른 위치에 자료를 저장하는 방법입니다.
개방주소법 안에서도 선형조사법, 이차조사법, 이중해싱법으로 방법이 나뉩니다.
그 중 선형조사법 먼저 설명드리겠습니다.
선형조사법은 다음 예시처럼 충돌발생 시, 순차적으로 빈 공간을 찾습니다.
EX) h(K), h(K + 1) % M, h(K + 2) % M .... (h()는 해쉬함수, K는 키 값, M은 해쉬테이블 사이즈를 의미합니다.)
다음으로 이차조사법은 선형조사법에서 더해지는 값에 제곱을 취합니다.
EX) h(K), h(K + 1^2) % M, h(K + 2^2) % M .....
마지막으로 이중해싱법은 서로 다른 두 개의 해쉬함수를 사용하는 방법입니다.
EX) h1(K), (h1(K) + 1 * h2(K)) % M, (h1(K) + 2 * h2(K)) % M .....
선형조사법 다음 방법으로는 체인법이 있습니다.
체인법은 해쉬테이블 내 동일 인덱스 위치에 충돌이 발생한 여러 자료들을 연결리스트와 같은 구조로 유지하는 방법입니다. 따라서, 충돌이 발생했을 때, 동일 인덱스에 연결리스트로 이어줍니다.
위 처럼 충돌해소방법을 사용하기 때문에 최악의 경우 O(N)이 소요됩니다.
해쉬테이블의 구현
해쉬테이블의 구현은 대표적으로 선형조사법과 체인법을 활용하여 구현해보았습니다.
먼저 선형조사법을 사용한 해쉬테이블의 삽입입니다.
위에서 설명한 대로, 충돌이 발생 시, 다음 공간으로 이동해 빈 공간을 찾습니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
typedef struct Node {
int key;
} Node;
Node** ht; //Node* 를 담아야하므로 이중 포인터 사용
int HASH_TABLE_SIZE;
int hash(int key) {
return key % HASH_TABLE_SIZE;
}
int add(int key) {
int i = hash(key);
int startIdx = i; //추후 i가 다시 이 값을 만나면 해쉬테이블 모두를 검사했는데 빈공간이 없는 경우.
while(ht[i] != nullptr) { //빈 공간을 찾을 때 까지 반복
if(ht[i]->key == key) { //같은 키값을 가진 게 있음.
cout << "중복 키";
return 0;
}
i = (i + 1) % HASH_TABLE_SIZE; //선형조사법 수행
if(i == startIdx) { //위에서 설명한 포화상태
cout << "해쉬 테이블이 가득 찼습니다.";
return 0;
}
}
Node* x = (Node*)malloc(sizeof(Node)); //while문 탈출 = 빈 공간을 찾음.
x->key = key;
ht[i] = x;
return 1;
}
void create_ht(int size) { //해쉬테이블의 생성.
HASH_TABLE_SIZE = size;
ht = (Node**)malloc(sizeof(Node*) * size);
for(int i = 0; i < HASH_TABLE_SIZE; i++)
ht[i] = nullptr;
}
|
cs |
다음은 선형조사법을 사용한 해쉬테이블의 탐색입니다.
삽입과 비슷하게 구현되며, 삽입에서 키 중복되는 조건이 탐색에서는 키의 발견이 됩니다.
삽입에서 해쉬테이블의 포화 조건은 탐색에서 키의 부재로 정의됩니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
typedef struct Node {
int key;
} Node;
Node** ht;
int HASH_TABLE_SIZE;
int hash(int key) {
return key % HASH_TABLE_SIZE;
}
int search(int key) {
int i = hash(key);
int startIdx = i;
while(ht[i] != nullptr) { //현재 인덱스에 키값이 있다면 반
if(ht[i]->key == key) return 1; //키 발견
i = (i + 1) % HASH_TABLE_SIZE; //선형조사법
if(i == startIdx) return 0; //키 부재
}
return 0;
void create_ht(int size) {
HASH_TABLE_SIZE = size;
ht = (Node**)malloc(sizeof(Node*) * size);
for(int i = 0; i < HASH_TABLE_SIZE; i++)
ht[i] = nullptr;
}
|
cs |
다음으로 체인법을 사용한 해쉬테이블의 삽입입니다.
선형조사법과는 다르게 해쉬함수를 통해 인덱스값을 얻은 후, 해당 인덱스 위치의 연결리스트에서 키 값이 있는지 탐색합니다. 그리고, 키 값이 있다면 중복으로 삽입을 수행하지 않고, 키 값이 없다면 연결리스트 끝 위치에 삽입합니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
typedef struct Node {
int key;
struct Node* next; //연결리스트로 구현하므로, 다음 위치를 가지는 포인터 추가
} Node;
Node** ht;
int HASH_TABLE_SIZE;
int hash(int key) {
return key % HASH_TABLE_SIZE;
}
int add(int key) {
int i = hash(key);
Node* prev, *p; //탐색 및 삽입을 위한 이전 위치 포인터와 현재 위치 포인터
for(prev = nullptr; p = ht[i]; p!= nullptr; prev = p, p = p->next) { //prev는 p보다 이전에서 시작해야하므로 nullptr, p는 ht[i]. 즉 첫위치 부터 시작하여 p가 nullptr이 아니라면 prev를 p로 바꾸고 p는 p의 next로 바꿉니다. 따라서 현재 인덱스 연결리스트의 끝 위치 까지 탐색
if(p->key == key) return 0; //키 중복
}
Node* x = (Node*)malloc(sizeof(Node)); //키 삽입
x->key = key;
x->next = nullptr;
if(prev == nullptr) ht[i] = x; //해당 인덱스에 키가 하나도 없다면, 첫 위치가 됨.
else prev->next = x; //아니라면, 연결리스트의 끝에 삽입이므로 이전 노드가 현재 새로 삽입되는 노드를 가리키게함.
return 1;
}
void create_ht(int size) {
HASH_TABLE_SIZE = size;
ht = (Node**)malloc(sizeof(Node*) * size);
for(int i = 0; i < HASH_TABLE_SIZE; i++)
ht[i] = nullptr;
}
|
cs |
마지막으로 체인법을 사용한 해쉬테이블의 탐색입니다.
이 경우, 입력받은 키값의 인덱스 위치의 끝까지 탐색하며 해당하는 키가 있는지 확인하면 됩니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
typedef struct Node {
int key;
struct Node* next;
} Node;
Node** ht;
int HASH_TABLE_SIZE;
int hash(int key) {
return key % HASH_TABLE_SIZE;
}
int search(int key) {
int i = hash(key);
for(Node* p = ht[i]; p != nullptr; p = p->next) { //해당 인덱스의 연결리스트 끝까지 탐색.
if(p->key == key) return 1; //키 발견.
}
return 0; //키 부재
void create_ht(int size) {
HASH_TABLE_SIZE = size;
ht = (Node**)malloc(sizeof(Node*) * size);
for(int i = 0; i < HASH_TABLE_SIZE; i++)
ht[i] = nullptr;
}
|
cs |
이렇게 자료구조에 대한 내용을 마치도록 하겠습니다.
다음 포스트 부터는 알고리즘과 관련된 내용 혹은 다른 내용으로 포스트하도록 하겠습니다.
'Computer Science > 자료구조' 카테고리의 다른 글
| 비선형 자료구조 (그래프) (0) | 2023.09.11 |
|---|---|
| 자료들의 비교 기반 정렬 (0) | 2023.09.08 |
| 우선순위 큐의 구현 (이진 힙) (1) | 2023.09.07 |
| 균형 탐색 트리 (AVL)에 대하여 (0) | 2023.09.05 |
| 이진 탐색 트리에 대하여 (0) | 2023.09.03 |