If like me, you have used dictionaries for years without understanding how they work. This is made for you!

What is a hash map and why we invented it?

A Hash Map is a data structure with an average insert and search time of a key in O(1). It is often used to build a dictionary, by associating arbitrary data to keys, allowing to retrieve corresponding data in O(1). To understand how a Hash Map achieves that let visualize and formalize the problem.

In order to have O(1) access time we need to use a vector which support random access in O(1). Random access mean that we can access any…