Hash Table

A hash table or hash map is essentially a key, value pair. The simplest way to think about a hash table is to imagine a row of houses in a neighborhood and a watchman for the neighborhood. You only know the names of the people in the neighborhood, but not their houses. You ask the watchman, where Mr. Zuckerberg lives and he points to house number 5. Next, you ask him where Mr. Gates lives and he points to house number 2. A hash table is similar in the sense that we'll give the data-structure a key, and it will map our key to a slot where we can then place our value.

The watchman maintains the mapping in his head, and the hash table will use a hash function to compute the mapping. Just like the watchman, the hash function will always point to the same slot when given the same key.

Array as a Hash Table

Let's say we are given a string of lowercase English-alphabet characters and are asked to find the frequency of each character in the given string. We can use an array of integers to act as our hash table.