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
[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)
{
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>
[/code]
Subscribe to:
Post Comments (Atom)
GraphQL
GraphQL What is GraphQL It is a specification laid out by Facebook which proposed an alternative way to query and modify data. Think o...
-
Hi, I'm currently working as a software developer in the logistics industry in San Francisco. My aim is to impact billions of pe...
-
GraphQL What is GraphQL It is a specification laid out by Facebook which proposed an alternative way to query and modify data. Think o...
-
DHCPerf is an open source load testing tool for DHCP-Server setups. The tool is capable of generating DHCP Client traffic with a customizabl...
No comments:
Post a Comment