How to Hash an ascii string using bit folding

So the other day in an interview, I was asked if I knew how to implement a hash table. To my surprise the answer was, “no.” I know how to use them, and I have fuzzy understanding of what’s under the hood. So I thought I’d get on it right away.

So after looking through my old comp sci books, I looked at hash tables and algorithms. Unfortunately I never really understood the math behind their explanations, so after feeling a bit frustrated I went ahead on Youtube and found this great video that sums it all up.

Hashing Lorem Ipsum
We’re going to hash the string ‘lorem ipsum dolor’ into a 32 bit integer.

Things to know off the bat. 
* ascii characters are 1 byte each (that’s 8 bits)
* integers are 32 bits

So the letters:
l — 01101100
o — 01101111
r — 01110010
e — 01100101

“folding” our bytes together (right to left) we get:
01100101011100100110111101101100
This translates to a integer value of 1701998444

The next four characters will be m space i p, which yield the value: 
1885937773

Integer math adding these we get:
-707031079

Continue on with the rest of the characters and we get the value:
17006390818

This is now our hash value that we get for the string.

Hope this helps. This is a simple hash function for strings that can be used to index their table.

Till next time,
Ed

Like what you read? Give Ed Huang a round of applause.

From a quick cheer to a standing ovation, clap to show how much you enjoyed this story.