20-1-다.해시
해시(Hash)는 자료를 입력할 때부터 검색하기 쉬운 위치에 삽입하는 방법이다. 따라서 해시는 검색 방법이라기보다는 빠른 검색을 위해 자료를 관리하는 기법이라고 볼 수 있다. 실생활에서도 해시 기법이 흔히 사용되는데 수첩에 주소록을 작성할 때 가나다순으로 페이지를 미리 분류하고 이름의 첫 글자를 기준으로 주소를 적는 방법이 바로 해싱이다.
수첩에 아무렇게나 주소를 적어 놓으면 새 주소를 추가하기는 간편하지만 다음에 찾기가 무척 어려워질 것이다. 하지만 성별로 분류해 놓으면 처음에 제 위치를 찾아 적기는 좀 귀찮지만 다음에 찾아 보기는 아주 쉬워진다. 김가, 강가는 ㄱ칸에서 찾고 황가, 한가는 ㅎ칸에서 찾으면 쉽게 찾을 수 있다. 이런 검색 방법이 바로 해싱이다.
자료가 저장되는 전체 저장소를 해시 테이블(Hash Table)이라고 한다. 해시 테이블은 여러 개의 버킷(Bucket)으로 나누어지는데 주소록 예에서 ㄱ, ㄴ, ㄷ, ㄹ 각 페이지가 버킷이다. 데이터를 삽입할 때 데이터의 값으로부터 적절한 버킷을 선택해서 삽입해야 한다. 버킷은 또한 여러 개의 슬롯(Slot)으로 구성되는데 슬롯은 버킷에 데이터가 저장되는 단위이다. 주소록의 각 페이지별로 한 명만 적을 수 있는 것이 아니라 여러 명을 적을 수 있어야 하는데 이때 한 명의 주소를 적는 칸이 슬롯이다.
해싱의 가장 기초적인 연산은 자료가 새로 입력될 때 이 자료를 어떤 버킷에 넣을지를 결정하는 것인데 이 연산을 하는 함수를 해시 함수라고 한다. 해시 함수는 입력된 키값으로 버킷의 번호(해시값)를 찾아내는 함수인데 새로 자료를 삽입할 때 해시 함수가 리턴하는 버킷 번호에 자료를 삽입한다. 다음에 특정 자료를 검색할 때는 다시 해시 함수로 버킷 번호를 찾아 여기에 원하는 자료가 있는지를 보면 된다.
주소록 예에서 해시 함수는 이름의 첫글자 자음으로부터 버킷 번호를 찾는다. 김 아무개는 ㄱ칸에, 장 아무개는 ㅈ칸을 찾아 선택된 버킷에 자료를 삽입하는 식이다. 이렇게 관리되는 주소록에서 "장군"이라는 사람의 주소를 알고 싶다면 "장군"을 다시 해시 함수로 넣어 ㅈ버킷을 찾고 이 페이지만 검색하면 쉽게 찾을 수 있다. 다음은 해시의 기본 동작 원리를 보여주는 아주 간단한 예제이다. 해시에 들어가는 수가 양의 정수 뿐이라고 가정하고 0은 버킷이 비어 있다는 특이값으로 사용한다.
|
예 제 : Hashing |
#include <Turboc.h>
#define BK 10
#define SL 1
int hashtable[BK][SL];
int hash(int key)
{
return key % 10;
}
void AddKey(int key)
{
int bucket;
bucket=hash(key);
if (hashtable[bucket][0] == 0) {
hashtable[bucket][0]=key;
}
}
BOOL FindKey(int key)
{
int bucket;
bucket=hash(key);
return (hashtable[bucket][0]==key);
}
void main()
{
int i,key;
memset(hashtable,0,sizeof(hashtable));
for (i=0;i<5;i++) {
printf("%d번째 값을 입력하세요 : ",i+1);scanf("%d",&key);
AddKey(key);
}
printf("검색할 키를 입력하세요 : ");scanf("%d",&key);
if (FindKey(key)) {
puts("검색되었습니다.");
} else {
puts("입력하신 값은 없습니다..");
}
}
해시 함수 hash는 키의 마지막 자리 수 하나만으로 해시값을 계산하는데 이는 % 연산자로 쉽게 구할 수 있다. 15는 5를, 347은 7을, 83은 3을 선택할 것이다. 10으로 나눈 나머지를 해시값으로 선택하므로 버킷은 10개를 준비하면 된다. 그래서 해시 테이블의 버킷 수는 10으로 정의했으면 충돌 현상을 쉽게 관찰하기 위해 슬롯은 일부러 1로 정의해 두었다.
AddKey 함수는 입력된 키로부터 hash 함수를 호출하여 해시값을 찾고 이 버킷이 비어 있을 때 해시 테이블에 데이터를 추가한다. 만약 이미 버킷이 점령되어 있다면 값을 추가할 수 없다. FindKey 함수는 키가 해시 테이블에 있는지만 조사하는데 해시값을 먼저 찾고 버킷에 들어있는 값과 키값을 비교한 결과를 리턴한다. 존재 여부만을 조사하도록 했는데 실제 예에서는 키가 들어있는 버킷과 슬롯 번호를 리턴하는 것이 더 실용적이다.
main 함수는 해시 테이블을 0으로 모두 초기화하여 비우는데 만약 이 테이블에 0도 입력될 수 있다면 -1 등의 다른 특이값으로 초기화해야 할 것이다. 그리고 다섯 개의 값을 입력받아 해시 테이블에 추가하고 검색할 키를 입력받은 후 FindKey 함수로 이 값이 해시 테이블에 들어 있는지 조사한다. 예제를 실행해 보자.
1번째 값을 입력하세요 : 7
2번째 값을 입력하세요 : 28
3번째 값을 입력하세요 : 942
4번째 값을 입력하세요 : 69
5번째 값을 입력하세요 : 33
검색할 키를 입력하세요 : 28
검색되었습니다.
다섯 개의 값을 입력했는데 각 입력에 의해 AddKey 함수는 뒷자리 번호에 해당하는 버킷에 값을 저장한다. 입력이 완료된 후 해시 테이블은 다음과 같은 상태가 될 것이다.
이 상태에서 28이 있는지 검색하는 방법은 아주 간단하고 빠르다. 해시 함수로 28이 들어갈 버킷 번호를 찾고 이 버킷에 과연 28이 들어 있는지만 점검하면 된다. FindKey는 28이 들어갈 8번 버킷만 보면 이 값의 존재 유무를 쉽게 알 수 있다. 해시 테이블이 아무리 크고 데이터가 많다 하더라도 검색 시간은 상수로 항상 일정하다. 검색 시간으로만 본다면 해시는 모든 검색 알고리즘 중에 가장 빠르다.
그러나 해싱도 여러 가지 문제점이 있는데 가장 큰 문제는 버킷끼리 충돌할 수 있다는 점이다. 새로 삽입하고자 하는 키의 버킷이 이미 점령되어 있다면 이 키는 해시 테이블에 추가할 수 없다. 예를 들어 38이 8번 버킷에 이미 들어 있을 때 48이나 58이 입력되면 이 값을 저장할 버킷이 없는 것이다. 버킷이 이미 점령되어 값을 추가할 수 없는 상황을 충돌(Collision)이라고 한다. 이 충돌을 어떻게 해결할 것인가가 해싱의 관건이며 물론 다수의 합리적인 해결 방법이 있다.
다중 슬롯
앞의 예제는 충돌 현상을 쉽게 목격하기 위해 슬롯 크기를 일부러 1로 설정했는데 슬롯을 충분히 크게 잡기만 해도 충돌을 많이 완화시킬 수 있다. 버킷의 슬롯이 커지면 설사 충돌이 발생하더라도 다음 슬롯에 데이터를 저장할 수 있으므로 슬롯 크기를 초과하는 데이터가 입력될 때만 문제가 발생한다. 슬롯 크기를 늘리면 데이터를 추가 및 검색하는 함수도 다중 슬롯을 지원하도록 수정해야 한다.
|
예 제 : MultiSlot |
#include <Turboc.h>
#define BK 10
#define SL 3
int hashtable[BK][SL];
int hash(int key)
{
return key % 10;
}
void AddKey(int key)
{
int i,bucket;
bucket=hash(key);
for (i=0;i<SL;i++) {
if (hashtable[bucket][i]==0) {
hashtable[bucket][i]=key;
break;
}
}
}
BOOL FindKey(int key)
{
int i,bucket;
bucket=hash(key);
for (i=0;i<SL;i++) {
if (hashtable[bucket][i]==key) {
return TRUE;
}
}
return FALSE;
}
====================== main은 동일하므로 생략 ======================
AddKey 함수는 일단 해시값을 찾은 후 슬롯 크기만큼 루프를 돌며 빈 자리를 찾아 새로운 키를 삽입한다. 버킷에 이미 값이 들어 있더라도 여유 슬롯이 있다면 이 슬롯에 새 데이터를 추가할 수 있을 것이다. 12, 76, 542, 126, 96 순으로 데이터가 입력되었다면 해시 테이블은 다음과 같이 구성된다.
2와 6자리에 데이터가 몰리더라도 슬롯이 충분하기 때문에 일단은 충돌을 방지할 수 있다. 단, 빈 슬롯이 하나도 없다면 이때는 삽입에 실패하며 여전히 충돌이 발생한다. 위 그림에서 새로 36이 입력된다면 충돌을 면할 수 없다. 슬롯이 아무리 많아도 한 버킷에 입력되는 데이터의 양이 많으면 어쩔 수 없는 것이다.
주소록에서도 이런 현상은 쉽게 목격할 수 있다. 가나다 순으로 페이지를 나누어 사람 이름을 적는데 다른 페이지는 남아 돌아도 ㄱ, ㅇ 페이지는 금방 가득 차서 더 적을 데가 없게 된다. 슬롯이 충분해도 입력되는 데이터가 많으면 이 충돌은 어쩔 수 없는 것이다. 그래서 다중 슬롯은 충돌을 지연시키기는 해도 완벽하게 해결하지는 못한다. 게다가 슬롯이 많아지면 추가, 검색 함수가 복잡해지기 때문에 실제 해싱을 할 때는 슬롯은 하나만 쓰고 다른 방법을 사용하는 것이 더 일반적이다.
정교한 해시 함수
해시 테이블이 아무리 커도 충돌은 발생할 수 있는데 이 충돌을 가급적 늦추고 버킷을 골고루 사용하려면 키로부터 해시값을 찾는 해시 함수가 정교해야 한다. 나머지 연산자로 끝 자리만 보는 간단한 방법은 균일한 해시값을 만들어 내는데는 한계가 있다. 예를 들어 해시 테이블에 저장되는 데이터가 점수값이라고 하자. 문제가 100개가 아닌 한 점수는 보통 1단위인 경우보다 2나 4단위인 경우가 많은데 이렇게 되면 짝수 버킷에만 데이터가 몰리게 될 것이고 홀수 버킷은 텅텅 빌 것이다. 이렇게 되면 충돌이 금방 발생할 뿐만 아니라 기억 장소도 낭비된다.
주소록의 경우도 마찬가지로 첫 글자의 자음을 해시값으로 쓰면 ㄱ, ㅂ, ㅇ 버킷은 금방 바닥나고 ㄹ, ㅋ, ㅌ 버킷은 남아돌 것이다. 알다시피 우리나라에게는 김가, 이가, 박가가 특히 많다. 첫 글자의 자음보다는 중간 글자의 자음을 보는 방법이 차라리 더 합리적인 해시 함수가 될 것이며 좀 더 정교하게 만들면 문자 코드의 총합을 구해 % 연산을 취하는 방법도 생각할 수 있다.
바람직한 해시 함수는 입력되는 임의의 값으로부터 균일한 해시값을 만들어 내야 한다. 또한 삽입과 검색 속도에 직접적인 영향을 미치므로 너무 복잡해서도 안되며 해시값을 신속하게 계산할 수 있어야 한다. 해시 함수를 만드는 여러 가지 연산 방법들이 개발되어 있는데 입력값을 제곱한다거나 쉬프트, 비트 연산으로 일부 비트만 취하는 간단한 방법에서부터 입력되는 값들의 분산, 표준 편차 등을 활용하는 수학적인 방법도 있다. 더하고 곱하고 나누고 돌리고 비틀고 꼬고 어찌하든간에 균일한 해시값만 만들어 내면 된다.
해시값은 복원 가능하지 않아도 상관없다. 즉 해시값으로부터 키를 다시 찾을 수 없더라도 문제되지 않는다. 키로부터 얻는 해시값이 일정하기만 하다면 삽입한 위치의 버킷 번호를 언제든지 찾을 수 있고 이 버킷에서 저장된 키를 읽을 수 있기 때문이다. 점수 데이터의 경우 십자리와 일자리를 더해 나머지 연산을 적용하기만 해도 훨씬 더 균일한 해시값을 얻을 수 있다.
int hash(int score)
{
return (score / 10 + score % 10) % 10;
}
모든 경우에 대해 잘 동작하는 그런 해시 함수는 없다. 저장하는 값의 성질을 잘 분석한 후에 값들을 골고루 분산시킬 수 있는 해시 함수를 찾아야 한다. 정교한 해시 함수는 충돌을 최소화하고 기억 장소를 효율적으로 사용하는 방법 중 하나이기는 하지만 충돌을 근본적으로 해결하지는 못한다.
선형 탐색
슬롯이 넉넉하고 해시 함수가 정교해도 충돌은 언제나 발생할 가능성이 있다. 그래서 충돌이 발생할 때의 대처 상황을 정의해야 하는데 선형 탐색법이 그 중 가장 간단한 방법이다. 선형 탐색법(Linear Probing)은 충돌이 발생할 경우 이 데이터를 버리지 않고 다른 버킷에라도 대신 집어 넣는 방법이다. 즉, 꿩 대신 닭을 찾는 방법인데 그렇다고 해서 아무 곳에나 넣어서는 안되며 검색 함수가 찾을 수 있는 곳이어야 한다.
대체 버킷을 찾는 가장 간단한 방법은 바로 옆칸에 적어 놓는 것이다. 그러면 검색 함수가 버킷에서 찾지 못했을 때 옆칸도 같이 찾아 볼 것이다. 주소록의 경우도 ㄱ칸이 모자라면 ㄴ칸을 잠시 빌려 쓸 수 있다. 이때 반드시 옆칸에 적어야지 ㅋ, ㅌ같은 엉뚱한 곳에 적어 놓으면 검색은 거의 불가능해질 것이다. 다음 예제는 선형 탐색의 예를 보여주는데 충돌의 재현을 쉽게 하기 위해 슬롯 크기는 다시 1로 설정했다.
|
예 제 : LinearProbe |
#include <Turboc.h>
#define BK 10
#define SL 1
int hashtable[BK][SL];
int hash(int key)
{
return key % 10;
}
void AddKey(int key)
{
int bucket;
bucket=hash(key);
while (hashtable[bucket][0]!=0) {
bucket=bucket+1 % BK;
}
hashtable[bucket][0]=key;
}
BOOL FindKey(int key)
{
int bucket;
bucket=hash(key);
while (hashtable[bucket][0]!=0) {
if (hashtable[bucket][0]==key) return TRUE;
bucket=bucket+1 % BK;
}
return FALSE;
}
====================== main은 동일하므로 생략 ======================
다음은 실행 결과이다.
1번째 값을 입력하세요 : 11
2번째 값을 입력하세요 : 12
3번째 값을 입력하세요 : 22
4번째 값을 입력하세요 : 66
5번째 값을 입력하세요 : 77
검색할 키를 입력하세요 : 22
검색되었습니다.
AddKey 함수는 입력된 데이터의 버킷 번호를 조사하여 여기에 데이터를 넣되 만약 이 버킷이 비어 있지 않다면 다음 버킷을 조사한다. 만약 다음 버킷도 비어 있지 않다면 그 다음 빈 버킷을 계속해서 찾아 최초로 빈 버킷에 값을 써 넣는다. 해시 테이블 전체가 가득 차지 않은 한 이 값이 들어갈 버킷을 언젠가는 찾게 될 것이다. 위 실행 예에서 11, 12까지는 제 자리를 찾아 들어 가지만 22가 들어갈 2번 버킷이 12에 의해 이미 점령당했으므로 22는 다음 칸인 3번 버킷에 들어간다.
만약 3번 버킷에도 값이 들어 있다면 그 다음 버킷을 찾을 것이다. 또한 22가 3번 버킷에 들어가 있는 상태에서 53같은 값이 입력된다면 이 값은 제 자리인 3번에 들어가지 못하고 다음 버킷에 들어가야 한다. AddKey는 이런 식으로 충돌 발생시 단순히 그 다음 칸을 사용한다. 만약 빈 칸이 하나도 없다면 무한 루프에 빠져 버리는 문제가 있는데 이 문제는 최초 버킷을 기억했다가 이 자리로 다시 돌아 왔을 때 에러 처리함으로써 일단 해결할 수 있다. 그러나 무한 루프만 해결했을 뿐이지 데이터 삽입은 실패하므로 해시 테이블을 더 크게 만들거나 아니며 해시 테이블보다 더 많은 자료를 삽입하지 않도록 하는 것이 근본적으로 옳다.
FindKey 함수는 특정 키가 있는지 검사할 때 해시값에 해당하는 버킷만 보아서는 안되며 다음 버킷과 그 다음 버킷까지도 봐야 한다. 그래서 빈 버킷을 만날 때까지 루프를 돌며 키를 찾아 보고 그래도 없을 때만 확실하게 없다는 결과를 리턴한다. 선형 탐색법은 삭제에 무척 취약한 알고리즘인데 FindKey가 빈칸을 찾을 때까지 검색을 하도록 되어 있어 삭제할 때 빈칸으로 만들어서는 안된다. 예를 들어 12, 22, 32, 42까지 입력한 후 22를 지우고 32를 찾는다고 해 보자.
22, 32, 42를 삽입할 때 충돌이 발생하므로 그 다음 칸에 이 값들을 기록했다. 이렇게 하더라도 FindKey가 연속된 옆칸을 찾도록 되어 있으므로 일단은 문제가 없다. 그러나 22가 삭제되어 버리면 FindKey가 버킷 3에서 검색을 중지하므로 32, 42는 없는 값으로 취급되어 버릴 것이다. 그래서 삭제할 때 빈칸으로 만들어서는 안되며 -1 등의 특이값으로 삭제된 칸임을 명시하고 FindKey는 삭제된 칸 이후도 계속 검색하도록 해야 한다.
이 예제의 선형 탐색법은 충돌 발생시 바로 오른쪽 칸을 사용하는데 반드시 그럴 필요는 없다. 왼쪽 칸을 사용할 수도 있고 일정칸씩 건너 뛰면서 다음 버킷을 찾을 수도 있다. 한 버킷이 넘치면 주변 버킷도 넘칠 확률이 높으로므 몇 칸씩 건너 뛰면 충돌을 좀 더 최소화할 수 있을 것이다.
재해시
재해시도 선형 탐색법과 기본적으로 유사한 방법이다. 선형 탐색법은 충돌 발생시 산술적인 연산으로 다른 칸을 찾지만 재해시법은 대체 칸을 찾는 해시 함수를 별도로 하나 더 두는 방법이다. 다음 예제를 보자.
|
예 제 : ReHash |
#include <Turboc.h>
#define BK 10
#define SL 1
int hashtable[BK][SL];
int hash(int key)
{
return key % 10;
}
int hash2(int key)
{
return (key/10 + key%10) % 10;
}
void AddKey(int key)
{
int bucket;
bucket=hash(key);
if (hashtable[bucket][0] != 0) {
bucket=hash2(key);
}
if (hashtable[bucket][0] == 0) {
hashtable[bucket][0]=key;
}
}
BOOL FindKey(int key)
{
int bucket;
bucket=hash(key);
if (hashtable[bucket][0]==key) {
return TRUE;
}
bucket=hash2(key);
if (hashtable[bucket][0]==key) {
return TRUE;
}
return FALSE;
}
====================== main은 동일하므로 생략 ======================
hash2라는 함수를 하나 더 정의하고 있는데 이 함수는 일자리와 십자리수를 더한 값을 10으로 나누기 연산해서 버킷을 찾는다. 예를 들어 23은 5를, 89는 7을 찾을 것이다. AddKey 함수는 먼저 hash 함수로 해시값을 찾되 이 자리가 점령되어 있다면 hash2 함수로 대체 버킷을 찾아 여기에 값을 기록한다. 만약 재해시를 했는데도 충돌이 발생한다면 이때는 어쩔 수 없다.
AddKey 함수가 두 개의 해시 함수를 사용하므로 FindKey 함수는 두 해시 함수가 계산하는 해시값을 다 점검해야 한다. 둘 중 하나라도 값이 존재하면 있는 것이고 둘 다 없다면 키가 존재하지 않는다는 것을 알 수 있다. 재해시 방법은 선형 탐사와 마찬가지로 충돌 발생시 대체칸을 찾는 방법인데 필요하다면 해시 함수를 더 많이 둘 수도 있다. 3차, 4차 해시 함수까지 둔다면 충돌 발생 확률은 지극히 떨어질 것이다.
단, 이때 재해시 함수는 원래 해시 함수와는 가급적 다른 해시값을 계산하도록 작성해야 한다. 만약 위 예에서 hash2 함수를 키의 제곱에 대한 10의 나머지를 계산하도록 return (key*key)%10으로 작성한다면 5나 6으로 끝나는 키에 대한 재해시 결과는 원래와 같아져 버려 별 소용이 없을 것이다.
동적 슬롯
동적 슬롯은 슬롯의 개수를 가변적으로 관리하는 방법이다. 선형 탐사나 재해시가 충돌을 회피하는 방법이라면 동적 슬롯은 충돌에 적극적으로 대처하는 방법이라고 할 수 있다. 최초 일정한 크기의 슬롯을 준비하되 만약 버킷이 가득찰 정도로 데이터가 들어 온다면 슬롯 크기를 실행중에 늘린다. 이렇게 하면 대체 버킷을 찾을 필요도 없고 삭제하는 방법도 번거롭지 않다.
슬롯은 실행중에 크기를 늘릴 수 있어야 하므로 동적 배열이나 연결 리스트로 작성해야 한다. 동적 배열을 쓴다면 해시 테이블은 포인터 배열이 될 것이다. 연결 리스트라면 각 버킷이 슬롯 연결 리스트의 진입점인 head를 저장해야 할 것이다. 버킷 내에서의 검색은 순차 검색을 사용하되 만약 동적 슬롯의 크기가 무척 커질 수 있다면 이분 검색을 쓰는 것이 더 유리할 것이다. 이때는 물론 배열로만 작성해야 한다.
이상으로 해싱에 대해 알아 봤는데 해싱은 검색 방법이라기 보다는 빠른 검색을 위한 자료 관리 알고리즘이라고 할 수 있다. 예제에서는 충돌 현상을 쉽게 목격하기 위해 해시 테이블도 작게 만들고 슬롯도 작게 만들었는데 실제 프로젝트에서는 해시 테이블을 가급적 크게 만들어야 한다. 정수를 저장한다면 버킷이 10개인 경우보다 100개인 경우 충돌이 훨씬 덜 할 것이고 1000개이면 더 좋다. 여기에 슬롯도 다섯 개 정도 준비하면 거의 충돌이 없을 것이고 혹시라도 충돌이 발생할 때를 대비해서 재해시 함수를 하나 정도 두면 된다.
해싱은 해시 함수로부터 버킷 위치를 바로 찾을 수 있으므로 검색 속도가 대단히 빠른 알고리즘이지만 반면 메모리는 굉장히 많이 소모한다. 크기와 속도가 항상 반비례라는 것을 잘 입증하는 알고리즘이다. 좀 더 빨라지고 싶다면 충분한 메모리를 준비해야 하고 메모리가 넉넉하지 않으면 잦은 충돌로 인해 느려질 수밖에 없다.