뇌를 자극하는 알고리즘 - 8. 해시 테이블 : 나눗셈법으로 구현된 간단한 해시 테이블

구현소스

SimpleHashTable.h

#ifndef SIMPLE_HASH_TABLE
#define SIMPLE_HASH_TABLE
// 간단한 나눗셈법으로 구현한 Hash Table

#include <stdio.h>
#include <stdlib.h>

typedef int KeyType;
typedef int ValueType;

typedef struct tagNode
{
	KeyType Key;
	ValueType Value;
} Node;

typedef struct tagHashTable
{
	int TableSize;
	Node* Table;
} HashTable;

HashTable*	SHT_CreateHashTable(int TableSize);

void		SHT_Set(HashTable* HT, KeyType Key, ValueType Value);
// SHT_Hash 함수를 통해 Key에 따른 Index를 얻고 Value를 저장한다.

ValueType	SHT_Get(HashTable* HT, KeyType Key);
// SHT_Hash 함수를 통해 Key에 따른 Index를 얻고 그에 따른 Value를 return 한다.

void		SHT_DestroyHashTable(HashTable* HT);

int			SHT_Hash( KeyType Key, int TableSize);
// Key % TableSize가 Value를 저장하는 Index가 된다.

#endif

--------------------------------------------------------------------
SimpleHashTable.cpp

#include "SimpleHashTable.h"

HashTable* SHT_CreateHashTable(int TableSize)
{
	HashTable* HT = (HashTable*) malloc( sizeof(HashTable) );

	HT->Table = (Node*) malloc( sizeof(Node) * TableSize );
	HT->TableSize = TableSize;
	return HT;
}

void SHT_Set(HashTable* HT, KeyType Key, ValueType Value)
{
	int Adress = SHT_Hash( Key, HT->TableSize );

	HT->Table[Adress].Key = Key;
	HT->Table[Adress].Value = Value;

}

ValueType SHT_Get(HashTable* HT, KeyType Key)
{
	int Adress  = SHT_Hash( Key,HT->TableSize );

	return HT->Table[Adress].Value ;


}
void SHT_DestroyHashTable(HashTable* HT)
{
	free( HT->Table );
	free( HT );
}

int	SHT_Hash( KeyType Key, int TableSize)
{
	return Key % TableSize;
}

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

main.cpp

#include "SimpleHashTable.h"

int main()
{
	HashTable* HT = SHT_CreateHashTable( 193 );
	// 나눗셈법으로 구현하는 HashTable에서는 Table size를 소수로 하는게 좋다.
		
	SHT_Set(HT, 311, 1);
	SHT_Set(HT, 103, 2);
	SHT_Set(HT, 352, 3);
	SHT_Set(HT, 500, 4);
	SHT_Set(HT, 777, 5);

	printf(" - Key : %d, Value : %d [ index : %3d ] \n", 311, SHT_Get(HT,311), 311%193 );
	printf(" - Key : %d, Value : %d [ index : %3d ] \n", 103, SHT_Get(HT,103), 103%193 );
	printf(" - Key : %d, Value : %d [ index : %3d ] \n", 352, SHT_Get(HT,352), 352%193 );
	printf(" - Key : %d, Value : %d [ index : %3d ] \n", 500, SHT_Get(HT,500), 500%193 );
	printf(" - Key : %d, Value : %d [ index : %3d ] \n", 777, SHT_Get(HT,777), 777%193 );


	return 0;
}

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

실행결과