A hash table organises data so you can quickly look up values for a given key

Complexity analysis

Strengths

Weaknesses

Hash maps are built on arrays

Arrays are pretty similar to hash maps already. Arrays let you quickly look up the value for a given "key" except the keys are called "indices," and we don't get to pick them — they're always sequential integers (0, 1, 2, 3, etc).

Think of a hash map as a "hack" on top of an array to let us use flexible keys instead of being stuck with sequential integer "indices."

All we need is a function to convert a key into an array index (an integer). That function is called a hashing function.

https://s3-us-west-2.amazonaws.com/secure.notion-static.com/305a2b01-3aa3-43ee-927a-ef40ad9ca225/Untitled.png

To look up the value for a given key, we just run the key through our hashing function to get the index to go to in our underlying array to grab the value.

How does that hashing method work? There are a few different approaches, and they can get pretty complicated. But here's a simple proof of concept:

Grab the number value for each character and add those up.

https://s3-us-west-2.amazonaws.com/secure.notion-static.com/82b231e3-ba68-48d6-a1d3-5667e3f12f56/Untitled.png