Chapter 7 · Space and Time Trade-Offs
Hashing Lab
Spend a table of m cells to find keys in about one probe. Watch the same keys go into open hashing (separate chaining) and closed hashing (linear probing and double hashing), and see how the load factor α = n/m decides the cost.
Open hashing · separate chaining
Closed · linear probing
Closed · double hashing
home cell h(K)
probed / compared
written / tombstoned
found
DELETED marker (tombstone)
Expected probes vs load factor α
Curves are the standard average-case estimates (Levitin §7.3; double hashing shown for idealized uniform probing). The vertical line is your table's current α; dots are the measured average probes of a successful search in your tables right now.
Table view of the curves
How to read this
- The hash function
- For a word, K is the sum of its letters' positions in the alphabet (A = 1, …, Z = 26); for an integer, K is the number itself. The home cell is h(K) = K mod m. The line above the tables shows the arithmetic for the current key.
- Open hashing (separate chaining)
- Each cell holds a linked list; colliding keys simply join the list. Search cost = how many list keys you compare. It keeps working even when n > m.
- Closed hashing (open addressing)
- Every key lives in the table itself. On a collision, linear probing tries the next cell (i + 1) mod m; double hashing jumps by its own step s(K) = (m − 2) − (K mod (m − 2)), so keys that collide at home follow different paths. Probes = table cells examined.
- Why tombstones
- Deleting from a closed table leaves a DELETED marker instead of an empty cell. An empty cell would stop later searches too early and “lose” keys that probed past it when they were inserted.
Try this
- Book check. Build the default words with m = 13. The home cells are 1, 9, 6, 10, 7, 11, 11, 12. ARE and SOON collide at 11. Linear probing sends SOON to 12, which pushes PARTED around to cell 0.
- Unsuccessful search. Search for KID (h = 11). Chaining compares it with ARE and SOON; linear probing walks 11, 12, 0, 1, 2 before hitting an empty cell, 5 probes.
- Tombstones. Delete SOON, then search for PARTED. Linear probing still finds it because the DELETED marker at 12 says “keep going”.
- Crowding. Set m = 11 and press Random words a few times with 9–10 keys. With α near 0.9, watch the linear-probing clusters grow and the measured dots climb toward the curves.
- Bad table size. With double hashing, s(K) must share no factor with m. Try m = 12: some keys get a step like 4 or 6 and can cycle through only a few cells. Prime m avoids this.