해시 (체이닝, 개방주소)

해쉬 테이블(hash table)

해쉬 테이블은 키(key)라는 특별한 인덱스로 자료에 접근하는 배열로 구성되는 자료구조 이다.

해쉬 테이블의 해쉬 함수는 키 값을 받아 그 키의 해쉬값(hash coding 또는 hash value)을 리턴한다.

간단한 해쉬테이블을 시각적으로 표시했을 때, 아래와 같은 그림으로 표시할 수 있다.

 

 

해쉬 테이블의 장점은 상수 시간에 탐색이 가능한 것이다.

대신 다른 특징(혹은 단점?)은 순차적인 접근을 지원하지 않는 것이다.

따라서 이러한 특징에 맞는 상황에서 사용되어야 할 것이다.

 

추가적으로 해쉬 테이블의 특징을 좀 더 알아보자.

- 사용할 키와 해쉬 함수를 잘 선택하여 테이블에 균등하게 항목이 배분되도록 해야 한다.

- 다른 키값에 대해 같은 해쉬값(같은 테이블로 매핑되는 경우)을 가지는 경우 충돌(collision)이라고 한다.

- 충돌 해결 방법에는 여러가지가 있으며 대표적인 방법(책에 설명된)은

  연쇄 해쉬 테이블(chained hash table)과 개방 주소지정 해쉬 테이블(open-addressed hash table)이 있다.

 

위키피디아에 따르면 해쉬 테이블은 탐색 트리(search tree)나 다른 lookup 구조의 테이블보다 효율적이라고 한다.

