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
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)
{
if (!LookUp(ValueParam))
InsertAtBucket(ValueParam, HashFunction(&ValueParam,sizeof(int))%BucketSize);
}
bool LookUp(int ValueParam)
{
return FindAtBucket(ValueParam, HashFunction(&ValueParam, sizeof(int))%BucketSize);
}
};