(1) 테이블 자료구조의 이해
테이블 - 데이터가 key와 value로 한 쌍을 이루며, key가 데이터의 저장 및 탐색의 도구가 된다.
즉, 테이블 자료구조에서는 원하는 데이터를 단번에 찾을 수 있다.
(이 때 value는 Data이다. key는 중복되지 않고 value를 찾게 해주는 값이다.)
따라서 테이블 자료구조의 탐색 연산은 O(1)의 시간 복잡도를 보인다.
보통 key는 공식에 의해 결정되는데 찾고자 하는 데이터를 근거로 key를 구하여 데이터를 바로 찾을 수 있어야 한다.
즉, Data -> 공식 ->key, 이 key가 있으면 데이터를 바로 찾을 수 있다.
이것이 테이블 자료구조의 핵심이다.
이는 성능이 매우 좋으나 늘 쓸 수 있는 것은 아니다.
일단 메모리적인 단점이 있다. -> 강의 수강 전 예상하는 이유 : 1부터 데이터가 순차적으로 저장되는 것이 아닐 것!
(tip) 테이블은 사전구조 또는 맵 이라고도 불린다.
(2) 배열을 기반으로 하는 테이블
#include <stdio.h>
typedef struct empInfo//employee의 emp이다.
{
int empNum; //직원의 고유 번호 : key
int age; //직원의 나이 : value
} EmpInfo;
int main()
{
EmpInfo empInfoArray[1000];
EmpInfo ei;
int eNum;//데이터 탐색 시 사용
printf("사번과 나이 입력 : ");
scanf("%d %d", &(ei.empNum), &(ei.age));//일단 ei에 정보를 저장
empInfoArray[ei.empNum] = ei;//ei.empNum이 들어왔으므로 배열의 ei.empNum항에 데이터 저장
printf("확인하고픈 직원의 사번 입력 : ");
scanf("%d", &eNum);
ei = empInfoArray[eNum];//단번에 탐색!
printf("사번 : %d, 나이 : %d\n", ei.empNum, ei.age);//eNum울 통해 한번에 데이터를 조회 가능
return 0;
}일단 위에서 key와 value를 억지로 구분하지 않아도 된다는 교훈을 얻을 수 있다.
vlaue의 일부분 혹은 일부분을 조합하여 key를 만들어낼 수 있다는 것을 이 예제가 보여주고 있다.
배열을 기반으로 하는 테이블이 있으면 연결 리스트를 기반으로 하는 테이블도 있을까?
탐색을 한번에 하려면 배열을 사용해야 하므로, 테이블과 배열은 뗄레야 뗄 수 없다.
연결 리스트를 기반으로 구현을 할 수도 있으나 이마저도 배열을 바탕으로 구현한다.
(3) 테이블에 의미를 부여하는 해쉬 함수와 충돌문제
#include <stdio.h>
typedef struct
{
int EmpNum;
int EmpAge;
}EmpInfo;
int GetHashValue(int empNum)
{
return empNum % 100;
}//키값을 얻는 함수
int main(void)
{
EmpInfo empInfoArray[100];
EmpInfo emp1 = { 20120003,42 };//구조체 초기화 방법
EmpInfo emp2 = { 20130012,33 };
EmpInfo emp3 = { 20170049,27 };
EmpInfo r1, r2, r3;//셋 다 구조체
//키를 인덱스 값으로 이용해서 저장
empInfoArray[GetHashValue(emp1.EmpNum)] = emp1;
empInfoArray[GetHashValue(emp2.EmpNum)] = emp2;
empInfoArray[GetHashValue(emp3.EmpNum)] = emp3;
//키를인덱스 값으로 이용해서 탐색 -> 찾고자 하는 사람이 사원번호는 알고 있었다 가정
r1 = empInfoArray[GetHashValue(20120003)];
r2 = empInfoArray[GetHashValue(20130012)];
r3 = empInfoArray[GetHashValue(20170049)];
//팀색 결과 확인
printf("사번 %d, 나이 %d\n", r1.EmpNum, r1.EmpAge);
printf("사번 %d, 나이 %d\n", r2.EmpNum, r2.EmpAge);
printf("사번 %d, 나이 %d\n", r3.EmpNum, r3.EmpAge);
return 0;
}이 때 데이터를 이용하여 키값을 얻는 함수가 바로 해쉬 함수이다.
위의 코드를 자세히 보자.
사번이 여덟자리라고 해서 여덟자리의 칸을 가지는 배열을 선언하는 것은 엄청난 메모리 낭비이다.
그래서 어떠한 방법을 택했느냐.
20120093 등의 사번이 0 ~ 99까지중 하나의 수와 매칭이 되도록 하는 방법
즉, GetHastValue함수를 선언하여 사번을 100으로 나눈 나머지를 키로 삼도록 한다.
이 때 얻는 키값이 바로 해쉬값이다.
그러나 이도 완벽하지 않은 방법이다.
예를 들어 사번이 20210003과 20210103 인 사람은 모두 해쉬값이 3으로 해쉬값이 충돌한다.
이를 해결하는 것이 굉장히 중요한 문제이다.
(4) 어느 정도 갖춰진 해쉬 테이블의 예
typedef struct
{
int ssn; //주민등록번호 -> 강의에서는 이를 키로 사용, 이게 정답은 아니다.
char name[STR_LEN]; //이름
char addr[STR_LEN]; //주소
}Person;
int GetSSN(Person* p)//구조체의 주소를 받아옴
{
return p->ssn;//사람의 주민등록번호를 불러오는 함수, 해쉬 테이블관점에서 이는 키를 반환하는 함수
}
void ShowPerInfo(Person* p)
{
printf("주민등록번호 : %d\n", p->ssn);
printf("이름 : %s\n", p->name);
printf("주소 : %s\n", p->addr);
}//구조체의 주소를 받아오면 그 구조체의 주민등록번호, 이름, 주소 등을 모두 출력
Person* MakePersonData(int ssn, char* name, char* addr)
{
Person* newP = (Person*)malloc(sizeof(Person));
newP->ssn = ssn;
strcpy(newP->name, name);
strcpy(newP->addr, addr);
return newP;
} 이 때 위의 코드를 보면 구조체의 주소를 불러와서 데이터의 정보를 알아내는데
정작 구조체의 주소를 저장해놀을 공간이 없다.
즉, key와 value를 저장할 공간이 필요한데
이 key와 value를 저장할 하나의 공간을 슬롯이라 한다.
enum SlotStatus {EMPTY, DELETED, INUSE};
//이렇게 하면 EMPTY = 0, DELETED = 1, INUSE = 2로 저장된다.
typedef struct
{
int key;
Person* value;
enum SlotStatus status;//그리고 이렇게 선언하면 status는 enum SlotStatus 중 하나의 값만을 가질 수 있다.
}Slot;즉, 이런 식으로 Slot이라는 구조체를 만들고 구조체 하나당 key값과 Person의 정보가 들어있는 value
(코드레벨에서는 Person의 정보가 들어있는 구조체의 주소)를 하나씩 저장하고
Slot배열을 만들어 거기에 SLot들을 저장한다.
value에는 꼭 주소값을 넣어야하는 것은 아니고, value를 Person형으로 선언할 수도 있다.
그리고 Slot은 기본적으로 EMPTY, DELETED, INUSE 상태 중 하나인데
EMPTY는 비어있는 것, INUSE는 사용중이다.
그럼 DELETED는 무엇인가? 이전에 데이터가 저장된 바 있으나 현재는 비워진 상태이다.
당장은 DELETED상태가 왜 필요한지 의문이 들 수 있으나 이는 '충돌'문제를 해결하기 위해 필요한 것이다.
Slot Table[MAX_TBL];
void TBLInit(Slot* Table)
{
int i;
//모든 슬롯 초기화
for(i = 0; i < MAX_TBL; i++)
{
Table[i].status = EMPTY;
}
}여기서 MAX_TBL이란 테이블의 성분의 최대 개수이다.
테이블은 Slot구조체 배열이며, 강의에서는 함수포인터를 이용하여 해쉬함수를 구조체에 포함시켰으나
나는 그렇게는 하지 않으려고 한다.(이런건 객체지향언어가서!)
그리고 테이블의 초기화는 테이블안의 모든 슬롯의 status를 EMPTY로 바꿔준다.
그리고 삽입, 삭제, 탐색의 연산에서도 키를 알아야 하므로, 키를 별도로 전달해야 한다.
//삽입 시 key값을 이용하여 value를 테이블에 저장, 삭제도, 탐색도 마찬가지이다.
왜 key값이 아닌 정보 전체를 주면 안되냐? 범용성이 떨어지기 떄문
(5) 헤더파일에 선언된 함수들의 정의
void TBLInsert(Slot table, int k, Person v)//k는 키 값
{
int hv = h(k);//해쉬함수 h는 따로 정의, key값을 해쉬함수에 넣어 해쉬값을 얻는다.
table[hv].value = v;
table[hv].key = k;
table[hv].status = INUSE;
}
Person TBLDelete(Slot table, int k)//어차피 이번에 공부할 때만 쓸거라 typedef을 안 해줬는데 typedef Person* Value;를 해줘도 됐겠다.
(typedef A B는 A를 B로 써도 된다. define A B는 B를 A로 정의)
{
int hv = h(k);
if(table[hv].status != INUSE)//table[hv]가 사용 중이 아니라면
{
return NULL;
}
else
{
table.status = DELETED;
return table[hv].value;
}}
Person TBLSearch(Slot table, int k)
{
int hv = h(k);
if(table[hv].status != INUSE) return NULL;
else return table[hv].val;}
(6) 좋은 해쉬 함수의 조건
MAP. Table이라는 라이브러리에 등록된 함수들이 있는데, 여기 내장된 함수들도 그렇게 좋다고 할 수 없다.
왜냐하면 라이브러리에 등록된 함수들은 일반화되어 있기 때문이다.
그럼 어떤게 좋은 해쉬 함수일까?
가급적 데이터의 저장 위치가 분산되어 있는게 좋은데, 키 전체를 참조하여 해쉬값을 만들어내는게 가장 좋다.
ex. 자릿수 선택 방법과 자릿수 폴딩 방법
자릿수 선택 방법 ->
여덟 자리의 수로 이뤄진 키에서 다양한 해쉬 값 생성에 도움을 주는 네 자리의 수를 뽑아서 해쉬 값을 생성한다.
자릿수 폴딩 방법 ->
더 다양한 방법을 사용할 수 있다.
ex. 34 + 72 + 91
