The Big Picture

  • Describe the general idea behind the hash table.

The fundamental idea behind Hash Table is to map each key (entry) to a position (an array index) based on the key itself.

Imagine I have this mystery function that can map keys to array indices:

So when I give it "cat," it would give me $1$, and when I give it "dam," it would give me $9$, $\dots$:

Using this mystery function, I know exactly where to insert each element (and therefore where exactly to look for it). The cost of insertion and search will essentially be the cost of running the mystery function.

Note that we access an entry based on its key (associative retrieval), not its location (so no need to, e.g., search for the key in a tree).

Resources
  • Wikipedia's entry on Hash Table.
  • Robert Nystrom's book "Crafting Interpreter" has a chapter on Hash Tables.