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 http://eternallyconfuzzled.com/tuts/algorithms/jsw_tut_hashing.aspx

 

 

</pre>
class HashTable
{
 typedef long long unsigned int HashValueType;
 typedef int KeyType;
 int BucketSize;
 vector<vector<KeyType>> Buckets;

 void InsertAtBucket(int ValueParam, int BucketId)
 {
 Buckets[BucketId].push_back(ValueParam);
 }
 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;
 Ptr++;
 }
 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;;
 }
public:

HashTable(int BucketSizeParam = 100)
 {
 BucketSize = BucketSizeParam;
 Buckets.clear();
 for (int i = 0; i < BucketSize; i++)
 Buckets.push_back(vector<KeyType>());
 }
 void Insert(int ValueParam)
 {
 //BucketSize
 if (!LookUp(ValueParam))
 InsertAtBucket(ValueParam, HashFunction(&ValueParam,sizeof(int))%BucketSize);
 }

bool LookUp(int ValueParam)
 {
 return FindAtBucket(ValueParam, HashFunction(&ValueParam, sizeof(int))%BucketSize);
 }
};
<pre>
Advertisements

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