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