뇌를 자극하는 알고리즘 - 8. 해시 테이블 : 개방 주소법(Open Addressing Hash Table)

구현 소스

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

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

실행 결과