티스토리 뷰
주의 사항!
- 이 글은 제가 직접 공부하는 중에 작성되고 있습니다.
- 따라서 제가 이해하는 그대로의 내용이 포함됩니다.
- 따라서 이 글은 사실과는 다른 내용이 포함될 수 있습니다.
충돌 문제는 테이블의 핵심 주제라고 할 수 있습니다. 충돌 문제를 해결하는 것이 뭔가 특별할 것 같지만 사실 개념 자체는 간단합니다. 만약 충돌이 발생하면, 충돌이 발생한 그 자리를 대신해서 빈자리를 찾는 것입니다. 그리고 빈자리를 찾는 방법에 따라서 해결책이 구분됩니다.
충돌이 발생했을 때 그 해결방법으로 우선 '선형 조사법'과 '이차 조사법'에 대해 설명하겠습니다.
선형 조사법은 충돌이 발생했을 때 그 옆자리가 비어 있는지 확인하고 빈자리에 데이터를 저장하는 방법입니다. 해쉬 함수가 다음과 같이 정의되어 있고,
int HashFunc(int key)
{
return key % 7;
}테이블이 다음과 같이 배열의 형태로 정의되어 있다고 가정하겠습니다.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
이 테이블에 키가 9인 데이터를 저장하려고 하면 해쉬 함수를 거치면서 해쉬 값은 2가 됩니다. 그리고 현재 배열의 2번 요소가 비어 있으므로 해당 배열 요소에 데이터를 저장합니다.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 9 |
그리고 여기에 키가 2인 데이터를 저장하려고 하면 해쉬 값은 2가 됩니다. 그런데 현재 2번 요소는 다른 데이터가 있으므로 그 옆으로 옮겨서 3번 요소가 비어 있는지 확인하고 데이터를 저장하게 됩니다.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 9 | 2 |
이처럼 충돌이 발생하면 다음과 같이 다음 칸, 또 다음 칸으로 옮겨서 데이터를 저장하는 방법을 선형 조사법이라고 합니다.
그런데 눈치챘겠지만 선형 조사법의 경우에는 데이터가 특정 영역에 몰릴 위험이 높습니다. 이런 현상을 '클러스터 현상'이라고 합니다. 그리고 이런 클러스터 현상은 충돌의 발생 확률을 증가시키는 직접적인 원인이 됩니다.
선형 조사법의 문제를 보완하고자 탄생한 것이 '이차 조사법'입니다. 선형 조사법이 충돌이 발생한 경우 바로 옆에 데이터를 저장해서 클러스터 현상을 일으켰다면, 이차 조사법은 바로 옆이 아닌, 멀찍이 떨어진 위치에 데이터를 저장하게 하면서 클러스터 현상의 발생 위험을 줄입니다.
이차 조사법의 조사 순서는 다음과 같이 됩니다.
물론 이차 조사법에도 문제는 존재합니다. 이는 잠시 후 '이중 해쉬'를 소개하면서 언급하게 됩니다.
이번에는 슬롯의 상태 정보를 별도로 관리해야 하는 이유에 대해서 설명하겠습니다. 앞서 우리는 슬롯의 상태 정보를 나타내는 것으로 다음 세 가지를 사용했습니다.
- EMPTY
- INUSE
- DELETED
그리고 DELETED의 존재 이유에 대해 궁금증을 가졌습니다. 이는 데이터의 탐색과정과 연관이 있습니다. 앞서 예로 들었던 테이블을 다시 가져오겠습니다.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 9 | 2 | ||||||||
| E | E | I | I | E | E | E | E | E | E |
이 테이블은 배열로 구현되었으며, 선형 조사법을 사용하고 있습니다. 위 테이블에서 3행의 알파벳은 각각 EMPTY(E), INUSE(I), DELETED(D)를 의미합니다. 그리고 해쉬 함수는 다음과 같습니다.
int HashFunc(int key)
{
return key % 7;
}위의 테이블에서 키가 9인 데이터를 삭제해 보겠습니다. 해쉬 함수를 거치면 해쉬 값은 2가 되므로 위 배열의 2번 요소를 조사하게 됩니다. 그리고 2번 요소에 키가 9인 데이터가 존재하므로 이 데이터를 삭제합니다. 그리고 여기서 2번 배열 요소(슬롯)의 상태 정보를 DELETED가 아닌 EMPTY로 바꿔보겠습니다.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 2 | |||||||||
| E | E | E | I | E | E | E | E | E | E |
문제는 이 상태에서 키가 2인 데이터를 삭제할 때 발생합니다. 키가 2인 데이터의 해쉬 값은 2입니다. 그런데 위 배열의 2번 요소를 보면 상태 정보가 EMPTY입니다. 이 상태 정보를 확인하면 키가 2인 데이터는 존재하지 않는다고 판단합니다. 바로 옆에 2가 저장되어 있지만 이를 조사하지는 않습니다. 하지만 EMPTY가 아닌 DELETED를 사용하면 이를 방지할 수 있습니다. 다시 다음과 같이 EMPTY가 아닌 DELETED로 상태 정보를 표시했을 경우에 2를 삭제해 보겠습니다.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 2 | |||||||||
| E | E | D | I | E | E | E | E | E | E |
키가 2인 데이터는 해쉬 값이 2이므로 위 배열의 2번 요소를 확인합니다. 그런데 2번 요소의 상태 정보가 DELETED입니다. 이는 '원래 이 자리에 다른 데이터가 저장되어 있었고, 해당 데이터로 인해서 충돌이 일어난 다른 데이터가 선형 조사법에 의해 그 옆에 저장되어 있을 수 있다. 즉, 쉽게 말해서, 똑같이 해쉬 값 2를 가지는 데이터가 이 옆에 있을 수 있다'는 의미를 가집니다. 그래서 프로그램은 다음 조사하는 슬롯의 상태 정보가 EMPTY일 때까지 그 옆의 슬롯을 조사하게 되고, 2를 발견하여 해당 데이터를 삭제할 수 있게 됩니다.
이제 '이중 해쉬'에 대해 설명합니다. 앞서 선형 조사법의 문제를 보완하기 위해 이차 조사법이 탄생했다고 했습니다. 하지만 이차 조사법이라고 해서 문제가 완전히 해결된 것은 아닙니다. 이차 조사법은 충돌이 발생할 경우, 선형 조사법과는 다르게 멀찍이서 빈자리를 찾기는 하지만 빈자리를 찾는 위치는 해쉬 값이 같을 경우 동일하기 때문입니다.
만약 해쉬 값이 1인데 충돌이 일어난다면, 그 다음 위치로는 2, 그리고 5, 10, 17번 슬롯을 조사하는 것은 동일합니다. 따라서 선형 조사법보다는 낮지만 접근이 진행되는 슬롯을 중심으로 클러스터 현상이 발생할 확률은 여전히 높을 수밖에 없습니다. 이를 해결하기 위해 등장한 것이 '이중 해쉬'입니다.
선형 조사법이나 이차 조사법이나 클러스터 현상이 문제가 된 이유는 다음 빈자리를 찾는 과정이 동일하기 때문입니다. 이는 마치 물수제비를 하는데, 돌을 몇 번이고 던져도 처음 돌이 튕긴 지점이 같으면 그 이후에 튕기는 지점들도 모두 같게 나오는 것과 같습니다.
여기서 우리는 문제의 핵심을 눈치챌 수 있습니다. 물수제비를 할 때, 똑같은 지점에서 돌이 처음 튕겨도 돌의 모양새에 따라서 그 이후에 튕기는 지점은 달라지게 하면 클러스터 발생 확률을 크게 줄일 수 있을 것만 같습니다. 이중 해쉬는 말 그대로 두 개의 해쉬 함수를 사용하기 때문에 붙여진 이름입니다. 하나의 해쉬 함수는 처음 돌이 튕길 지점을 반환하고, 다른 하나의 해쉬 함수는 돌이 튕겨나갈 거리를 반환합니다.
- 1차 해쉬 함수 키를 근거로 저장 위치를 결정하기 위한 것
- 2차 해쉬 함수 충돌 발생 시, 키를 근거로 몇 칸 뒤를 살필지 결정하기 위한 것
확실한 이해를 위해 이중 해쉬의 두 해쉬 함수를 정의해 보겠습니다. 먼저, 배열을 저장소로 하는 테이블이 존재한다고 가정하겠습니다. 다음은 1차 해쉬 함수입니다.
int firstHashFunc(int key)
{
return key % 10;
}위의 함수는 총 10개의 해쉬 값을 반환합니다. 따라서 배열의 크기가 10일 것임을 예상할 수 있습니다. 그리고 다음은 2차 해쉬 함수입니다.
int secondHashFunc(int key)
{
return 1 + (key % c); //c는 10이하의 소수
}위 함수에서 반환 값에 1을 더하는 이유는 반환 값이 0이 나오는 것을 방지하기 위함입니다. 그리고 c는 상수이며, 10 이하의 소수를 선택합니다. c가 10 이하인 이유는 배열의 크기가 10이므로 이보다는 작은 값이 나오게 하기 위함이며, 소수를 선택하는 이유는 통계적으로 소수를 선택했을 때 클러스터 발생 확률이 크게 줄일 수 있기 때문입니다.
c 값으로 7을 선택하면 다음과 같이 정의할 수 있습니다.
int secondHashFunc(int key)
{
return 1 + (key % 7);
}이번에 소개할 '체이닝'이라는 것은 앞서 소개한 충돌 해결책과는 해결 방식이 근본적으로 다릅니다. 앞서 소개한 유형들을 가리켜 '열린 어드레싱 방법'이라고 합니다. 이런 유형은 충돌이 발생하면 다른 자리에 대신 저장하는 식의 해결 방식을 가지고 있습니다. 반면 이번에 소개하는 체이닝과 같은 유형을 가리켜 '닫힌 어드레싱 방법'이라고 부르며, 이들은 충돌이 일어나도 자기 자리에 저장하는 식의 해결 방식을 가지고 있습니다.
충돌이 일어나도 자기 자리에 데이터를 저장하겠다니, 그럼 기존의 데이터는 어떻게 되는 것인지 궁금할 것입니다. 기존의 데이터도 그 자리에 존재합니다. 즉, 한 자리에 다수의 데이터가 존재할 수 있는 것입니다. 이는 간단하게는 2차원 배열을 통해서 구현할 수 있습니다.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 11 | 33 | 24 | 15 | 67 | |||||
| 13 | 87 | ||||||||
| 97 |
위와 같이 2차원 배열로 테이블을 구성하면 7번 슬롯과 같이 같은 자리에 다수의 데이터를 저장할 수 있습니다. 다만 2차원 배열을 이용하는 방법은 메모리 공간의 낭비가 심하다는 단점을 가지고 있습니다. 그래서 연결 리스트를 활용하는 방법을 사용하는 것이 '체이닝'입니다.
위 그림에서 보다시피 충돌이 발생하면 슬롯을 생성해서 연결 리스트의 모델로 연결해 나가는 방식으로 충돌 문제를 해결하고 있습니다. 따라서 체이닝 방법을 적용하면 하나의 해쉬 값에 다수의 슬롯을 둘 수 있습니다. 다만, 탐색을 위해서는 동일한 해쉬 값으로 묶여 있는 연결된 슬롯을 모두 조사해야 한다는 불편이 따릅니다. 하지만 해쉬 함수를 잘 정의하여 충돌의 확률을 줄일 수 있다면 연결된 슬롯의 길이는 부담스러운 정도는 아닐 것입니다.
이제 체이닝을 구현해 보겠습니다. 다만, 앞서 구현했던 테이블을 확장하는 형태로 구현합니다. 따라서 다음의 파일들을 사용할 것입니다.
- Person.h
- Person.c
- Slot.h
- Table.h
- Table.c
그리고 동일한 해쉬 값의 슬롯을 연결 리스트로 연결하기 위해서, 이전에 구현한 연결 리스트를 활용하기로 합니다. 여기서 우리가 활용할 연결 리스트 파일은 다음과 같습니다.
//LinkedList.h 헤더 파일로 저장
//수정 날짜 : 2021.03.25
//작성자 : KOEY
#ifndef LINKED_LIST_H
#define LINKED_LIST_H
#define TRUE 1
#define FALSE 0
typedef int Data;
typedef struct Node
{
Data data;
struct Node* next;
} Node;
typedef struct LinkedList
{
Node* head;
Node* cur;
Node* before;
int numOfData;
}LinkedList;
typedef LinkedList List;
void ListInit(List* plist);
void LInsert(List* plist, Data data);
int LFirst(List* plist, Data* pdata);
int LNext(List* plist, Data* pdata);
Data LRemove(List* plist);
int LCount(List* plist);
#endif//LinckedList.c 소스 파일로 저장
//수정 날짜 : 2021.03.25
//작성자 : KOEY
#include "LinkedList.h"
#include <stdlib.h>
#include <stdio.h>
void ListInit(List* plist)
{
plist->head = NULL;
plist->numOfData = 0;
}
void LInsert(List* plist, Data data)
{
Node* newNode = (Node*)malloc(sizeof(Node));
if (newNode == NULL)
{
printf("메모리 공간이 부족합니다.");
exit(1);
}
newNode->data = data;
if (plist->head == NULL)
{
newNode->next = NULL;
}
else
{
newNode->next = plist->head;
}
plist->head = newNode;
plist->numOfData++;
}
int LFirst(List* plist, Data* pdata)
{
plist->cur = plist->head;
plist->before = NULL;
if (plist->cur == NULL)
{
return FALSE;
}
*pdata = plist->cur->data;
return TRUE;
}
int LNext(List* plist, Data* pdata)
{
plist->before = plist->cur;
plist->cur = plist->cur->next;
if (plist->cur == NULL)
{
return NULL;
}
*pdata = plist->cur->data;
return TRUE;
}
Data LRemove(List* plist)
{
Node* delNode = plist->cur;
Data delData = delNode->data;
plist->cur = plist->before;
if (delNode == plist->head)
{
plist->head = delNode->next;
}
else
{
plist->before->next = delNode->next;
}
free(delNode);
plist->numOfData--;
return delData;
}
int LCount(List* plist)
{
return plist->numOfData;
}
먼저 Slot.h 파일을 변경하겠습니다. 변경된 Slot.h 파일은 다음과 같습니다.
//Slot.h 헤더 파일로 저장
//수정 날짜 : 2021.03.25
//작성자 : KOEY
#ifndef SLOT_H
#define SLOT_H
#include "Person.h"
typedef int Key; //주민등록번호를 키로 사용
typedef Person* Value; //Person 구조체 변수의 주소를 값으로 사용
typedef struct Slot
{
Key key;
Value val;
} Slot;
#endif슬롯의 상태 정보를 표현하는 enum 선언이 사라졌습니다. 왜냐하면 체이닝 같은 닫힌 어드레싱 방법에서는 상태 정보가 필요 없기 때문입니다. 다음으로 Table.h 파일을 소개합니다.
//Table.h 헤더 파일로 저장
//수정 날짜 : 2021.03.25
//작성자 : KOEY
#ifndef TABLE_H
#define TABLE_H
#include "Slot.h"
#include "LinkedList.h"
#define MAX_TBL 100
typedef int(*HashFunc)(Key key);
typedef struct Table
{
List tbl[MAX_TBL];
HashFunc hashFunc;
} Table;
void TBLInit(Table* ptbl, HashFunc func);
void TBLInsert(Table* ptbl, Key key, Value val);
Value TBLDelete(Table* ptbl, Key key);
Value TBLSearch(Table* ptbl, Key key);
#endif변경점은 다음과 같습니다.
typedef struct Table
{
List tbl[MAX_TBL];
HashFunc hashFunc;
} Table;Table 구조체가 Slot 대신 List를 멤버로 가집니다. 그리고 이를 위해서 연결 리스트 헤더 파일을 인클루드 했습니다. 여기까지는 쉬운 과정입니다. 지금부터는 연결 리스트와 슬롯의 관계를 고민해야 합니다.
- 슬롯을 연결 리스트의 노드로서 사용한다.
- 연결 리스트와 슬롯을 엄연히 구분하여 노드에 슬롯의 주소를 저장한다.
- 슬롯을 연결 리스트 노드의 멤버로서 사용한다.
첫 번째 방법은 리스트 자료구조와 관련된 코드를 직접 새로 작성하는 경우에 생각해 볼 수 있습니다. 하지만 두 번째나 세 번째 방법을 선택하면 연결 리스트 관련 코드와 테이블 관련 코드의 구분이 용이하기 때문에 이 방법을 더 추천합니다.
우선은 세 번째 방법으로 체이닝을 구현해 보겠습니다. 이를 위해서는 연결 리스트 헤더 파일을 열어서 typedef 선언을 다음과 같이 수정해야 합니다.
//LinkedList.h 헤더 파일로 저장
//수정 날짜 : 2021.03.25
//작성자 : KOEY
#ifndef LINKED_LIST_H
#define LINKED_LIST_H
#include "Slot.h" //Slot 파일 인클루드
#define TRUE 1
#define FALSE 0
typedef Slot Data; //변경된 typedef 선언문
typedef struct Node
{
Data data;
struct Node* next;
} Node;
typedef struct LinkedList
{
Node* head;
Node* cur;
Node* before;
int numOfData;
}LinkedList;
typedef LinkedList List;
void ListInit(List* plist);
void LInsert(List* plist, Data data);
int LFirst(List* plist, Data* pdata);
int LNext(List* plist, Data* pdata);
Data LRemove(List* plist);
int LCount(List* plist);
#endif이제 남은 것은 Table.c 파일의 함수 구현입니다. 연결 리스트의 활용 방법만 제대로 이해하고 있다면 함수의 구현도 직접 할 수 있습니다.
//Table.c 소스 파일로 저장
//수정 날짜 : 2021.03.25
//작성자 : KOEY
#include "Table.h"
#include <stdlib.h>
#include <stdio.h>
void TBLInit(Table* ptbl, HashFunc func)
{
int i;
for (i = 0; i < MAX_TBL; i++)
{
ListInit(&(ptbl->tbl[i]));
}
ptbl->hashFunc = func;
}
void TBLInsert(Table* ptbl, Key key, Value val)
{
if (TBLSearch(ptbl, key) != NULL)
{
printf("키 중복 오류 발생 \n");
return;
}
int hashVal = ptbl->hashFunc(key);
List* plist = &(ptbl->tbl[hashVal]);
Slot slot = { key, val };
LInsert(plist, slot);
}
Value TBLDelete(Table* ptbl, Key key)
{
int hashVal = ptbl->hashFunc(key);
List* plist = &(ptbl->tbl[hashVal]);
Slot slot;
if (LFirst(plist, &slot))
{
if (slot.key == key)
{
return LRemove(plist).val;
}
while (LNext(plist, &slot))
{
if (slot.key == key)
{
return LRemove(plist).val;
}
}
}
}
Value TBLSearch(Table* ptbl, Key key)
{
int hashVal = ptbl->hashFunc(key);
List* plist = &(ptbl->tbl[hashVal]);
Slot slot;
if (LFirst(plist, &slot))
{
if (slot.key == key)
{
return slot.val;
}
while (LNext(plist, &slot))
{
if (slot.key == key)
{
return slot.val;
}
}
}
return NULL;
}
이제 마지막으로 main 함수를 정의하고, 그 실행결과를 확인하겠습니다.
//main.c 소스 파일로 저장
#include <stdio.h>
#include <stdlib.h>
#include "Table.h"
#include "Person.h"
int MyHashFunc(int key)
{
return key % 100;
}
int main(void)
{
Table myTbl;
TBLInit(&myTbl, MyHashFunc);
Person* newPerson; //새로 생성한 Person 구조체 변수의 주소를 저장할 변수
Person* searchPerson; //탐색된 Person 구조체 변수의 주소를 저장할 변수
Person* removePerson; //삭제할 Person 구조체 변수의 주소를 저장할 변수
//데이터 생성
newPerson = MakePersonData(900254, "Lee", "Seoul");
TBLInsert(&myTbl, GetSSN(newPerson), newPerson);
newPerson = MakePersonData(900139, "Kim", "Jeju");
TBLInsert(&myTbl, GetSSN(newPerson), newPerson);
newPerson = MakePersonData(900339, "Han", "Busan");
TBLInsert(&myTbl, GetSSN(newPerson), newPerson);
newPerson = MakePersonData(900339, "Han", "Busan");
TBLInsert(&myTbl, GetSSN(newPerson), newPerson);
//데이터 탐색
searchPerson = TBLSearch(&myTbl, 900254);
if (searchPerson != NULL)
{
ShowPerInfo(searchPerson);
}
searchPerson = TBLSearch(&myTbl, 900139);
if (searchPerson != NULL)
{
ShowPerInfo(searchPerson);
}
searchPerson = TBLSearch(&myTbl, 900339);
if (searchPerson != NULL)
{
ShowPerInfo(searchPerson);
}
//데이터 삭제
removePerson = TBLDelete(&myTbl, 900254);
if (removePerson != NULL)
{
free(removePerson);
}
removePerson = TBLDelete(&myTbl, 900139);
if (removePerson != NULL)
{
free(removePerson);
}
removePerson = TBLDelete(&myTbl, 900339);
if (removePerson != NULL)
{
free(removePerson);
}
return 0;
}
/*
실행결과
키 중복 오류 발생
주민등록번호 : 900254
이름 : Lee
주소 : Seoul
주민등록번호 : 900139
이름 : Kim
주소 : Jeju
주민등록번호 : 900339
이름 : Han
주소 : Busan
*/실행결과를 보면 똑같은 키의 중복 저장을 막고 있고, 충돌 문제도 잘 해결하고 있음을 확인할 수 있습니다.
'공부 일지 > 자료구조 공부 일지' 카테고리의 다른 글
| Chapter 14. 인접 리스트 기반의 그래프 구현 (0) | 2021.03.27 |
|---|---|
| Chapter 14. 그래프의 이해와 종류 (0) | 2021.03.27 |
| Chapter 13. 빠른 탐색을 보이는 해쉬 테이블 (0) | 2021.03.25 |
| Chapter 12. 균형 잡힌 이진 탐색 트리 : AVL 트리의 구현 (0) | 2021.03.23 |
| Chapter 12. 균형 잡힌 이진 탐색 트리: AVL 트리의 이해 (0) | 2021.03.23 |