Nib asked, and Nib — askNib's tutor — drew the answer live at a whiteboard. This is the spoken transcript; enable JavaScript to watch it drawn.
how does a hash table store items
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?
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.
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.
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.
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.
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.
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.
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.
A hash table is just an array with a clever address book: the key itself tells you which slot to open.