How does a hash table store items?

1the puzzle

An array is fast because you ask for slot four and get it, no searching. But how do you ask for the word cat, without checking every slot?

2the hash

The trick: turn the word into a number. Add the letter codes: c is 99, a is 97, t is 116. That makes 312. Divide by 8 slots; the remainder, 0, is its slot.

3filling in

Same recipe for every key. Dog adds up to 314, remainder 2. Bee adds up to 300, remainder 4. Each word is written straight into its own slot.

4collision

And to find a word later, run the same math and jump straight to the slot. But owl adds up to 338, remainder 2. Slot two is taken. That is a collision.

5chaining

Fix one is chaining: each slot holds a little list. Dog and owl both live in slot two, linked in a row. Lookup jumps to slot two and walks that short list.

6probing

Fix two is open addressing: everything stays in the array itself. Owl finds slot two taken, so it tries slot three, which is empty, and settles there.

7too full

A crowded table slows both fixes. So count items divided by slots, the load. Java's HashMap starts with sixteen slots and doubles at about three quarters full; Python's dict, near two thirds.

8the whole idea

So the whole idea: hash the key, take the remainder, land in a slot. Lookup is one step on average, but not guaranteed: if everything hashes to one slot, you scan it all.