§3Exercises
Ten exercises in four layers: three proofs, two designs, three implementations with milestones, and two read-the-code. Proofs and designs are the same in both languages; the implementation exercises come as templates in PythonJava with tests that fail on purpose, and your job is to make every test pass. Try each exercise before you open its solution.
| # | Layer | Topic | Video |
|---|
| 1 | Proof | Expected chain length under uniform hashing | 2 |
| 2 | Proof | Quadratic probing and the size of the table | 3 |
| 3 | Proof | Rehashing costs O(1) per put on average | 4 |
| 4 | Design | A hash code for a composite key | 1 |
| 5 | Design | Deleting from an open-addressing table | 3 |
| 6 | Implement | Hash codes, compression and measuring a hash | 1 |
| 7 | Implement | A chained hash map with rehashing | 2, 4 |
| 8 | Implement | Linear probing with tombstones | 3 |
| 9 | Read the code | An AI-written key class | 1 |
| 10 | Read the code | An AI-written probing map | 3 |
PROOFS
Exercise 1 · Expected chain length. Simple uniform hashing: every key goes to each of the m buckets with probability 1/m, independently of the other keys. n keys are stored by separate chaining, a new key is appended at the end of its chain, and α = n/m is the load factor. (a) Prove that the expected length of any given bucket is α. (b) An absent key is searched; its bucket is uniformly random. Show that the expected number of key comparisons is α (it walks the whole chain), so the cost is Θ(1 + α) with the hash computation. (c) A stored key, chosen uniformly among the n stored keys, is searched. Show that the expected number of comparisons is exactly 1 + (n − 1)/(2m), which is less than 1 + α/2. (Hint: the key inserted j-th is preceded in its chain by each of the j − 1 earlier keys with probability 1/m.) (d) Evaluate (a)–(c) for the map of video 2 (n = 10 keys, m = 7 buckets) and compare with what the video measured: chain lengths 0, 0, 3, 1, 3, 1, 2, and 17 comparisons for finding each of the ten keys once (1.70 on average). Also compute the expected number of empty buckets, m(1 − 1/m)ⁿ, and compare it with the two empty buckets of the video. Is one measurement that differs from an expectation a contradiction?
Solution
(a) Let Xₖ = 1 if key k is in the given bucket, else 0. Then P(Xₖ = 1) = 1/m, and the length of the bucket is X₁ + … + Xₙ, so by linearity of expectation E[length] = n · (1/m) = α. (No independence is needed for this step.) ∎
(b) The absent key hashes to a uniformly random bucket, independently of the stored keys, and a failed search compares it with every key of that chain, so the expected number of comparisons is E[length of a random bucket] = α. This holds for any set of stored keys, because the average of the m chain lengths is n/m whatever they are. With the hash computation and the index the cost is Θ(1 + α). ∎
(c) Number the keys 1, …, n in the order of insertion. A successful search for key j compares it with the keys before it in its chain and then with itself: 1 + (the number of earlier keys i < j in the same bucket) comparisons. Each earlier key shares the bucket with probability 1/m, so the expectation is 1 + (j − 1)/m. Choosing j uniformly: (1/n) Σⱼ (1 + (j − 1)/m) = 1 + (1/(nm)) · n(n − 1)/2 = 1 + (n − 1)/(2m) = 1 + α/2 − α/(2n) < 1 + α/2. (Checked exactly, by enumerating all mⁿ assignments for small n and m, in test_ex7_claims.pyEx7ClaimsTest.java.) ∎
(d) n = 10, m = 7, α = 1.43. (a) A bucket holds 10/7 = 1.43 keys on average (the video's chain lengths 0, 0, 3, 1, 3, 1, 2 add up to 10: this holds for any ten keys). (b) An absent key costs 1.43 comparisons on average (3 for the key 9 of the video, which is one particular bucket). (c) A stored key costs 1 + 9/14 = 1.643 on average (the rule of thumb 1 + α/2 gives 1.714; the video quotes 1.71). The video measured 17/10 = 1.70: the chains of 3, 1, 3, 1, 2 keys cost 6 + 1 + 6 + 1 + 3 = 17 comparisons. The expected number of empty buckets is 7 · (6/7)¹⁰ = 1.50; the video has two. These are not contradictions: an expectation is an average over all possible key sets, and the video shows one set of ten keys, whose chains are a little uneven (two chains of 3). A Monte Carlo experiment with random buckets (60,000 trials, test_monte_carlo_agrees) gives averages that match 1.643, 1.43 and 1.50 to within 0.02; it is the average over many tables that obeys the formulas, and that is why a table is run at a load factor below 1: a chain of length 3 or 4 is normal and costs nothing.
Exercise 2 · Quadratic probing and the size of the table. Quadratic probing looks at the slots (h + i²) mod m for i = 0, 1, 2, …, where h is the home slot of the key. (a) For m = 12 and for m = 16, which slots does the probe sequence of a key with home slot 0 ever visit? What does that mean for the table when most slots are still free? (b) Let p be an odd prime. Prove that the first (p + 1)/2 probes (i = 0, 1, …, (p − 1)/2) visit (p + 1)/2 different slots. (Hint: if i² ≡ j² (mod p), then p divides (j − i)(j + i).) (c) Conclude: in a table of p slots with fewer than (p + 1)/2 slots occupied (a load factor below about ½), a new key is always stored within the first (p + 1)/2 probes. (d) The bound of (c) is sharp. For p = 13, find a set of 7 occupied slots such that a new key with home slot 0 can never be stored, although 6 slots are free.
Solution
(a) The probe sequence of a key with home slot 0 is i² mod m, and for m = 12 the squares are 0, 1, 4, 9, 16 → 4, 25 → 1, 36 → 0, 49 → 1, 64 → 4, 81 → 9, 100 → 4, 121 → 1, then the pattern repeats: the visited slots are {0, 1, 4, 9} and no others. For m = 16 the squares mod 16 are again {0, 1, 4, 9}. A key with home slot h only ever reaches h, h + 1, h + 4 and h + 9. So if those four slots are occupied the key cannot be inserted, although the table is mostly free: with a composite table size quadratic probing may fail long before the table is full. (13 is better: its squares reach seven slots, see (d).)
(b) Let 0 ≤ i < j ≤ (p − 1)/2 and suppose i² ≡ j² (mod p). Then p divides j² − i² = (j − i)(j + i). Here 1 ≤ j − i ≤ (p − 1)/2 < p and 1 ≤ j + i ≤ (p − 3)/2 + (p − 1)/2 = p − 2 < p, so p divides neither factor; but a prime that divides a product divides one of its factors, a contradiction. Hence the squares i² mod p for i = 0, …, (p − 1)/2 are pairwise different: those are (p + 1)/2 different slots. (Checked for every odd prime below 400.) ∎
(c) The first (p + 1)/2 probes of a key visit (p + 1)/2 different slots. If fewer than (p + 1)/2 slots are occupied (with tombstones counting as occupied for this purpose, because an insert may reuse a tombstone but a search may not stop at it), at least one of the probed slots is free, so the insert succeeds within (p + 1)/2 probes: quadratic probing on a prime-sized table is safe up to a load factor of about ½. (Verified for every set of (p − 1)/2 occupied slots for p = 3, 5, 7, 11, 13.) ∎
(d) For p = 13 the squares of 0, 1, …, 6 are 0, 1, 4, 9, 16 → 3, 25 → 12, 36 → 10: the seven slots {0, 1, 3, 4, 9, 10, 12}; and (13 − i)² = i² (mod 13), so i = 7, …, 12 repeat the same seven slots. Occupy these seven slots: a new key with home slot 0 probes only them, so it can never be stored, although the six slots 2, 5, 6, 7, 8 and 11 are free. The load factor is 7/13 = 0.54, just above the bound of (c). ∎
Exercise 3 · Rehashing costs O(1) per put on average. A chained map starts with m₀ buckets and, whenever a put makes the size exceed λ·m (λ is the maximum load), builds a table of at least twice as many buckets (the next prime above 2m) and re-inserts every entry; each re-insertion is a move. (a) Prove that n puts cause fewer than 2n + R moves, where R is the number of rehashes, and that R = O(log n). So the amortized cost of a put is O(1), as for the dynamic array of chapter 1. (b) Check (a) against the experiment of video 4: 1,000 puts, a start with 7 buckets, λ = 0.75, 7 rehashes and 984 moves. At which sizes did the rehashes happen? (c) Suppose the table grows by a fixed 100 buckets instead of doubling. Show that the number of moves for n puts is about n²/(2λ·100); evaluate it for n = 1,000 and λ = 0.75, and compare with 984. What happens to the number of moves when n doubles? (d) With λ = 0.5 instead of 0.75, does (a) still hold? What do you pay, and what do you get?
Solution
(a) Let the capacities be m₀ < m₁ < … < m_R with m_{r+1} ≥ 2m_r. The r-th rehash (r = 1, …, R) happens in a table of capacity m_{r−1} when the size reaches ⌊λ·m_{r−1}⌋ + 1, and moves that many entries. Hence the total number of moves is Σᵣ (⌊λ·m_{r−1}⌋ + 1) = Σᵣ ⌊λ·m_{r−1}⌋ + R. Because the capacities at least double, λ·m_{R−1−t} ≤ λ·m_{R−1}/2ᵗ, so Σᵣ ⌊λ·m_{r−1}⌋ ≤ λ·m_{R−1} · (1 + ½ + ¼ + …) < 2λ·m_{R−1}. The last rehash happened at size ⌊λ·m_{R−1}⌋ + 1 ≤ n, so λ·m_{R−1} < n. Altogether moves < 2n + R. And m_{R−1} ≥ 2^{R−1}·m₀ with λ·m_{R−1} < n gives R ≤ log₂(n/(λ·m₀)) + 1 = O(log n). So the amortized cost of a put is < 2 + R/n = O(1). (The bound is checked for every n below 3,000.) ∎
(b) The rehashes of video 4 happened when the sizes 6, 13, 28, 60, 123, 249 and 505 were reached (the table had 7, 17, 37, 79, 163, 331 and 673 buckets and grew to 17, 37, 79, 163, 331, 673 and 1,361), so R = 7 and the moves are 6 + 13 + 28 + 60 + 123 + 249 + 505 = 984 < 2 · 1,000 + 7. The last rehash moved 505 entries, about half of all moves, exactly as the geometric sum predicts.
(c) With a growth of c = 100 buckets the r-th rehash happens at about λ(m₀ + c(r − 1)) entries and moves that many, and R ≈ n/(λc) rehashes are needed, so the number of moves is about Σᵣ λcr ≈ λc·R²/2 = n²/(2λc). For n = 1,000, λ = 0.75, c = 100 the formula gives 6,667; the exact count (rehashes at 6, 81, 156, …, 981 entries, 14 of them: 14 · 6 + 75 · (0 + 1 + … + 13) = 84 + 6,825) is 6,909, seven times as many as the 984 of doubling, and for n = 2,000 it is 26,487: doubling n multiplies the cost by about 4. A fixed growth step makes a put cost Θ(n) on average, a growth factor keeps it Θ(1): the same lesson as for the dynamic array.
(d) Yes: (a) never used the value of λ, only that every table is at least twice as large as the one before, so moves < 2n + R still holds. With λ = 0.5 the same 1,000 puts need 8 rehashes and 1,338 moves (final capacity 2,729, load factor 0.37), against 7 rehashes and 984 moves for λ = 0.75 (final load 0.73). So you pay more moves, and about twice the memory, and in return get shorter chains (expected 1 + α/2 comparisons for a successful search, about 1.2 instead of 1.4) and, for open addressing, far fewer probes (video 3). A larger λ such as 0.9 gives 1,180 moves here (7 rehashes) but, for linear probing, long probe sequences (video 3's table: 51 probes for a miss at load 0.9).
DESIGNS
Exercise 4 · A hash code for a composite key. The points (x, y) of a 100 × 100 grid (0 ≤ x, y < 100, so 10,000 points) are the keys of a map; equality compares x and y. The table has m = 10,007 buckets (a prime). (a) Four colleagues propose the hash codes h = x + y, h = x xor y, h = 31·x + y (this is what Objects.hash(x, y) computes, up to a constant: 31·(31 + x) + y) and h = 100·x + y. Predict which are good. Then run ex7_designs.grid_stats (or Ex7Designs.gridStats) in solutions/, which reports the number of distinct hash codes, the length of the longest bucket and the number of empty buckets, and explain every row. (b) State a recipe for hashing a key with several fields: which fields go in (and why the same ones as in equals), how to combine them, what to avoid. (c) Why is 100·x + y perfect on this grid but a poor design in general? What would you use for coordinates of unknown range?
Solution
(a) The results for 10,000 points in 10,007 buckets (test_hash_codes_of_a_100_by_100_grid_in_10007_buckets, also in Java):
| hash code | distinct codes | longest bucket | empty buckets |
|---|
| x + y | 199 | 100 | 9,808 |
| x xor y | 128 | 100 | 9,879 |
31·x + y (= Objects.hash(x, y) − 961) | 3,169 | 4 | 6,838 |
| 100·x + y | 10,000 | 1 | 7 |
| 1,000,003·x + y (extra row) | 10,000 | 2 | 2,857 |
x + y takes only the values 0 … 198, so the 10,000 points share 199 codes and the 100 points of the anti-diagonal x + y = 99 land in one bucket: one chain holds 100 entries. x xor y is worse still, 128 codes (it is below 128), and it is 0 for all 100 points with x = y. 31·x + y: (x, y) and (x + 1, y − 31) have the same code (31 · 3 + 40 = 31 · 4 + 9), because y ranges over 100 values but the multiplier is only 31; each code is shared by up to 4 points, only 3,169 codes exist, and 6,838 buckets stay empty, yet the longest chain is a modest 4. 100·x + y gives every point its own code (it is the position in the grid) and the prime table size keeps them apart: a perfect hash for this grid. Note that Objects.hash(x, y) is 31·(31 + x) + y = 31·x + y + 961, so a small grid behaves exactly like the third row.
(b) Recipe: (1) include exactly the fields that equals compares, no more (a field that equals ignores breaks the contract, Exercise 9) and no fewer (leaving one out is legal but collides every pair that differs only in it); (2) combine them in a way that depends on the position of each field, the polynomial rule h = 31·h + hash(field) for each field in turn (Objects.hash and Arrays.hashCode do exactly this): sums and xors are symmetric, so (x, y) and (y, x) collide, and they stay inside a small range; (3) use all 32 bits (int wrap-around is fine) and compress with a (floor) mod by a prime; (4) never hash a mutable field of a key that is stored in the table (video 1).
(c) 100·x + y works only because we know that y < 100: it is a perfect hash for this range, and (x, 100) would collide with (x + 1, 0). For a general design the range is unknown, so use a multiplier that is large and odd (such as 1,000,003, last row: all 10,000 codes differ and only a few pairs share a bucket) or a library hash; a mixing step on the result helps for patterns like grids, where neighbouring keys have neighbouring codes.
Exercise 5 · Deleting from an open-addressing table. Linear probing, m slots, int keys. (a) Show with the table of video 3 (13 slots, keys 18, 41, 22, 44, 59, 32, 31, 73 inserted in this order) why "delete = empty the slot" is wrong (delete 44, look for 32). Describe the tombstone scheme: what get, put and remove do with a tombstone, and when the table has to be rebuilt (do tombstones count toward the load factor?). (b) There is a second scheme for linear probing that leaves no tombstones. After emptying the slot i, scan the slots j = i + 1, i + 2, … (cyclically) up to the first empty slot. An entry at j whose home slot lies cyclically in (i, j] stays; any other entry is moved into the hole at i and the hole becomes j. State the invariant that makes this correct, prove that it is preserved, and apply the procedure to delete 44 from the table of video 3. (c) Compare the two schemes (cost of a delete, effect on later searches, memory, simplicity). Does (b) work for quadratic probing and double hashing?
Solution
(a) In the table [-, -, 41, -, -, 18, 44, 59, 32, 22, 31, 73, -] the key 32 has home slot 32 mod 13 = 6 but sits in slot 8, because 44 was in slot 6 when it was inserted. Emptying slot 6 to delete 44 makes get(32) stop at the empty slot 6 (probes [6]) and answer "missing" although 32 is in slot 8; with a tombstone it probes [6, 7, 8] and finds it (video 3, and test_remove_leaves_a_tombstone_and_get_skips_it). Tombstone scheme: remove turns the slot into DELETED; get and remove treat DELETED as "occupied by something else" (skip it, never match it) and stop only at an EMPTY slot or after m probes; put of a new key probes until an EMPTY slot (to be sure the key is not further along) and stores the entry in the first tombstone met, otherwise in the empty slot; put of an existing key updates it. Because searches stop only at EMPTY slots, tombstones count toward the load: the rebuild condition is (entries + tombstones) > λ·m, and the rebuild (a rehash into a fresh table of the same or a larger size) drops all tombstones. Without it a table that has seen many removals ends up with no empty slot, and every unsuccessful search walks the whole table (Exercise 10).
(b) Invariant I: for every stored key k at slot s, all slots from home(k) to s (cyclically) are occupied. Search is correct exactly when I holds: a search from home(k) walks along occupied slots to k. Deleting key x at slot i: empty slot i; this can break I only for entries whose path from home to their slot crosses i, and those lie after i in the same run of occupied slots (before the first empty slot e). Scan j = i + 1, … until the first empty slot. For the entry at j with home h: if h lies in (i, j] (cyclically), its path starts after i, so it does not cross the hole: leave it. Otherwise the path from h to j contains i (h is at or before i): move the entry to i; its new path h → i is a prefix of the old path and all of its slots are occupied (i is now filled), so I holds for it; the hole is now at j, and the entries after j are examined against the new hole. When the scan reaches an empty slot, no entry beyond it has a path that crosses the holes (their paths cannot cross an empty slot by I), so I holds everywhere. ∎ Example: delete 44 (slot 6): j = 7 holds 59 with home 7 ∈ (6, 7]: stay; j = 8 holds 32 with home 6 ∉ (6, 8]: move to slot 6, the hole is 8; j = 9 holds 22 with home 9 ∈ (8, 9]: stay; j = 10 holds 31 with home 5 ∉ (8, 10]: move to slot 8, the hole is 10; j = 11 holds 73 with home 8 ∉ (10, 11]: move to slot 10, the hole is 11; j = 12 is empty: stop and empty the hole 11. Result [-, -, 41, -, -, 18, 32, 59, 31, 22, 73, -, -]: no tombstone, and 32, 31, 73 are found after 1, 4 and 3 probes (test_the_worked_example; with a wrap-around across the end of the array in test_wrap_around_case; random operations in both languages check that I holds after every operation and that the table equals a built-in map).
(c) A delete with a tombstone costs a search (O(1) expected); backward shift costs a search plus a scan of the rest of the run (the cluster after the slot: O(1) expected at a moderate load, but it grows with the clustering of linear probing). Tombstones make later searches longer until the next rebuild and cost memory for the counters and the rebuild logic; backward shift keeps the table exactly as if the key had never been inserted, so later searches are never slowed down and no rebuild is needed, at the price of a trickier delete. Backward shift needs one cheap test per entry — "is the hole on the path from the entry's home to its slot?" — which is the interval test of linear probing; for quadratic probing and double hashing the path of an entry is a different sequence for every key, entries that depended on the hole may be anywhere in the table (not in the run that follows), and there is no simple test: those schemes use tombstones. (Chaining needs neither: a delete is a list removal.)
IMPLEMENTATIONS (WITH MILESTONES)
Each file lists its milestones at the top. Do them in order and run the tests after each one.
Exercise 6 · Hash codes, compression and measuring a hash — ex7_hash.pyEx7Hash.java. Write the polynomial hash with 32-bit wrap-around (to_int32 / the int loop), compression that is never negative, next_prime, and bucket_stats, which repeats the experiment of video 1 on the 720 anagrams of "abcdef" in 1,009 buckets: 1 distinct code and a chain of 720 for the sum-of-letters hash, 720 codes and a longest chain of 4 for the polynomial hash. The tests also use the numbers of video 1 (the hash code of "hello", "Aa" and "BB") and the most negative int.
Solution
Reference: solutions/py/ex7_hash.py, solutions/java/Ex7Hash.java. The points to get right: wrap at 32 bits after every step in Python (to_int32(base * h + ord(ch)); the final result is the same as wrapping once at the end, which the tests check against the exact polynomial) while a Java int does it by itself; compression must never be negative: Python's % already has the sign of the divisor (-3 % 7 is 4), in Java % keeps the sign of the dividend (−3 % 7 is −3) and the fix is Math.floorMod (also for Integer.MIN_VALUE, whose absolute value is still negative: floorMod(Integer.MIN_VALUE, 10) is 2); next_prime(n) is the smallest prime ≥ n (next_prime(14) = 17, next_prime(1346) = 1361); bucket_stats is a counting loop: the number of distinct hash codes (a set), the buckets as counts, and the longest bucket and the empty buckets from them. The tests are the numbers of video 1: poly_hash("hello") = 99162322, "Aa" and "BB" both 2112, "polygenelubricants" hashes to exactly −2,147,483,648, and the 720 anagrams of "abcdef" in 1,009 buckets give (1, 720, 1008) for the sum of letters and (720, 4, 514) for the polynomial hash.
Exercise 7 · A chained hash map with rehashing — ex7_chained.pyEx7Chained.java. Implement put (it returns the old value), get, remove, the number of comparisons of the last operation, and the rehash into the next prime above twice the capacity when the load exceeds max_load. The tests replay the ten keys of video 2 (the chains, 1, 3 and 3 comparisons, 17 in all) and the 1,000 puts of video 4 (capacities 7, 17, 37, …, 1,361 and 984 moves), and compare random operations with a built-in map.
Solution
Reference: solutions/py/ex7_chained.py, solutions/java/Ex7Chained.java. The points to get right: the bucket is key % capacity in Python and Math.floorMod(key, capacity) in Java (negative keys); put first looks for the key in the chain and only appends when it is absent (so an update keeps its position and does not grow the table); count comparisons as the position + 1 when found and the chain length when missing (the tests replay the ten keys of video 2: 1, 3 and 3 comparisons for get(12), get(16), get(9), and 17 for all ten keys); rehash after the put that exceeded max_load · capacity, into next_prime(2 · capacity), walking the old buckets in order and appending each entry to its new chain, one move per entry (the 1,000 puts give the capacities 7, 17, 37, 79, 163, 331, 673, 1,361 and 984 moves, as in video 4); an update must never rehash. Note the milestone-3 test of the first rehash: 5 entries do not exceed 0.75 · 7 = 5.25, the sixth does, and then the key 5 lives in bucket 5 of 17, not in bucket 5 of 7 — the index depends on the table size, the misconception of video 4.
Exercise 8 · Linear probing with tombstones — ex7_probing.pyEx7Probing.java. Implement a fixed-capacity linear-probing map: put and get with the probe sequences of video 3 (19 probes for the eight keys), remove with a tombstone, and the reuse of the first tombstone by a later put. The tests include a table in which no slot is empty any more: every operation must still terminate (Exercise 10 is about exactly that).
Solution
Reference: solutions/py/ex7_probing.py, solutions/java/Ex7Probing.java. The core is one search routine that returns where the key is (or −1) and the first tombstone it passed, and that stops after capacity probes: (1) it stops at an EMPTY slot, (2) it skips DELETED slots but remembers the first one, (3) it compares keys only in used slots, (4) it never loops more than capacity times, so a table without any empty slot (all entries, or entries and tombstones) still answers; put of a new key stores in the remembered tombstone if there is one, else in the empty slot it stopped at, else raises "table full". get(99) in the table of video 3 probes [8, 9, 10, 11, 12] (it stops at the empty slot 12). The test with five tombstones in a 5-slot table is the one that matters most: it fails with the textbook loop "while the slot is not empty", and it is the bug of Exercise 10.
READ THE CODE
An AI assistant wrote each class together with a claim. In both exercises the claim is wrong because of a bug. Find a small input that shows it, say what exactly goes wrong and why the usual quick test does not show it, and fix it. Use the habits from the chapter: test with equal-but-different objects, and test the corner of a table (full, or full of tombstones).
Exercise 9 — Reading in read/py/ex7_read.py / Ex7Read.Reading in read/java/Ex7Read.java. The comment claims that two readings with the same temperature are equal and are the same key of a dictionary (a HashMap).
Solution
The bug. __eq__ / equals compares only the temperature, but the hash code is computed from the number and the temperature. So two readings that are equal have different hash codes: Reading(1, 20) == Reading(2, 20) is true, but hash(Reading(1, 20)) != hash(Reading(2, 20)) (Java: 1,012 and 1,043 for Objects.hash(1, 20) and Objects.hash(2, 20)). A hash table finds the bucket from the hash code, and compares the stored hash code before it calls equals, so the second reading is never even compared with the first: Reading(2, 20) in {Reading(1, 20): "a"} is False, put stores a second entry, and len(table) is 2 for two keys that are equal. The claim "the same temperature means the same key" is false; the table holds duplicates (test_equal_readings_are_not_the_same_key, also in Java with a HashMap and a HashSet). Why the quick tests miss it. Every test the AI wrote probably used the same object, or two readings with the same number (Reading(1, 20) twice), whose hash codes agree; the difference only shows for readings with different numbers and the same temperature. Compare an equal-but-different object with the one you stored: that is the test for the equals/hashCode contract. The fix. Hash exactly the fields that equality compares: hash(self.temperature) (Java: Integer.hashCode(temperature), or Objects.hash(temperature)). Then equal readings have equal hash codes (the contract of video 1: equal keys, equal hash codes) and the dictionary has one entry (test_the_repair). What happens if the hash is missing. In Python a class that defines __eq__ but no __hash__ becomes unhashable and raises TypeError the moment it is used as a key, which protects you (video 1). In Java a class that overrides equals but not hashCode silently inherits the identity hash code of Object: two equal objects have different hash codes and map.get(equalKey) returns null, with no error (equalsWithoutHashCodeUsesTheIdentityHashCode). Override both, with the same fields.
Exercise 10 — Probe10 in read/py/ex7_read.py / Ex7Read.Probe10 in read/java/Ex7Read.java. The comment claims that put, get and remove always terminate and take O(1) on average. (When you run it on a bad input it will not come back: interrupt it, or run it with a step limit.)
Solution
The bug. The probe loop while slot is not EMPTY and slot != key: i = next(i) only stops at an EMPTY slot or at the key, and the class never makes a slot EMPTY again and never reuses a tombstone, so it ends up in a state without any empty slot, and then every search for a key that is not there runs forever. Two inputs show it: (1) put the 13 keys 0 … 12 into the 13 slots and call get(99) (or put(99, …)): all slots are used and none holds 99, the loop never ends (an existing key such as 5 is still found, which makes the failure look random); (2) worse, with no entries at all: put a key and remove it, 13 times (put(5), remove(5), put(5), …): a remove leaves a tombstone, the next put skips the tombstone (it is not an EMPTY slot) and takes the next free slot, so each cycle uses up one more slot, and after 13 cycles all 13 slots are tombstones, size is 0 and get(7) hangs (test_tombstones_are_never_reused_so_an_empty_map_hangs; the tests use a subclass with a step limit so that the endless loop becomes a failing assertion). Why the quick tests miss it. A table with a few entries and a removal or two always has empty slots; the bug needs the table to run out of them, by being full or by tombstones piling up over time (a long-running server, not a unit test). The claim "always terminate" is a claim about the corner of the table, so test the full table and the table full of tombstones. The fix. (1) Bound the loop: at most capacity probes per operation, so a search in a table without empty slots ends with "not found". (2) Remember the first tombstone on the way and reuse it for a new key (the loop still goes on to an empty slot to be sure that the key is not further along). (3) Count the tombstones and rebuild the table (a rehash into a fresh array) when entries + tombstones exceed the maximum load, or use the backward-shift delete of Exercise 5(b), which needs no tombstones at all. Without (3) the bounded loop would end, but lookups would still degrade to O(m) as tombstones pile up. The class Fixed in test_ex7_read.pyEx7ReadTest.java does (1) and (2) and survives both inputs and 5,000 random operations (test_the_repair_survives_the_hanging_inputs).