Hash Table

앞으로 조금씩 자료구조를 연재할 계획이다.

물론, 간단하게 조금씩 구현할 계획이다...

언어는 C++ 또는 Java가 될거같다.

오늘은 Hash Table이다.

Hash Table에 관한 이론은 Wiki와 블로그로...

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

http://egloos.zum.com/sweeper/v/925740

구현 언어는 C++이다.

/* myHashTable.h */
#pragma once
#include 

using namespace std;

unsigned __int32 jenkins_one_at_a_time_hash(char *key, size_t len)
{
	unsigned __int32 hash, i;
	for (hash = i = 0; i < len; ++i)
	{
		hash += key[i];
		hash += (hash << 10);
		hash ^= (hash >> 6);
	}
	hash += (hash << 3);
	hash ^= (hash >> 11);
	hash += (hash << 15);
	return hash;
}
// Robert Jenkins' 32bit hash function
unsigned __int32 Fhash(unsigned __int32 key)
{
	key += (key << 12);
	key ^= (key >> 22);
	key += (key << 4);
	key ^= (key >> 9);
	key += (key << 10);
	key ^= (key >> 2);
	key += (key << 7);
	key ^= (key >> 12);

	return key;
}

template < typename K, typename V >
class HashEntry
{
private:
	K key;
	V value;
public:
	HashEntry(K _key, V _value){
		key = _key;
		value = _value;
	}
	K getKey(){
		return key;
	}
	V getValue(){
		return value;
	}
};
const int TABLE_SIZE = 128;
template < typename K, typename V >
class myHashTable
{
private:
	HashEntry< K, V >** table;
public:
	myHashTable(){
		table = new HashEntry< K, V >*[TABLE_SIZE];
		for (int i = 0; i < TABLE_SIZE; i++)
			table[i] = NULL;
	}
	~myHashTable(){
		for (int i = 0; i < TABLE_SIZE; i++)
		if (table[i] != NULL)
			delete table[i];
		delete[] table;
	}
	V get(K _key){
		int KEY = validateKEY(_key);
		
		int _hash = Fhash(KEY) % TABLE_SIZE;
		while (table[_hash] != NULL && table[_hash]->getKey() != _key)
			_hash = (_hash + 1) % TABLE_SIZE;
		if (table[_hash] == NULL)
			return -1;
		else
			return table[_hash]->getValue();
	}
	void put(K _key, V _value){
		int KEY = validateKEY(_key);

		int _hash = Fhash(KEY) % TABLE_SIZE;
		while (table[_hash] != NULL && table[_hash]->getKey() != _key)
			_hash = (_hash + 1) % TABLE_SIZE;
		if (table[_hash] != NULL)
			delete table[_hash];
		table[_hash] = new HashEntry< K, V >(_key, _value);
	}
	bool isEmpty(){}
	bool isFull(){}
	void clear(){}
	void showStructure(){}
private:
	int validateKEY(K _key)
	{
		if (is_same< K, string >::value)
			;// return cHash(dynamic_cast(_key));
		else
			return (int)_key;
	}
	int cHash(string *str)
	{
		int val = 0;

		for (int i = 0; i < str.length(); i++)
			val += str[i];
		return val;
	}
};

/* main.cpp */
#include 
#include "myHashTable.h"

int main()
{
	myHashTable< int, int > test;

	test.put(0, 5);
	test.put(2, 55);

	printf("%d\n", test.get(0));
	printf("%d\n", test.get(2));

	return 0;
}