Resource Lookup with Custum HashTable

When working on my OpenGL tech demo, i needed to look up resources that were loaded, sources such as models, shaders or cube maps. I did this using std::map. When starting to work on my games fleadh game from scratch again i wanted to change how i did resource look up. I decided to roll my own hash table along with create my own hash function  using fvn-1a.

Hash class here.

#ifndef HASH_MAP_H
#define HASH_MAP_H

#include "HashID.h"
#include <iostream>

template <class T>
class HashTable
{
public:
	HashTable();
	~HashTable();

	unsigned int HashIndex(HashID hashID);
	void Insert(HashID hashID, T value);
	T* Find(HashID hashID);
	void Remove(HashID hashID);
	// Calculate the number of items in list giving at a index.
	unsigned int SizeOfBucket(int index);

private:
	static const unsigned int TABLE_SIZE = 4;

	struct Item
	{
		HashID hashID;
		T value;
		Item *next;
	};

	Item* hashTable[TABLE_SIZE];
};

// --- Implementation Here ---

The constuctor and deconsontror

template <class T>
HashTable<T>::HashTable()
{
	for (int i = 0; i < TABLE_SIZE; i++) 	{ 		hashTable[i] = new Item; 		hashTable[i]->hashID.hashID = 0x00000000;
		//hashTable[i]->value = 0;
		hashTable[i]->next = NULL;
	}
}

template <class T>
HashTable<T>::~HashTable()
{
	Item *ptr = NULL;
	Item *curr;
	for (int i = 0; i < TABLE_SIZE; ++i) 	{ 		ptr = hashTable[i]; 		if (ptr == NULL) 			continue; 		while (ptr->next != NULL)
		{
			curr = ptr;
			ptr = ptr->next;
			delete curr;
		}
	}
}

Finding the index from a hash value

template <class T>
unsigned int HashTable<T>::HashIndex(HashID hashID)
{
	int index = hashID.hashID % TABLE_SIZE;

	return index;
}

Inserting a value into the hash table

template <class T>
void HashTable<T>::Insert(HashID hashID, T value)
{
	int index = HashIndex(hashID);

	if (hashTable[index]->hashID.GetValue() == 0x00000000)
	{
		hashTable[index]->hashID = hashID;
		hashTable[index]->value = value;
	}
	else
	{
		Item *ptr = hashTable[index];
		Item *n = new Item;
		n->hashID = hashID;
		n->value = value;
		n->next = NULL;

		while (ptr->next != NULL)
		{
			ptr = ptr->next;
		}
		ptr->next = n;
	}
}

Finding an value giving a hashID

template <class T>
T* HashTable<T>::Find(HashID hashID)
{
	int index = HashIndex(hashID);
	T *value = new T;

	Item *ptr = hashTable[index];
	while (ptr != NULL)
	{
		if (ptr->hashID.hashID == hashID.hashID)
		{
			*value = ptr->value;
		}
		ptr = ptr->next;
	}

	return value;
}

Remove an item from the table

template <class T>
void HashTable<T>::Remove(HashID hashID)
{
	int index = HashIndex(hashID);

	Item *ptr = hashTable[index];

	if (!ptr)
	{
		std::cout << "There is no matching hash value to remove." << std::endl; 		return; 	} 	if (ptr->hashID == hashID && ptr->next == NULL)
	{
		std::cout << hashID.GetValue() << " hash ID removed" << std::endl; 		delete ptr; 	} 	Item *currentNode; 	while (ptr->next != NULL)
	{
		currentNode = ptr;
		ptr = ptr->next;
		if (ptr->hashID == hashID)
		{
			currentNode->next = ptr->next;
			std::cout << hashID.GetValue() << " hash ID removed" << std::endl;
			delete ptr;
		}
	}
}

Printing the size of a bucket or the size of items at the top of a tree node.

template <class T>
unsigned int HashTable<T>::SizeOfBucket(int index)
{
	int count = 0;

	if (hashTable[index]->hashID.GetValue() == 0x00000000)
	{
		return count;
	}
	else
	{
		count++;
		Item* ptr = hashTable[index];
		while (ptr->next != NULL)
		{
			count++;
			ptr = ptr->next;
		}
	}

	return count;
}

Link to source: Link

Posted in C++

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s