The Big Picture

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.

This further alludes to the point I've made earlier: 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