Saturday, March 1, 2014

Hash Table in C++

I have implemented a simple hash-table in C++. I have used the modified version of Bernstein's Hash function for it. For more on the Bernstein's hash, read this



[code language="cpp"]</pre>
class HashTable
typedef long long unsigned int HashValueType;
typedef int KeyType;
int BucketSize;
vector<vector<KeyType>> Buckets;

void InsertAtBucket(int ValueParam, int BucketId)
bool FindAtBucket(int ValueParam, int BucketId)
if (Buckets[BucketId].size() <= 0) return false;
vector<KeyType>::iterator Ptr = Buckets[BucketId].begin();
while (Ptr != Buckets[BucketId].end())
if ((*Ptr) == ValueParam) return true;
return false;
HashValueType HashFunction(void* Input, int Size)
HashValueType HValue = 0;
for (int i = 0; i < Size; i++)
HValue = (33 * HValue) + ((char*)Input)[i];
return HValue;;

HashTable(int BucketSizeParam = 100)
BucketSize = BucketSizeParam;
for (int i = 0; i < BucketSize; i++)
void Insert(int ValueParam)
if (!LookUp(ValueParam))
InsertAtBucket(ValueParam, HashFunction(&ValueParam,sizeof(int))%BucketSize);

bool LookUp(int ValueParam)
return FindAtBucket(ValueParam, HashFunction(&ValueParam, sizeof(int))%BucketSize);

No comments:

Post a Comment


GraphQL What is GraphQL It is a specification laid out by Facebook which proposed an alternative way to query and modify data. Think o...