Skip to main content

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

 

 

[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]

Comments

Popular posts from this blog

GraphQL

GraphQL



What is GraphQL

It is a specification laid out by Facebook which proposed an alternative way to query and modify data. Think of it is an as a complimentary of REST/RPC.

Now head here and read the original graphQL documentation. It will take 2-3 hours tops but is a worthy read. This will help you build some impressions on it and help contrast against mine below:


Why use GraphQL

Core advantage

Instead of defining custom backend rpc/rest endpoints for every data-shape, graphql allows you to build a more general endpoint which give frontend/mobile engineers freedom and query and play with the data. It might be less efficient, add a bit more complexity (need for things like data-loader), harder to standardize and control client-contracts for. What it looses in complexity and control, it gains in flexibility and freedom - provided your data model is worth of a graphql-ish query How to tell if my data-model graphql-ish?Are there complex relationships between your models? Is there a need …

About me

Hi,

I'm currently working as a software developer in the logistics industry in San Francisco. 
My aim is to impact billions of people's live for the better and make the world a better place.

Cheers,
Vignesh



Backend - Tech refresher 2019

Hello there

As a software engineer, it is important to keep updating your skillsets by learning the latest programming-elements (includes paradigms, patterns, languages, tools and frameworks). This becomes a bit easy if you already working on the cutting edge of something. Even then, it is possible to go too deep and loose breadth.

I've taken upon myself to do a tech refresher every year. The intent is to read, experiment and understand these elements by spending anywhere between 4 days to 4 weeks. The ultimate goal is: "do I know most that I need to know to build a planet-scale backend tech-stack ground up"

I'll write up my learnings in posts to help myself (and maybe others) refer it.

Here is the initial list I'm thinking about:


RedisMySQL, GraphQLAurora, Mesos, KubernetesCadence, SWSCassandra, MangoDB, NoSQL, MySQL, Spanner, S<, DynDBELKFlink, Storm, Samza, SparkHadoop HDFS, Yarn, MapReduceHive, HBaseKafka, ZookeeperNW: http, Tcp, thrift, grpc, yarpc, Terraform,…