티스토리 뷰
주의 사항!
- 이 글은 제가 직접 공부하는 중에 작성되고 있습니다.
- 따라서 제가 이해하는 그대로의 내용이 포함됩니다.
- 따라서 이 글은 사실과는 다른 내용이 포함될 수 있습니다.
앞서 소개한 AVL 트리는 탐색과 관련하여 매우 만족스러운 성능을 보였습니다. 하지만 탐색 키의 비교 과정을 거치면서 찾는 대사에 가까워지는 방식이기 때문에, 원하는 바를 '단번에' 찾아내는 방식이라고 말하기는 어렵습니다. 때문에 상황에 따라서는 이러한 AVL 트리의 성능에 만족하지 못할 수도 있습니다. 그리고 이러한 상황에서 도입을 검토할 수 있는 자료구조가 바로 '테이블'입니다.
테이블도 자료구조인데 찾고자 하는 데이터를 '단번에' 찾을 수 있다니 믿기 어려우실 겁니다. 물론 테이블이라고 해서 정말로 찾고자 하는 데이터를 단번에 찾아내지는 못합니다. 그럼에도 그렇게 말할 수 있는 이유는 테이블의 시간 복잡도의 빅-오가 다음과 같기 때문입니다.
테이블이 어떻게 위와 같은 시간 복잡도를 가질 수 있는지 앞으로 설명하겠습니다. 우선 테이블 자료구조를 먼저 소개합니다.
| 사번 : Key | 직원 : Value |
| 99001 | 이순신 부장 |
| 99002 | 유관순 차장 |
| 99003 | 박새로이 과장 |
| 99004 | 안중근 사원 |
위의 표를 테이블이라고 하는 것은 다들 알고 있을 것입니다. 하지만 자료구조의 관점에서는 모든 표를 테이블이라고 하지 않습니다. 표에 저장된 데이터의 형태가 다음과 같을 때에만 테이블로 구분 짓습니다.
- 저장되는 데이터는 키와 값이 하나씩 쌍을 이룬다.
- 모든 키는 중복되지 않는다.
테이블의 예로 '사전'을 들 수 있습니다. 그런데 사전은 표로 정리되어 있지도 않은데 사전을 테이블에 비유할 수 있다니 어리둥절할 수도 있습니다. 자료구조에서 테이블의 핵심은 키와 값이 서로 1 대 1 대응되고, 중복되는 키가 없는가입니다. 표가 그려져 있는지는 전혀 관심 없습니다. 그런 관점에서 봤을 때 사전의 단어는 키로 볼 수 있고, 단어를 설명하는 내용은 값으로 볼 수 있습니다. 그래서 사전을 테이블의 예로 들 수 있는 것입니다.
이러한 이유로 자료구조의 '테이블'은 '사전 구조'라고도 불립니다. 더불어 '맵'이라고 불리기도 합니다.
테이블의 이해를 돕기 위해 배열을 이용해서 매우 간단하게 구현한 테이블을 보이겠습니다.
//main.c 소스 파일로 저장
#include <stdio.h>
typedef struct EmpInfo
{
int empNum;
int age;
} EmpInfo;
int main(void)
{
EmpInfo empInfoArr[100];
EmpInfo ei;
int eNum;
printf("사번과 나이 입력 : ");
scanf("%d%d", &(ei.empNum), &(ei.age));
empInfoArr[ei.empNum] = ei;
printf("확인하고픈 직원의 사번 입력 : ");
scanf("%d", &eNum);
ei = empInfoArr[eNum]; //단번에 탐색
printf("사번 %d, 나이 %d\n", ei.empNum, ei.age);
return 0;
}
/*
실행결과
사번과 나이 입력 : 59 24
확인하고픈 직원의 사번 입력 : 59
사번 59, 나이 24
*/위의 코드에서 다음과 같은 구조체는,
typedef struct EmpInfo
{
int empNum;
int age;
} EmpInfo;직원의 번호와 나이를 한 쌍으로 저장합니다. 여기서 직원의 번호를 키로 사용하고, 값은 나이가 됩니다. 그리고 main 함수에 이 구조체를 저장할 수 있는 배열을 선언했습니다.
EmpInfo empInfoArr[100];그런데 이런 배열만 가지고는 테이블이라고 할 수 없습니다. 왜냐하면 테이블이라고 부를 수 있으려면 키를 이용해서 찾고자 하는 데이터를 단번에 찾을 수 있어야 하기 때문입니다. 배열이 선언되어 있어도 어디에 어떤 데이터가 저장되어 있는지를 알지 못하므로 아직은 테이블이라고 할 수 없습니다.
그런데 다행히도 우리는 다음과 같이 직원의 번호(키)와 같은 인덱스에 데이터를 저장합니다.
empInfoArr[ei.empNum] = ei;이로써 배열의 인덱스가 곧 키가 되고, 그렇게 되면 키를 이용해 해당 인덱스에 접근하여 바로 데이터를 찾을 수 있기 때문에 이로써 위 배열은 비로소 테이블이라고 할 수 있게 되었습니다. 그런데 이렇게 배열로 구현한 테이블은 다음과 같은 한계를 가집니다.
"사번의 범위가 100000 ~ 999999이라면, 배열의 크기가 매우 커져야 한다."
이러한 문제점은 테이블의 핵심인 '해쉬'와 관련된 내용이 빠졌기 때문에 발생합니다.
위 예제에서 배열을 이용해 구현해 본 테이블의 문제점을 다음과 같이 정리할 수 있을 것 같습니다.
"직원 고유번호의 범위가 배열의 인덱스 값으로 사용하기에 적당하지 않다."
"직원 고유번호의 범위를 수용할 수 있는 매우 큰 배열이 필요하다"
이 두 가지 문제를 동시에 해결해주는 것이 바로 '해쉬 함수'입니다. 그럼 해쉬 함수의 소개를 위해서 앞서 보인 예제를 다시 보이겠습니다. 단, 이번에는 직원의 고유 번호를 입사 연도 4자리와 해당 연도 입사 순서 4자리로 구성하겠습니다.
예를 들어서 2012년에 네 번째로 입사한 직원의 고유번호는 20120004가 됩니다.
//main.c 소스 파일로 저장
#include <stdio.h>
typedef struct EmpInfo
{
int empNum;
int age;
} EmpInfo;
int GetHashValue(int empNum)
{
return empNum % 100;
}
int main(void)
{
EmpInfo empInfoArr[100];
EmpInfo emp1 = { 20120003, 42 };
EmpInfo emp2 = { 20130012, 33 };
EmpInfo emp3 = { 20170049, 27 };
EmpInfo r1, r2, r3;
empInfoArr[GetHashValue(emp1.empNum)] = emp1;
empInfoArr[GetHashValue(emp2.empNum)] = emp2;
empInfoArr[GetHashValue(emp3.empNum)] = emp3;
r1 = empInfoArr[GetHashValue(20120003)];
r2 = empInfoArr[GetHashValue(20130012)];
r3 = empInfoArr[GetHashValue(20170049)];
printf("사번 %d, 나이 %d\n", r1.empNum, r1.age);
printf("사번 %d, 나이 %d\n", r2.empNum, r2.age);
printf("사번 %d, 나이 %d\n", r3.empNum, r3.age);
return 0;
}
/*
실행결과
사번 20120003, 나이 42
사번 20130012, 나이 33
사번 20170049, 나이 27
*/위 예제를 보면 empInfoArr 배열에 EmpInfo 구조체 변수를 저장할 때, 직원의 고유번호를 이용하되 GetHashValue 함수를 거쳐 가공된 고유번호를 사용하고 있습니다. GetHashValue 함수를 보면 총 8자리의 고유번호를 2자리의 번호로 바꿔주고 있습니다. 바로 이런 함수를 해쉬 함수라고 합니다.
해쉬 함수는 큰 범위의 키를 좁은 범위의 키로 변경하는 역할을 합니다. 그런데 이미 눈치챘겠지만, 위 예제에서 보인 GetHashValue 함수는 문제점을 가지고 있습니다. 바로 직원의 고유번호의 뒤 두 자리가 같을 경우 해쉬 함수를 거쳐 가공된 번호도 같게 된다는 것입니다. 예를 들어 고유번호가 20080012인 직원과, 20120012인 직원은 해쉬 함수를 거쳐 가공되면 12로 같은 번호를 갖게 됩니다. 이러한 상황을 가리켜 '충돌'이라고 합니다.
테이블에서 '충돌'상황은 피하려야 피할 수 없는 상황입니다. 따라서 충돌을 해결하는 다양한 방법들이 사용되고 있으며, 이 충돌의 해결 방법에 따라 테이블의 구조가 달라지는 경우가 있을 정도로 충돌의 해결 방법은 테이블에 있어서 큰 의미를 갖습니다.
앞서 예제를 통해서 테이블과 해쉬 함수를 간단히 구현해 봤지만, 사실 테이블의 구현 사례로는 부족하기 때문에 어느 정도 모습을 갖춰서 다시 구현해 보고자 합니다. 먼저, 테이블에 저장할 대상에 대한 헤더 파일과 소스 파일을 소개합니다.
//Person.h 헤더 파일로 저장
//수정 날짜 : 2021.03.25
//작성자 : KOEY
#ifndef PERSON_H
#define PERSON_H
#define STR_LEN 50
typedef struct Person
{
int ssn; //주민등록번호
char name[STR_LEN]; //이름
char addr[STR_LEN]; //주소
} Person;
int GetSSN(Person* p); //주민등록번호 반환
void ShowPerInfo(Person* p); //Person 구조체 변수의 정보 출력
Person* MakePersonData(int ssn, char* name, char* addr); //Person 구조체 변수를 만들고 그 주소를 반환
#endif//Person.c 소스 파일로 저장
//수정 날짜 : 2021.03.25
//작성자 : KOEY
#include "Person.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int GetSSN(Person* p)
{
return p->ssn;
}
void ShowPerInfo(Person* p)
{
printf("주민등록번호 : %d\n", p->ssn);
printf("이름 : %s\n", p->name);
printf("주소 : %s\n\n", p->addr);
}
Person* MakePersonData(int ssn, char* name, char* addr)
{
Person* newP = (Person*)malloc(sizeof(Person));
if (newP == NULL)
{
printf("메모리 공간이 부족합니다. \n");
exit(1);
}
newP->ssn = ssn;
strcpy(newP->name, name);
strcpy(newP->addr, addr);
return newP;
}테이블에 저장할 것은 사람을 의미하는 Person 구조체 변수이며, 주민등록번호와 이름, 주소를 멤버로 가지고 있습니다. 이 중에서 주민등록번호는 key로 사용하게 됩니다.
이어서 테이블의 구현과 관련이 있는 파일을 소개하겠습니다. 지금 소개할 파일은 슬롯을 정의한 헤더 파일입니다. 슬롯은 테이블을 구성하는 칸 하나하나를 의미한다고 이해하면 되겠습니다.
//Slot.h 헤더 파일로 저장
//수정 날짜 : 2021.03.25
//작성자 : KOEY
#ifndef SLOT_H
#define SLOT_H
#include "Person.h"
typedef int Key; //주민등록번호를 키로 사용
typedef Person* Value; //Person 구조체 변수의 주소를 값으로 사용
typedef enum SlotStatus
{
EMPTY, DELETED, INUSE //EMPTY : 비어있음, DELETED : 삭제됨, INUSE : 유효한 데이터가 저장됨
} SlotStatus;
typedef struct Slot
{
Key key;
Value val;
SlotStatus status;
} Slot;
#endif슬롯은 키를 저장하고, Person 구조체 변수의 주소를 값으로 가집니다. 그리고 슬롯이 비어 있는지, 유효한 데이터가 있는지, 삭제됐는지를 의미하는 status도 멤버로 가집니다. INUSE는 유효한 데이터가 저장되었다는 의미이고, EMPTY는 슬롯이 비어 있다는 의미, DELETED는 삭제된 슬롯임을 의미합니다. 그런데 조금 생각해 보면, 삭제된 슬롯이면 그냥 EMPTY로 해도 될 거 같은데 왜 굳이 DELETED로 구분 짓는지 의아할 수 있습니다. 이 부분은 '충돌'의 해결책을 소개하면서 같이 소개하겠습니다.
다음은 테이블을 실질적인 구현에 해당하는 헤더 파일과 소스 파일입니다.
//Table.h 헤더 파일로 저장
//수정 날짜 : 2021.03.25
//작성자 : KOEY
#ifndef TABLE_H
#define TABLE_H
#include "Slot.h"
#define MAX_TBL 100
typedef int(*HashFunc)(Key k);
typedef struct Table
{
Slot slot[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//Table.c 소스 파일로 저장
//수정 날짜 : 2021.03.25
//작성자 : KOEY
#include "Table.h"
#include <stdlib.h>
void TBLInit(Table* ptbl, HashFunc func)
{
int i;
for (i = 0; i < MAX_TBL; i++)
{
ptbl->slot[i].status = EMPTY;
}
ptbl->hashFunc = func;
}
void TBLInsert(Table* ptbl, Key key, Value val)
{
int hashVal = ptbl->hashFunc(key);
ptbl->slot[hashVal].val = val;
ptbl->slot[hashVal].key = key;
ptbl->slot[hashVal].status = INUSE;
}
Value TBLDelete(Table* ptbl, Key key)
{
int hashVal = ptbl->hashFunc(key);
if (ptbl->slot[hashVal].status != INUSE)
{
return NULL;
}
else
{
ptbl->slot[hashVal].status = DELETED;
return ptbl->slot[hashVal].val;
}
}
Value TBLSearch(Table* ptbl, Key key)
{
int hashVal = ptbl->hashFunc(key);
if (ptbl->slot[hashVal].status != INUSE)
{
return NULL;
}
else
{
return ptbl->slot[hashVal].val;
}
}
위 파일들을 보면 직접 정의한 해쉬 함수를 등록할 수 있도록 디자인되었음을 알 수 있습니다. 이어서 위의 테이블을 대상으로 하는 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(20120003, "Lee", "Seoul");
TBLInsert(&myTbl, GetSSN(newPerson), newPerson);
newPerson = MakePersonData(20130012, "Kim", "Jeju");
TBLInsert(&myTbl, GetSSN(newPerson), newPerson);
newPerson = MakePersonData(20170049, "Han", "Busan");
TBLInsert(&myTbl, GetSSN(newPerson), newPerson);
//데이터 탐색
searchPerson = TBLSearch(&myTbl, 20120003);
if (searchPerson != NULL)
{
ShowPerInfo(searchPerson);
}
searchPerson = TBLSearch(&myTbl, 20130012);
if (searchPerson != NULL)
{
ShowPerInfo(searchPerson);
}
searchPerson = TBLSearch(&myTbl, 20170049);
if (searchPerson != NULL)
{
ShowPerInfo(searchPerson);
}
//데이터 삭제
removePerson = TBLDelete(&myTbl, 20120003);
if (removePerson != NULL)
{
free(removePerson);
}
removePerson = TBLDelete(&myTbl, 20130012);
if (removePerson != NULL)
{
free(removePerson);
}
removePerson = TBLDelete(&myTbl, 20170049);
if (removePerson != NULL)
{
free(removePerson);
}
return 0;
}
/*
실행결과
주민등록번호 : 20120003
이름 : Lee
주소 : Seoul
주민등록번호 : 20130012
이름 : Kim
주소 : Jeju
주민등록번호 : 20170049
이름 : Han
주소 : Busan
*/이로써 우리가 모델로 삼을 수 있는 테이블의 구현이 완료되었습니다. 잠시 후에는 이 예제에 충돌에 대한 해결책까지 담을 예정입니다.
해쉬 함수도 좋은 해쉬 함수와 나쁜 해쉬 함수로 나눌 수 있습니다. 좋은 해쉬 함수와 나쁜 해쉬 함수를 설명하기 전에 두 함수의 사용 결과부터 비교해 보겠습니다. 좋은 해쉬 함수를 사용하는 테이블은 메모리가 상황이 다음과 같게 됩니다.
위 그림에서 검은색 영역은 데이터가 저장된 슬롯을 의미하고, 흰 영역은 빈 슬롯을 의미합니다. 위 그림처럼 데이터가 테이블에 고루 분포된다는 것은 그만큼 '충돌'이 발생할 확률이 낮다는 것을 의미합니다. 충돌의 해결책이 마련되어 있다고 하더라도 충돌이 덜 발생해야 데이터의 저장, 삭제 및 탐색의 효율을 높일 수 있습니다. 때문에 좋은 해쉬 함수는 '충돌을 덜 일으키는 해쉬 함수'라고도 말할 수 있습니다.
반면 다음 그림은 나쁜 해쉬 함수의 사용 결과를 보여줍니다.
나쁜 해쉬 함수는 특정 영역에 데이터가 몰리게 합니다. 이렇게 되면 '충돌'이 발생할 확률이 높아집니다.
그럼 좋은 해쉬 함수가 되기 위한 조건은 무엇일까요? 좋은 해쉬 함수를 디자인하는 방법에는 정답이 없습니다. 왜냐하면 키의 특성에 따라서 달라지기 때문입니다. 하지만 일반적으로 다음의 사항을 고려해서 해쉬 함수를 정의하라고 조언합니다.
"좋은 해쉬 함수는 키의 일부분을 참조하여 해쉬 값을 만들지 않고, 키 전체를 참조하여 해쉬 값을 만들어 낸다."
위의 조언, 키 전체를 참조하는 방법과 관련하여 다양한 방법이 소개되고 있는데, 그중 하나는 다음과 같습니다.
"여덟 자리의 수로 이뤄진 키에서 다양한 해쉬 값 생성에 도움을 주는 네 자리의 수를 뽑아서 해쉬 값을 생성한다."
키의 특정 위치에서 중복의 비율이 높거나, 아예 공통으로 들어가는 값이 있다면, 이를 제외한 나머지를 가지고 해쉬 값을 생성하는 지극히 상식적인 방법입니다. 그리고 이와 유사한 방법으로 '비트 추출 방법'이라는 것이 있습니다. 이는 탐색 키의 비트 열에서 일부를 추출 및 조합하는 방법입니다.
이어서 '자릿수 폴딩'이라는 방법도 있습니다. 만약 다음과 같이 6자리의 숫자가 있다면,
273419
이를 두 자리씩 나누어 3 등분합니다.
27 34 19
그리고 이들을 모두 더하면 80이라는 숫자를 얻을 수 있습니다. 이를 해쉬 값이라고 하면 이는 여섯 자리의 숫자를 모두 반영하여 얻은 결과라고 할 수 있습니다. 이렇듯 폴딩은 종이를 접듯이 숫자를 겹치게 해서 더한 결과를 해쉬 값으로 결정하는 방법입니다.
이 외에도 통계적으로 넓은 분포를 보이는 다양한 방법들이 존재하지만, 해쉬 함수를 디자인할 때는 이러한 방법들보다 키의 특성과 저장 공간의 크기를 고려하는 것이 우선입니다.
'공부 일지 > 자료구조 공부 일지' 카테고리의 다른 글
| Chapter 14. 그래프의 이해와 종류 (0) | 2021.03.27 |
|---|---|
| Chapter 13. 충돌(Collision) 문제의 해결책 (0) | 2021.03.26 |
| Chapter 12. 균형 잡힌 이진 탐색 트리 : AVL 트리의 구현 (0) | 2021.03.23 |
| Chapter 12. 균형 잡힌 이진 탐색 트리: AVL 트리의 이해 (0) | 2021.03.23 |
| Chapter 11. 이진 탐색 트리 (2) (0) | 2021.03.22 |