How does a Hash Table work?

Understand the differences between direct address table and hash table, implement a Hashmap from Scratch

The graphic shows the mapping of the keys to their bucket by using the hash function.

A hash table is a dynamic set that supports the dictionary operations of INSERT, SEARCH, and DELETE with average O(1) time complexity.

How does a hash table work under the hood? Let’s figure it out in this post.

Direct Address Table

To understand a hash table, the direct address table is the first concept we should understand.

direct-address table

The direct address table uses the key directly as an index to a slot in an array. The size of universe keys is equal to the size of the array. It is really fast to access this key in O(1) time because an array supports random access operations.

However, there are four considerations before implementing an direct address table:

1. To be an valid array index, the keys should be integers
2. The universe of the keys is fairly small, otherwise, we will need a giant array.
3. Not two different keys are mapped to the same slot in the…