Chap13. 테이블과 해쉬
테이블
- 테이블에 저장되는 데이터는 키(key)와 값(value)가 한 쌍을 이룬다
- 키가 존재 하지 않는 값은 저장할수 없다.
- 모든 키는 중복되지 않는다.
- 키를 이용해서, 데이터를 '단번에' 찾아야 한다.
다음과 같은 사원 정보에 대한 구조체가 있다고 하자.
typedef struct _empInfo
{
int empNum;
int age;
} EmpInfo;empNum을 인덱스의 값으로해서 그 위치에 age 값을 저장하면, empNum의 인덱스 값을 기반으로 해당 사원의 age값을 바로 찾을수 있다.
예를들어 사원번호 100번인 사원의 나이는 EmpInfo[100] 으로 바로 찾을수 있을 것이다.
하지만 이런식으로 테이블을 만든다면 사원의 고유번호 empNum의 범위 만큼의 크기의 배열이 필요하다.
예를들어 사원의 고유번호가 1부터 1억까지라면 크기 1억의 배열이 필요하다.
이러한 문제는 해쉬로 해결하고 이것이 테이블 자료구조의 핵심이다.
해쉬
위의 테이블의 문제를 해결하는 것이 해쉬 함수다.
간단한 해쉬 함수는 예를들어 다음과 같다
int GetHashValue(int empNum)
{
return empNum % 100;
}
위 해쉬 함수는 사원번호를 받아 끝 두자리를 반환한다.
예를들어 사원번호가 8자리고 다음과 같다면 20120030
해쉬 함수에 이 사원번호가 전달되면 30 이 반환될 것이다.
이렇게 해쉬 함수는 넓은 범위의 키를 좁은 범위의 키로 변경한다.
아래는 Person이라는 객체를 Hash의 Slot에 저장하는 예제이다.
Person.h
/*
* hash slot에 담을 Person 객체
*/
#ifndef CHAP13_SIMPLEHASH_PERSON_H
#define CHAP13_SIMPLEHASH_PERSON_H
#define STR_LEN 50
typedef struct _person
{
int ssn; // 주민등록번호, key
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 //CHAP13_SIMPLEHASH_PERSON_H
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("ssn: %d\n", p->ssn);
printf("name: %s\n", p->name);
printf("addr: %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;
}Slot.h
/*
* hash slot
*/
#ifndef CHAP13_SIMPLEHASH_SLOT_H
#define CHAP13_SIMPLEHASH_SLOT_H
#include "Person.h"
typedef int Key; // Person ssn
typedef Person * Value;
enum SlotStatus {EMPTY, DELETED, INUSE};
typedef struct _slot
{
Key key;
Value val;
enum SlotStatus status;
} Slot;
#endif //CHAP13_SIMPLEHASH_SLOT_H
Table.h
/*
* Person을 저장하는 Slot을 갖는 Hash Table
*/
#ifndef CHAP13_SIMPLEHASH_TABLE_H
#define CHAP13_SIMPLEHASH_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);
// key를 근거로 테이블에서 데이터 삭제
Value TBLDelete(Table *pt, Key k);
// key를 근거로 테이블에서 데이터 탐색
Value TBLSearch(Table *pt, Key k);
#endif //CHAP13_SIMPLEHASH_TABLE_H
Table.c
#include <stdio.h>
#include <stdlib.h>
#include "Table.h"
void TBLInit(Table *pt, HashFunc *f)
{
for(int i = 0; i < MAX_TBL; i++)
(pt->tbl[i]).status = EMPTY;
pt->hf = f; // hash func 등록
}
void TBLInsert(Table *pt, Key k, Value v)
{
int hv = pt->hf(k); // hash func으로 key 가져옴
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; // 대상 값 반환
}
위 예제는 해쉬의 충돌은 해결하지 못한 예제다.
예를들어 위의 해쉬 함수에 20120003과 20210103 가 입력된다면 둘다 결과 값은 03 이고, 이것이 해쉬 충돌이다.
좋은 해쉬 함수
먼저 나쁜 해쉬 함수는 특정 영역에 데이터가 몰려 충돌 확률이 높아지도록 해쉬 값을 생성하는 해쉬 함수라고 할 수 있다.
반대로 좋은 해쉬 함수는 데이터가 골고루 분포하도록 해쉬 값을 생성하고 따라서 데이터의 충돌 확률이 낮다.
좋은 해쉬 함수를 디자인하는데 정답은 없는데 그것은 키의 특성에 따라 달라지기 때문이다.
하지만 일반적으로 좋은 해쉬 함수는 키의 일부분을 참조하여 해쉬 값을 만들지 않고, 키 전체를 참조해 해쉬 값을 만들어 낸다.
해쉬 충돌 해결 방법 : 열린 어드레싱 방법
선형 조사법
충돌이 발생했을때, 그 옆자리를 살펴보고 비었으면 그 자리에 데이터를 저장하고, 비어있지 않다면 그 옆 자리를 살핀다 ...
즉 k의 키에서 충돌 발생 시 조사 순서는
f(k)+1 -> f(k)+2 -> f(k)+3 ...
선형 조사법의 단점은 충돌의 횟수가 증가함에 따라 특정 영역에 데이터가 집중적으로 몰리게 된다. (클러스터 현상)
이차 조사법
이차 조사법은 위 선형 조사법의 클러스터 현상을 어느정도 해결한다.
k의 키에서 충돌 발생 시 조사 순서는
f(k)+1^2 -> f(k)+2^2 -> f(k)+3^2 ...
이차 조사법의 단점은 해쉬 값이 같으면, 충돌 발생시 빈 슬롯을 찾기 위해 접근하는 위치가 늘 동일하기 때문에 여전히 클러스터 현상이 발생할 확률이 높다는 것이다.
예를들어 해쉬 함수가 k%15일때 3, 18, 33이 해쉬 함수를 거치면 모두 결과는 3이다.
따라서 위 3개의 숫자들은 해쉬 충돌시 모두 같은 자리를 탐색하게 된다.
이중 해쉬
이중 해쉬는 말그대로 2개의 해쉬 함수를 사용한다.
- 1차 해쉬 함수: 키를 근거로 저장위치를 결정
- 2차 해쉬 함수: 충돌 발생 시 몇 칸 뒤를 살펴볼지 결정
1차 해쉬 함수는 지금까지처럼 만들면 된다.
2차 해쉬 함수는 일반적으로 다음과 같은 형태로 만들어진다
h2(k) = 1 + (k % c)
위의 2차 해쉬 함수에서 상수 c는 일반적으로 배열의 크기 보다 작고, 소수(prime number)인 수 중에서 하나를 고른다.
배열의 크기보다 작은 값인 이유는 배열의 크기보다 클 경우 배열을 몇 바퀴 돌 수도 있기 때문이고, 소수인 이유는 소수를 선택했을 때 클러스터 현상의 발생 확률이 매우 낮다는 통계에 의한다.
또한 1을 더하는 이유는 해쉬 값이 0이 되지 않도록 하기 위해서다.
해쉬 값이 0이 되지 않도록 하는 이유는 2차 해쉬 함수의 결과는 충돌 발생 시 몇 칸 뒤를 살펴볼지 결정하는 값인데 0이면 그자리 그대로다.
슬롯의 상태
앞서 간단한 테이블을 구현했을때 slot에 상태를 다음과 같이 나타냈다.
enum SlotStatus {EMPTY, DELETED, INUSE};
이렇게 슬롯들에 상태를 표시한 이유는 다음과 같다.
해쉬 함수가 다음과 같을때
int HashFunc(int k)
{
return k % 7;
}
key 9가 해쉬함수에 전달되면 2를 리턴해 다음과 같이 [2]에 해당 키를 저장한다.
| idx:0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 9 |
이어서 key 2가 전달되면 마찬가지로 2를 리턴하고, 선형 조사법에 따라 충돌을 해결한다고 하면 다음과 같은 상태가 된다.
| idx:0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 9 | 2 |
이 상황에서 만약 키가 9인 데이터를 삭제했을 때, 키가 2인 데이터를 탐색하는 상황을 생각해보자.
| idx:0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 2 |
키가 2인 데이터를 찾기 위해 해쉬 함수를 거치고, 결과로 얻은 2를 인덱스 값으로 하여 탐색을 시작하는데, 위 테이블에서 [2] 자리는 비어있고 탐색을 중지하게 된다.
따라서 각 슬롯에 상태를 표시하는 것이다.
키가 9인 데이터를 삭제했을때 해당 슬롯을 DELETED 상태로 변경해주면, 키가 2인 데이터를 찾을때 [2] 로 찾아가서 DELETED 상태인것을 확인하고 선형 조사법 또는 이차 조사법에 따라 다음으로 탐색할곳으로 이동한다.
해쉬 충돌 해결 방법 : 닫힌 어드레싱 방법
체이닝
체이닝은 해쉬 충돌 해결 방법 중 열린 어드레싱 방법 중 하나로, 해쉬 충돌이 발생해도 같은 자리에 저장한다는 의미가 담겨있다.
그리고 같은 자리에 저장할수 있는 방법은 바로 자리를 늘리는 것이고, 일반적으로 연결 리스트를 이용해 슬롯을 연결한다.
체이닝은 탐색 시 동일한 해쉬 값으로 묶여있는 연결된 슬롯을 모두 탐색해야 한다는 단점이 있지만, 해쉬 함수를 잘 정의해 충돌이 많이 일어나지 않게 한다면 감당할수 없을 정도는 아닐 것이다.
구현
Slot이 노드의 맴버가 되도록 체이닝을 구현.
이전에 구현한 연결 리스트를 사용.
DLinkedList.h
#include <stdio.h>
#include <stdlib.h>
#include "Table.h"
#include "DLinkedList.h"
void TBLInit(Table *pt, HashFunc *f)
{
for(int i = 0; i < MAX_TBL; i++)
ListInit(&(pt->tbl[i]));
pt->hf = f; // hash func 등록
}
void TBLInsert(Table *pt, Key k, Value v)
{
int hv = pt->hf(k); // hash func으로 key 가져옴
Slot ns = {k, v};
if(TBLSearch(pt, k) != NULL) // key가 중복
{
printf("existing key\n");
return;
}
else
{
LInsert(&(pt->tbl[hv]), ns);
}
}
Value TBLDelete(Table *pt, Key k)
{
int hv = pt->hf(k);
Slot cSlot;
if(LFirst(&(pt->tbl[hv]), &cSlot))
{
if(cSlot.key == k)
{
LRemove(&(pt->tbl[hv]));
return cSlot.val;
}
else
{
while(LNext(&(pt->tbl[hv]), &cSlot))
{
if(cSlot.key == k)
{
LRemove(&(pt->tbl[hv]));
return cSlot.val;
}
}
}
}
return NULL;
}
Value TBLSearch(Table *pt, Key k)
{
int hv = pt->hf(k);
Slot cSlot;
if(LFirst(&(pt->tbl[hv]), &cSlot))
{
if(cSlot.key == k) return cSlot.val;
else
{
while(LNext(&(pt->tbl[hv]), &cSlot))
{
if(cSlot.key == k) return cSlot.val;
}
}
}
return NULL;
}
Table.c
#include <stdio.h>
#include <stdlib.h>
#include "Table.h"
#include "DLinkedList.h"
void TBLInit(Table *pt, HashFunc *f)
{
for(int i = 0; i < MAX_TBL; i++)
ListInit(&(pt->tbl[i]));
pt->hf = f; // hash func 등록
}
void TBLInsert(Table *pt, Key k, Value v)
{
int hv = pt->hf(k); // hash func으로 key 가져옴
Slot ns = {k, v};
if(TBLSearch(pt, k) != NULL) // key가 중복
{
printf("existing key\n");
return;
}
else
{
LInsert(&(pt->tbl[hv]), ns);
}
}
Value TBLDelete(Table *pt, Key k)
{
int hv = pt->hf(k);
Slot cSlot;
if(LFirst(&(pt->tbl[hv]), &cSlot))
{
if(cSlot.key == k)
{
LRemove(&(pt->tbl[hv]));
return cSlot.val;
}
else
{
while(LNext(&(pt->tbl[hv]), &cSlot))
{
if(cSlot.key == k)
{
LRemove(&(pt->tbl[hv]));
return cSlot.val;
}
}
}
}
return NULL;
}
Value TBLSearch(Table *pt, Key k)
{
int hv = pt->hf(k);
Slot cSlot;
if(LFirst(&(pt->tbl[hv]), &cSlot))
{
if(cSlot.key == k) return cSlot.val;
else
{
while(LNext(&(pt->tbl[hv]), &cSlot))
{
if(cSlot.key == k) return cSlot.val;
}
}
}
return NULL;
}