In this article we are starting by example before digging deeper into hash tables.
suppose a cashier working in a grocery store and need to know the price of an apple, he/she would find the price in a book. If the book is alphabetized he/she would use a simple search which would take O(n) time. And if the book is alphabetized he/she would use binary search to find price of apples which would take O(log n) time.
But what if the cashier is having an assistant, who memorize every item and its price, so it would take O(1) time.
Hash Function
hash function maps a string to a number. So a hash function can play the cashier assistant role, where he/she maps string item to number price.
suppose we are having an array where we store the prices, we would give the hash function the apple price to be stored and the hash function would output number 0 which is the index where the apple price is stored in the array.
Hash Table
It is a complex data structure as it is a combination of a hash function and an array. hash tables consist of key and value.
{"apple": 5, "banana": 3}
you don't have to implement a hash table yourself it is already implemented in most programming languages.
Hash Table Use Cases
Using hash tables for lookup
- the phone contact every name has a number associated to it.
- lookup for IP address that is associated with a web address.
Preventing duplicate entries
- like voting system the same person cannot vote twice.
Using hash table as a cache
- memorizing data instead of requesting it over and over.
Collisions
It is when two keys are assigned to the same slot in memory.
One way to deal with a collision, if multiple keys are assigned to the same slot, start a linked list at this slot.
Performance
In the average case, hash tables have O(1) time complexity of everything!
Top comments (0)