뇌를 자극하는 알고리즘 - 8. 해시 테이블 : 체이닝(Chaining)

구현소스

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;
}

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

실행결과