테이블(Table)
탐색 연산은 O(1)의 시간 복잡도이므로, 단번에 탐색을 수행한다고 표현이 가능하다.
저장되는 데이터는 키(key)와 값(value)이 하나의 쌍을 이룬다.
'값'은 반드시 '키'가 존재해야 하며, 키는 중복 비허용.
단어가 키가 되고, 그 단어에 대한 설명 또는 내용이 값이 되는 사전(dictionary)이 테이블의 대표적인 예시.
맵(map)이라 불리기도 한다.
배열을 기반으로 하는 테이블 소스 코드
// UnderstandTable.c
#include <stdio.h>
typedef struct _empInfo
{
int empNum;
int age;
} EmpInfo;
int main(void)
{
EmpInfo empInfoArr[1000];
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;
}출력 결과
사번과 나이 입력: 134 25 확인하고픈 직원의 사번 입력: 134 사번 134, 나이 25
위 예제의 단점
1. 번호의 범위는 배열의 인덱스 값으로 사용하기에 적당하지 않다.
2. 번호의 범위를 수용할 수 있는 매우 큰 배열이 필요하다.
위 두 가지의 문제를 동시 해결해주는 것이 '해쉬 함수'.
"직원의 고유번호는 입사 년도 네 자리와 입사순서 네 자리로 구성된다"라는 가정을 추가하여 위 예제를 재구성한 소스 코드.
// TableHashFunction.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
여덟 자리의 수로 이뤄진 직원의 고유번호를 두 자리의 수로 변경하는 함수를 구현했고
이러한 함수 ∫(x)도 변경의 일종이며 해쉬 함수(hash function)라 하고
해쉬 함수는 넓은 범위의 키를 좁은 범위의 키로 변경하는 역할을 한다.
서로 다른 두 개의 키가 해쉬 함수를 통과하였는데, 그 결과가 동일한 상황을 충돌(collision)이라 하고 피하기보다는 해결이 필요.
어느 정도 갖춰진 테이블과 해쉬의 구현 소스 코드
// Person.h
#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 * MakePersonData(int ssn, char * name, char * addr);
#endif// Person.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "Person.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));
newP->ssn = ssn;
strcpy(newP->name, name);
strcpy(newP->addr, addr);
return newP;
}// Slot.h
#ifndef __SLOT_H__
#define __SLOT_H__
#include "Person.h"
typedef int Key;
typedef Person * Value;
enum SlotStatus {EMPTY, DELETED, INUSE};
typedef struct _slot
{
Key key;
Value val;
enum SlotStatus status;
} Slot;
#endif// Table.h
#ifndef __TABLE_H_
#define __TABLE_H_
#include "Slot.h"
#define MAX_TBL 100
typedef int (*HashFunc)(Key k);
typedef struct _table
{
Slot tbl[MAX_TBL];
HashFunc * hf;
} Table;
// 테이블의 초기화
void TBLInit(Table * pt, HashFunc * f);
// 테이블에 키와 값을 저장
void TBLInsert(Table * pt, Key k, Value v);
// 키를 근거로 테이블에서 데이터 삭제
Value TBLDelete(Table * pt, Key k);
// 키를 근거로 테이블에서 데이터 탐색
Value TBLSearch(Table * pt, Key k);
#endif// Table.c
#include <stdio.h>
#include <stdlib.h>
#include "Table.h"
void TBLInit(Table * pt, HashFunc * f)
{
int i;
// 모든 슬롯 초기화
for(i=0; i<MAX_TBL; i++)
(pt->tbl[i]).status = EMPTY;
pt->hf = f; // 해쉬 함수 등록
}
void TBLInsert(Table * pt, Key k, Value v)
{
int hv = pt->hf(k);
pt->tbl[hv].val = v;
pt->tbl[hv].key = k;
pt->tbl[hv].status = INUSE;
}
Value TBLDelete(Table * pt, Key k)
{
int hv = pt->hf(k);
if((pt->tbl[hv]).status != INUSE)
return NULL;
else {
(pt->tbl[hv]).status = DELETED;
return (pt->tbl[hv]).val; // 소멸 대상의 값 반환
}
}
Value TBLSearch(Table * pt, Key k)
{
int hv = pt->hf(k);
if((pt->tbl[hv]).status != INUSE)
return NULL;
else
return (pt->tbl[hv]).val; // 탐색 대상의 값 반환
}// SimpleHashMain.c
#include <stdio.h>
#include <stdlib.h>
#include "Person.h"
#include "Table.h"
int MyHashFunc(int k)
{
return k % 100; // 키를 부분적으로 사용한 좋지 않은 해쉬의 예시
}
int main(void)
{
Table myTbl;
Person *np;
Person *sp;
Person *rp;
TBLInit(&myTbl, MyHashFunc);
// 데이터 입력
np = MakePersonData(20120003, "Lee", "Seoul");
TBLInsert(&myTbl, GetSSN(np), np);
np = MakePersonData(20130012, "KIM", "Jeju");
TBLInsert(&myTbl, GetSSN(np), np);
np = MakePersonData(20170049, "HAN", "Kangwon");
TBLInsert(&myTbl, GetSSN(np), np);
// 데이터 검색
sp = TBLSearch(&myTbl, 20120003);
if (sp != NULL)
ShowPerInfo(sp);
sp = TBLSearch(&myTbl, 20130012);
if (sp != NULL)
ShowPerInfo(sp);
sp = TBLSearch(&myTbl, 20170049);
if (sp != NULL)
ShowPerInfo(sp);
// 데이터 삭제
rp = TBLDelete(&myTbl, 20120003);
if (rp != NULL)
free(rp);
rp = TBLDelete(&myTbl, 20130012);
if (rp != NULL)
free(rp);
rp = TBLDelete(&myTbl, 20170049);
if (rp != NULL)
free(rp);
return 0;
}
좋은 해쉬 함수의 조건이란?
데이터가 테이블의 전체 영역에 고루 분포되어 있어서 충돌이 발생할 확률이 낮음
좋지 않은 해쉬 함수의 조건이란?
테이블의 특정 영역에 데이터가 몰려있음
이는 해쉬 함수가 특정 영역에 데이터가 몰리도록 해쉬 값을 생성한 결과이고 충돌 가능성도 높아진다.
"좋은 해쉬 함수는 키의 일부분을 참조하여 해쉬 값을 만들지 않고, 키 전체를 참조하여 해쉬 값을 만들어 낸다."
적은 수의 데이터를 조합하여(키의 일부분을 조합하여) 해쉬 값을 생성하는 것보다 많은 수의 데이터를 조합하여(키 전부를 조합하여) 해쉬 값을 생성했을 때, 보다 다양한 값의 생성을 기대할 수 있을 것이다.
좋은 해쉬 함수의 디자인 방법은 키의 특성에 따라 달라지고 해쉬 함수의 디자인에 있어서 절대적인 방법은 없음.
그 예시 중 두 가지 방법은?
1. 자릿수 선택(Digit Selection) - 여덟 자리의 수로 이뤄진 키에서 다양한 해쉬 값 생성에 도움을 주는 네 자리 수를 뽑아서 해쉬 값을 생성
2. 자릿수 폴딩(Digit Folding) - 여러 수를 펼쳐놓고 각 자리의 수를 더함 - 모든 숫자를 모두 반영하여 얻은 결과
댓글 없음:
댓글 쓰기