Hash Tables and Near-Constant Lookup
A hash table calculates a key's home slot and compares keys using a collision rule. Different keys can share a home slot. With suitable capacity and good key spreading, expected lookup work stays near constant.
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 how key distribution and table occupancy affect expected lookup work, including long chains and probe walks
1 · Read
A hash table stores key-value pairs. A hash function gives a key a number. Its remainder after division by the table size gives the home slot. Slots run from 0 to size minus 1. Lookup starts there and compares keys using a collision rule. With the same hash rule and table size, the same key has the same home slot. Python dictionaries use hashing.
Use this practice rule: uppercase A = 1, B = 2, through Z = 26. Add a key's letter values, then take the remainder after division by the table size. In seven slots, AC has sum 4 and home slot 4. P has sum 16 and home slot 2: 16 = 2 x 7 + 2. B also has home slot 2. Different keys with the same home slot have a collision.
Chaining stores a bucket of pairs at each slot. Here each bucket is a linked list, using the next references you have studied. A distinct colliding key joins that bucket. Lookup compares its keys until finding a match or reaching null. A bucket containing b pairs needs at most b key comparisons. Other buckets are not searched.
Linear probing stores pairs in the slots. Assume no deletions here. Start at the home slot and compare any stored key. A match updates its value; an empty slot accepts a new pair. Otherwise advance one slot, wrapping from the last slot to 0. Lookup follows the same route, stopping at a match or an empty slot. Stop after one full circuit if no slot is empty; a new key then needs more capacity.
Treat hashing and comparing a key as fixed-cost work here. With good key spreading and suitable capacity, expected lookup work stays near constant as more pairs are stored. Crowding can lengthen chains or probe walks. Poor spreading can also cause long chains in a roomy table. One bucket holding every key may require checking them all. Hashing does not sort keys. Python dictionaries preserve insertion order during iteration.
Calculate the home slot, then compare keys along the collision route. Key spreading and capacity affect expected lookup work.
The lesson, questions and flashcards were written for this dataset.
The readings and flashcards were written for this dataset. Video: 'Dictionary hashing' by Khan Academy.
More to read
What a fast lookup still checks
A scoreboard might associate each player name with a score. In an unsorted sequence, finding one player's score may require comparing many names. A hash table calculates a home slot from the name and then follows its collision rule to find a matching key.
The home slot is a starting point. With chaining, it identifies a bucket that may contain several pairs. With probing, the pair may occupy another slot along the probe route. In either case, comparing the stored key with the requested key prevents returning a different player's score.
Expected lookup work can stay near constant as the table grows when keys spread well and capacity remains suitable. This assumes that hashing and comparing a key take fixed work. Processing longer text keys can require more work. Expected cost is also not a worst-case promise: if many keys enter one bucket, a lookup may examine many pairs.
A table can increase its capacity and place existing pairs again using the new size. This can reduce crowding, but cannot guarantee good spreading from a poor hash rule. Hashing itself does not sort keys. A structure can maintain a separate iteration order; Python dictionaries preserve insertion order.
Calculating with keys
A hand calculation needs an exact rule. Use uppercase letters, with A = 1 through Z = 26. Add the letter values and divide the sum by five. Use the remainder as the home slot in a table numbered 0 through 4.
D gives 4, so it starts at slot 4. K gives 11. Since 11 = 2 x 5 + 1, K starts at slot 1. BE gives 2 + 5 = 7, so it starts at slot 2. F gives 6 and also starts at slot 1. K and F are different keys with the same home slot. The collision rule must retain both pairs.
This rule uses the key, not the associated value. Changing a player's score does not change the home slot calculated from that player's unchanged name. Inserting a key already present updates its value rather than adding a second copy of that key.
Repeatability has conditions. The same key receives the same home slot while the hash rule and table size stay unchanged. Changing the table size can change the remainder, so a resized table must place its existing pairs again.
Tracing collisions without losing keys
Consider six slots numbered 0 through 5. For integer keys, use the remainder after division by six. Keys 5 and 11 both have home slot 5.
With chaining, both pairs enter slot 5's bucket. If that bucket uses a linked list, a lookup follows next references and compares keys. It returns the matching value or reports the key absent after reaching null.
With linear probing, suppose key 5 occupies slot 5 and slot 0 is empty. Inserting key 11 checks slot 5, finds a different key and wraps to slot 0. The new pair is stored there. Looking up 11 must follow that route too: compare at 5, then at 0. A different stored key is a reason to continue, not a reason to report absence.
Assume no deletions for this trace. An empty slot ends an unsuccessful lookup. If all slots are occupied, stop after checking one full circuit; do not loop forever. A new distinct key then needs more capacity. Deletion requires an additional rule because clearing a slot carelessly can interrupt later lookups.
No single occupancy threshold suits all collision rules. Both occupancy and key distribution affect how many entries lookup checks.
Explore more
2 · Watch
به انگلیسیTake it off screen
Where it sits
Learn first
Optional connections
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.