이런 이유로 아래와 같은 곳에서 사용이 된다. (참조: http://en.wikipedia.org/wiki/Hash_table#Uses )

- Associative arrays (프로그래밍 랭귀지의 데이터 타입 같은 것. 예를 들면 Python 의 Dictionary 타입?)

- Database indexing

- Caches

- Sets

- Object representation

- Unique data representation

 

위키피디아에 상세한 설명이 되어 있으니, 해쉬 테이블에 대한 더 많은 정보를 원한다면 방문해 보기 바란다.

http://en.wikipedia.org/wiki/Hash_table

 

앞으로 나올 용어에 대해서 간단히 설명하면 다음과 같이 사용할 것이다.

n : 테이블의 항목 갯수

m : 버킷의 갯수

a : 부하 계수(load factor). a = n / m

 

 

해쉬 테이블 인터페이스

해쉬 테이블에 필요한 인터페이스는 간단한 편이다.

Data Insert, Remove, Lookup 정도?

중요한 건 키 값을 같이 넘겨주는 것이다.

 

해쉬 함수(hash function)

 

 

 

 

해쉬 함수 h 는 키값 k 를 받아 테이블 위치 x 에 매핑하는 함수이다.

k 의 값은 보통 정수임을 가정한다.

k 가 정수가 아니더라도 어렵지 않게 정수로 바꿀 수 있다.

(물론 k 가 같은 값이 나오지 않게 잘 바꿔야 하겠다)

 

책에서는 간단한 방법 2가지를 제시한다.

- 나눗셈 방법(devision method)

 

 

으로 표현할 수 있다. 일반적으로 m 의 값으로는 2의 제곱수는 피해서

2의 제곱수에 가깝지 않은 소수를 m 으로 선택한다.

 

- 곱셈 방법(multiplication method)

 

 

k*A 한 다음 여기에서 소수 부분만 택하여 m 을 곱한값에서 정수 부분만 택한값을 사용한다.

( A 값은 저렇게 하면 효율적이라고 Donald Knuth 란 분이 이야기 했나 보다. )

 

이것들은 간단한 방법들이니 좀 더 효율적인 해쉬 함수를 원한다면,

좀 더 공부가 필요하겠다.

 

 

충돌 해결(Collision resolution)

① 체이닝(Chaining)

 

체이닝에서는 같은 주소로 해슁되는 원소를 모두 하나의 연결 리스트에 매달아 관리한다.

 

 

위 의 그림처럼 h(39) = h(13) = 0 인 경우 해쉬테이블의 0 인덱스는 39를 가리키고 39는 13을 가리킨다.

 

체이닝에서의 삽입은 효율성을 위해서 연결리스트의 맨 앞에 삽입을 한다. 맨 뒤에 삽입할 경우 삽입시마다 연결리스트를 따라 맨 끝으로 이동해야하므로 낭비가 된다.

 

탐색과 삭제 같은 경우는 그냥 연결리스트 방식과 동일하게 진행된다.

 

 

구현소스

ChainingHashTable.h

#ifndef CHAINING_HASH_TABLE
#define CHAINING_HASH_TABLE
#include <stdio.h>
#include <stdlib.h> 
#include <string.h> 
typedef char* KeyType;
typedef char* ValueType; 
typedef struct tagNode { 
	KeyType Key;
	ValueType Value; 
	struct tagNode* Next; 
	
} Node; 
typedef Node* List;
typedef struct tagHashTable
{ 
	int TableSize; List* Table;
	// Linked List로 구현된 Node를 가리키는 더블 포인터 // HashTable 생성시 동적할당되어 포인터 배열로 쓰임.
	}HashTable; 
	HashTable*	CHT_CreateHashTable(int TableSize);
	void	CHT_DestroyHashTable(HashTable* HT);
	Node*	CHT_CreateNode(KeyType Key, ValueType Value); 
	void	CHT_DestroyNode(Node* _Node);
	void	CHT_Set(HashTable* HT, KeyType Key, ValueType Value);
	ValueType	CHT_Get(HashTable* HT, KeyType Key);
	int	CHT_Hash(KeyType Key, int KeyLength, int TableSize); 
	void	CHT_DestroyList(List L); 
	#endif 

-----------------------------------------------------------------------

ChainingHashTable.cpp

#include "ChainingHashTable.h"
HashTable* CHT_CreateHashTable(int TableSize) {
HashTable* HT = (HashTable*) malloc( sizeof(HashTable) );
HT->TableSize = TableSize; HT->Table = (List*) malloc( sizeof(List) * TableSize ); 
// List를 가리키는(Node *) 포인터 배열을 생성후 
memset(HT->Table , 0, sizeof(List) * TableSize);
// NULL 로 초기화 
return HT; }
Node* CHT_CreateNode(KeyType Key, ValueType Value) 
{ 
Node* NewNode = (Node*) malloc( sizeof(Node) );
NewNode->Key = (char*) malloc( sizeof(char) * (strlen(Key) + 1) );
NewNode->Value = (char*) malloc( sizeof(char) * (strlen(Value) + 1) ); 
strcpy(NewNode->Key , Key);
strcpy(NewNode->Value , Value);
NewNode->Next = NULL; return NewNode; 
} 
void CHT_DestroyNode(Node* _Node) 
{
free(_Node->Key); 
free(_Node->Value);
free(_Node); 
} 
void CHT_DestroyList(List L)
{ if(L==NULL) return; if(L->Next !=NULL) CHT_DestroyList(L->Next);
CHT_DestroyNode(L);
// List의 마지막 요소부터 순차적으로 제거
} 
void CHT_DestroyHashTable(HashTable* HT)
{
int i; for(i=0; i< HT->TableSize ; i++)
{ 
List L = HT->Table[i];
CHT_DestroyList(L);
} 
// 먼저 Table에 연결된 Node들을 모두 제거한 후에 
// Table을 제거하고 
free(HT->Table); 
// 해쉬 테이블을 제거한다. 
free(HT); 
} 
void CHT_Set(HashTable* HT, KeyType Key, ValueType Value) 
{ 
int Address = CHT_Hash(Key, strlen(Key), HT->TableSize);
Node* NewNode = CHT_CreateNode(Key, Value);
printf(" - Hashing ...Key : [%s], Value : [%s], Address : [%d]\n", Key, Value, Address); 
// 해당 주소가 비어 있는 경우 
if(HT->Table[Address] == NULL) { HT->Table[Address] = NewNode; 
} 
else 
{ // 비어 있지 않는 경우 
// NewNode가 List의 Head가 되게 조정. 
List L = HT->Table[Address]; 
// List = Node* 
NewNode->Next = L;
HT->Table[Address] = NewNode; 
printf(" ** Collision Occured : Key(%s), Address(%d) \n", Key, Address); 
} 
}
ValueType CHT_Get(HashTable* HT, KeyType Key)
{ 
int Address = CHT_Hash(Key, strlen(Key), HT->TableSize); 
List _List = HT->Table[Address];
List Target = NULL; 
if(_List == NULL) return NULL; 
while(1) { if(strcmp( _List->Key, Key) == 0 ) 
{ 
// 찾는 Key 값과 동일한 경우 
Target = _List; 
break; 
} 
if( _List->Next == NULL ) break;
else{ _List = _List->Next ;
printf(" *** Finding *** .... Key : %s\n", Key);
} 
}
if(Target == NULL) return NULL; return Target->Value;
}
int CHT_Hash(KeyType Key, int KeyLength, int TableSize) 
{ 
int i; int HashValue = 0;
for(i=0 ; i< KeyLength; i++) HashValue = (HashValue << 3) + Key[i];
// 자릿수 접기
// - 아스키코드는 0~127이므로 만약에 10개의 문자를 지는 문자열이라면
// 가질 수 있는 값의 최대는 1270이다. Table 사이즈가 2000이라면 730의 공간이 쓰여지지 않기 때문에 
// 시프트 연산을 활용하여 그 값을 늘린다. 
// ex) HashValue가 2이라면 2 << 3 의 결과는 0010 -> 10000 이 되므로 8이 됨. n << x의 결과는 n * n^x = n^(x+1) 
HashValue = HashValue % TableSize;
return HashValue; 
} 

-----------------------------------------------------------------------

main.cpp

#include "ChainingHashTable.h"
int main()
{ 
HashTable* HT = CHT_CreateHashTable(12289); 
CHT_Set( HT, "MSFT", "Microsoft Corporation"); 
CHT_Set( HT, "JAVA", "Sun Microsystems"); 
CHT_Set( HT, "REDH", "Red Hat Linux"); 
CHT_Set( HT, "APAC", "Apache Org"); 
CHT_Set( HT, "ZYMZZ", "Unisys Ops Check"); 
CHT_Set( HT, "IBM", "IBM Ltd."); 
CHT_Set( HT, "ORCL", "Oracle Corporation"); 
CHT_Set( HT, "CSCO", "Cisco Systems, Inc."); 
CHT_Set( HT, "GOOG", "Google Inc."); 
CHT_Set( HT, "YHOO", "Yahoo! Inc."); 
CHT_Set( HT, "NOVL", "Novell, Inc."); 
printf("\n"); printf("Key:%s , Value:%s\n", "MSFT", CHT_Get( HT, "MSFT" ) ); 
printf("Key:%s , Value:%s\n", "REDH", CHT_Get( HT, "REDH" ) ); 
printf("Key:%s , Value:%s\n", "APAC", CHT_Get( HT, "APAC" ) ); 
printf("Key:%s, Value:%s\n", "ZYMZZ", CHT_Get( HT, "ZYMZZ" ) ); 
printf("Key:%s , Value:%s\n", "JAVA", CHT_Get( HT, "JAVA" ) ); 
printf("Key:%s , Value:%s\n", "IBM", CHT_Get( HT, "IBM" ) ); 
printf("Key:%s , Value:%s\n", "ORCL", CHT_Get( HT, "ORCL" ) ); 
printf("Key:%s , Value:%s\n", "CSCO", CHT_Get( HT, "CSCO" ) ); 
printf("Key:%s , Value:%s\n", "GOOG", CHT_Get( HT, "GOOG" ) ); 
printf("Key:%s , Value:%s\n", "YHOO", CHT_Get( HT, "YHOO" ) ); 
printf("Key:%s , Value:%s\n", "NOVL", CHT_Get( HT, "NOVL" ) ); 
CHT_DestroyHashTable( HT );
return 0; 
} 

-----------------------------------------------------------------------

실행결과

 

- 개방 주소지정 해쉬 테이블(Open addressing)

 

 

그림이 좀 헷갈려 보이긴 하지만, 위와 같은 충돌 발생시 다른 버킷에 저장하는 방식이다.

여기서 잠깐, 다른 버킷은 어떻게 선택하는가?

잘 알려진 방법으로는 다음과 같은 3가지 방법이 있다.

 

1. 선형 조사(Linear probing) : 다음 버킷을 조사. 주클러스터링 현상으로 과다한 조사 발생 가능성 있음.

2. 2중 조사(Quadratic probing) : i^2 번째의 버킷을 조사. 부클러스터링 현상으로 과다한 조사 발생 가능성 있음.

   (i 는 현재까지 조사한 위치의 갯수)

3. 2중 해싱(Double hashing): 해쉬 함수와 보조 해쉬 함수의 결과를 더하는 것이다.

2중 조사와 다른 점은, 키 값에 따라 다음 조사위치가 고정된 것이 아니라 달라진다는 것이다.

수식으로 표현하지면 위와 같다. 그러나 어떤 위치가 두 번 조사되기 전에 모든 위치들이

조사됨을 보장하기 위해 다음의 두 절차 중 하나를 따라야 한다.

a. m이 2의 제곱수이고 h2 가 항상 홀수를 리턴한다.

b. m이 소수이고 h2는 항상 m보다 작은 양수를 리턴해야 한다.

 

 

구현 소스

OpenAddressing.h

#ifndef OPEN_ADDRESSING_H 
#define OPEN_ADDRESSING_H
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef char* KeyType;
typedef char* ValueType;
enum ElementStatus { Empty = 0, Occupied = 1 }; 
typedef struct tagElementType {
KeyType Key;
ValueType Value; 
enum ElementStatus Status;
}ElementType; 
typedef struct tagHashTable 
{ int OccupiedCount;
int TableSize; 
ElementType* Table; 
}HashTable; 
HashTable* OAHT_CreateHashTable(int TableSize);
void OAHT_DestroyHashTable(HashTable* HT);
void OAHT_ClearElement(ElementType* Element);
void OAHT_Set(HashTable** HT, KeyType Key, ValueType Value);
ValueType OAHT_Get(HashTable* HT, KeyType Key); 
int OAHT_Hash(KeyType Key, int KeyLength, int TableSize);
int OAHT_Hash2(KeyType Key, int KeyLength, int TableSize);
void OAHT_Rehash(HashTable** HT);
#endif

 
---------------------------------------------------------------
OpenAddressing.cpp

#include "OpenAddressing.h" 
HashTable* OAHT_CreateHashTable(int TableSize)
{
HashTable* HT = (HashTable*) malloc( sizeof(HashTable) );
HT->Table = (ElementType*) malloc( sizeof(ElementType) * TableSize ); 
memset( HT->Table , 0, sizeof(ElementType) * TableSize); 
HT->OccupiedCount = 0; HT->TableSize = TableSize; return HT;
} 
void OAHT_Set(HashTable** HT, KeyType Key, ValueType Value) 
{
int KeyLen, Address, StepSize; double Used; 
Used = (double)(*HT)->OccupiedCount / (*HT)->TableSize ;
if( Used > 0.5) 
// 점유율이 0.5이상일때 재해싱 수행(OAHT_Rehash 함수 호출) 
{ OAHT_Rehash(HT); 
} 
KeyLen = strlen(Key); 
Address = OAHT_Hash( Key, KeyLen, (*HT)->TableSize ); 
StepSize = OAHT_Hash2( Key, KeyLen, (*HT)->TableSize ); 
while( (*HT)->Table[Address].Status != Empty && strcmp( (*HT)->Table[Address].Key , Key) !=0) 
{
// 1차 해싱후 구한 Address가 이미 점유되어 있고,
//키 값이 다른 경우 -> 충돌이 일어난 경우 
// 2차 해싱값을 더한 값을 Address 로 사용한다.
printf(" *** Collusion Occured : Key[%s] , Address[%d], StepSize[%d]\n" ,Key,Address,StepSize); Address = (Address + StepSize) % (*HT)->TableSize ; }
(*HT)->Table[Address].Key = (char* )malloc( sizeof(char) * (strlen(Key) + 1) );
(*HT)->Table[Address].Value = (char* )malloc( sizeof(char) * (strlen(Value) + 1) ) ;
strcpy( (*HT)->Table[Address].Key , Key ); strcpy( (*HT)->Table[Address].Value, Value );
( (*HT)->OccupiedCount )++;
(*HT)->Table[Address].Status = Occupied;
printf(" ...Hashing - Key[%s], Value[%s], Address[%d]\n", Key, Value, Address);
} 
ValueType OAHT_Get(HashTable* HT, KeyType Key) {
int Address = OAHT_Hash( Key, strlen(Key), HT->TableSize );
int StepSize = OAHT_Hash2( Key, strlen(Key), HT->TableSize );
while( HT->Table[Address].Status != Empty && strcmp( HT->Table[Address].Key , Key) != 0 ) 
{ 
// 1차 해싱후 구한 Address가 이미 점유되어 있고, 
//키 값이 다른 경우 -> 충돌이 일어난 경우 
// 2차 해싱값을 더한 값을 Address 로 사용한다.
Address = (Address + StepSize) % HT->TableSize ;
} 
return HT->Table[Address].Value; 
} 
void OAHT_ClearElement(ElementType* Element)
{
if(Element->Status == Empty) return; 
// Empty인 상태는 아직 Key와, Value가 동적할당되지 않은 상태이므로 free할 필요가 없다.
free(Element->Key); 
free(Element->Value); 
} 
void OAHT_DestroyHashTable(HashTable* HT) {
int i;
for(i=0 ; i< HT->TableSize ; i++) {
OAHT_ClearElement(&(HT->Table[i]));
} 
// Table의 각 요소의 동적할당된 부분을 제거후
// Table 제거 
free(HT->Table);
// 전체 HashTable 제거 
free(HT); 
} 
int OAHT_Hash(KeyType Key, int KeyLength, int TableSize) {
// 1차 해싱 함수
int i; 
int HashValue = 0; 
for(i=0; i<KeyLength ; i++) { 
HashValue = (HashValue << 3) + Key[i];
} 
// 자릿수 접기 
HashValue = HashValue % TableSize; return HashValue;
} 
int OAHT_Hash2(KeyType Key, int KeyLength, int TableSize) { 
// 2차 해싱 함수 - 1차 해싱함수와 같은 값을 갖지 않도록 만듬.
// ~ Cluster 현상과 Collusion 방지
int i; int HashValue = 0;
for(i=0; i<KeyLength ; i++)
{ 
HashValue = (HashValue << 2) + Key[i]; 
} 
// 자릿수 접기 
HashValue = HashValue % (TableSize - 3);
return HashValue + 1; 
} 
void OAHT_Rehash(HashTable** HT) {
int i = 0;
ElementType* OldTable = (*HT)->Table ;
HashTable* NewHT = OAHT_CreateHashTable( (*HT)->TableSize * 2); 
printf(" *** Rehashed... New Table Size : %d\n", NewHT->TableSize ); 
// 이전 Table의 데이터를 새로운 Hash Table의 테이블로 복사 
for(i=0; i < (*HT)->TableSize ; i++) { 
if( OldTable[i].Status == Occupied ) { 
OAHT_Set( &NewHT, OldTable[i].Key , OldTable[i].Value );
} 
} 
OAHT_DestroyHashTable( *HT );
// 이전의 HashTable을 제거한 후 
//HT는 새로운 HashTable을 가리키도록 변경한다.
(* HT) = NewHT;
} 

---------------------------------------------------------------
main.cpp

#include "OpenAddressing.h" 
int main() {
HashTable* HT = OAHT_CreateHashTable(11);
OAHT_Set( &HT, "MSFT", "Microsoft Corporation");
OAHT_Set( &HT, "JAVA", "Sun Microsystems"); 
OAHT_Set( &HT, "REDH", "Red Hat Linux"); 
OAHT_Set( &HT, "APAC", "Apache Org");
OAHT_Set( &HT, "ZYMZZ", "Unisys Ops Check"); 
OAHT_Set( &HT, "IBM", "IBM Ltd.");
OAHT_Set( &HT, "ORCL", "Oracle Corporation");
OAHT_Set( &HT, "CSCO", "Cisco Systems, Inc.");
OAHT_Set( &HT, "GOOG", "Google Inc."); 
OAHT_Set( &HT, "YHOO", "Yahoo! Inc."); 
OAHT_Set( &HT, "NOVL", "Novell, Inc.");
printf("\n"); printf("Key:%s , Value:%s\n", "MSFT", OAHT_Get( HT, "MSFT" ) ); 
printf("Key:%s , Value:%s\n", "REDH", OAHT_Get( HT, "REDH" ) ); 
printf("Key:%s , Value:%s\n", "APAC", OAHT_Get( HT, "APAC" ) );
printf("Key:%s, Value:%s\n", "ZYMZZ", OAHT_Get( HT, "ZYMZZ" ) );
printf("Key:%s , Value:%s\n", "JAVA", OAHT_Get( HT, "JAVA" ) );
printf("Key:%s , Value:%s\n", "IBM", OAHT_Get( HT, "IBM" ) ); 
printf("Key:%s , Value:%s\n", "ORCL", OAHT_Get( HT, "ORCL" ) );
printf("Key:%s , Value:%s\n", "CSCO", OAHT_Get( HT, "CSCO" ) );
printf("Key:%s , Value:%s\n", "GOOG", OAHT_Get( HT, "GOOG" ) ); 
printf("Key:%s , Value:%s\n", "YHOO", OAHT_Get( HT, "YHOO" ) ); 
printf("Key:%s , Value:%s\n", "NOVL", OAHT_Get( HT, "NOVL" ) ); 
OAHT_DestroyHashTable( HT ); 
} 

---------------------------------------------------------------

실행 결과