Hash Tables and Near-Constant Lookup
Turning a key into a slot number with a hash function, so a value is reached by calculation instead of by searching. Two keys can land in the same slot, and the table needs a rule for what happens when they do.
What a learner can do afterwards
- Apply a small hash function to several keys and place them in a table of slots
- Describe one collision rule, such as chaining or probing, and run it on a clash
- Explain why lookup stays close to constant time until the table gets crowded
1 · Read
A hash table stores key and value pairs in a fixed row of slots. A hash function turns each key into a slot number, so lookup jumps straight to the computed slot instead of searching. The same key always lands in the same slot, which is the whole trick, and a Python dictionary you already know is exactly this structure.
Try a tiny hash by hand: add up the letter positions of a key and take the remainder after dividing by the table size. A key with hash value 10 in a 7 slot table lands in slot 3, since 10 divided by 7 leaves remainder 3. Two different keys can still land in the same slot, and that clash is called a collision.
Every table needs one collision rule. Chaining keeps a small list inside each slot, so clashing keys queue up and lookup scans that short list. Linear probing instead walks forward to the next free slot on insert and repeats the same walk on lookup. Both rules find the key provided the same steps run both times.
Lookup stays close to constant time until the table gets crowded. As slots fill, chains grow long and probe walks stretch far, so the jump stops landing near the answer. Keys also sit in scrambled order, not sorted order, which is the price paid for the speed.
Hash the key, jump to its slot, settle clashes by one fixed rule, and keep the table roomy.
2 · Watch
Take it off screen
Where it sits
8 questions wait behind this lesson, each with its answer explained. Every answer feeds the sky: stars light as they are learned, and dim when it is time to come back.