Hash function & Hash Table

Short & Sweet series — part 4

3 min readApr 25, 2020

Following the COVID-19 crisis that requires me to stay at home these days, I use the free time to promote myself to the goal of expert Front End developer. As part of my learning process, I try to share once a week an exciting thing that I learn.

I hope this experience will help you and me to keep learning new things even during these difficult days.❤️

A hash table, also known as hash map and dictionary, is a data structure that stores information in a key-value model. The reason that hash tables are so popular is the low time complexity of O(1) for the actions of insert, get, and delete.

This Incredible Complexity Is Made Possible By a Simple Process:

Get a key, value element.
Convert the key to a unique hash value with a hash function.
Use the hash value as an index in an array.

Convert key, value to a hash table — flow.

When we would like to get a specific value from the array, the only thing we need to do is to go to the cell that has the same index as the hash value of our key.

Time Complexity Of Hash Table:

How not? A video of Brian Kernighan explains Hash Table:

Hash Table In Different Languages:

Java: The interface Map (common implementation is HashMap).
JavaScript: The class Map.

Hash Function

The hash function is used for mapping data from arbitrary size into a fix sized value, for example, representating an object or a string as an integer value.

Hash Functions In Different Languages:

Java: came as part of the Object’s methods.

JavaScript: in JS, there is no implementation to hash function because it comes transparently with Map.

The Hash Function Is Irreversible:

For each input, you have exactly one output, but not the other way around. Multiple inputs yield the same output.

For example:

On Java, the value of “Hello World”.hashCode() is -862545276, but this value could be produced by other Strings also. Therefore, we cannot know what was the original value represented by the output of the hash function.

Collision

Collision is a situation that more than one different inputs return the same hash value. It can be solved by implementing the array so the value of each hash index will be a linked list that will store the values that have the same hash value.

Linke to other articles from this series:

Final Words

I hope you’ve enjoyed this article and learned new things.
If you like this post, I would appreciate applause and sharing :-)
If you have something to add or change I would love to hear ❤️

Who Am I?
My name is Michal Porag. I am a Full-Stack Developer working at Skillset and a Computer Science student at The Open University.

You can contact or follow me:
Twitter

My Youtube Chanel
Facebook
LinkedIn