Essay, code-tracing, bug-fixing and coding questions are in the week's question bank:
Data Structures and Algorithms (DSA27) · Week 13
Hash Tables (Lecture 13)
These quizzes are for self-study. Your answers are saved on this device only and are not sent anywhere.
-
A hash table finds the slot of a key by computing:
hashturns the key into an integer;% capacityfolds it into 0..capacity - 1. (a) only works for integer keys and puts all small keys in slot 0; (c) is searching, which is what hashing avoids. -
In a table of capacity 8, the index of the key 45 is:
45 = 5 × 8 + 5.
-
The one rule every hash function must obey is:
Otherwise two equal keys look in different buckets, and a key that is present is reported missing. (a) is impossible — there are more keys than hash values — and not needed: collisions are handled.
-
python -c "print(hash('abc'))"prints a different number each time you run it because:Hash randomisation, on by default since Python 3.3, so that an attacker cannot predict which strings collide. Within one run the hash never changes. (b) is how objects without a
__hash__of their own are hashed, not strings. -
Which of these is the same in every run of Python?
hash(n)isnfor every integer of this size.strandbyteshashes are randomised (b, c), and a set's order follows the hashes (d). -
m.put([1, 2], "x")raisesTypeError: unhashable type: 'list'because:A mutable key could change after
put; its hash would change with it, and it would sit in a bucket no lookup visits. So Python refuses to hash lists, dicts and sets at all. -
23 keys are placed in 365 slots at random. The probability that at least two share a slot is about:
1 - 365/365·364/365⋯343/365 ≈ 0.507 — the birthday paradox. 23/365 (c) is about 6% (a), the chance for one given pair, and ignores the other 252 pairs.
-
The load factor of a hash table is:
For chaining it is also the average chain length.
-
A
ChainingHashMap()receivesputfor 5, 13 and 21. Bucket 5 is:All three are 5 mod 8, and each new key is pushed on the front: after 5, then 13 → 5, then 21 → 13 → 5. Load 3/8: no resize.
-
In the table of W13-M09,
get(29)compares 29 with how many entries before raisingKeyError?29 % 8 = 5: it compares with 21, 13 and 5, reaches the end of the chain, and raises
KeyError. -
A
ChainingHashMap()receives distinct keys one at a time. The first resize happens during the put of the:The check runs after the insert, with
>: 6/8 = 0.75 is allowed, 7/8 = 0.875 is not. The table goes from 8 to 16 buckets during the 7th put. -
_resizecannot copyold[i]intonew[i]because:A key in bucket 2 of 8 (say 10) belongs in bucket 10 of 16. Copied across, it stays in bucket 2, and
get(10)looks in bucket 10:KeyError. Every key must be rehashed. -
An
OpenAddressingHashMap()receivesputfor 6, 14 and 22. Key 22 is in slot:6 → slot 6. 14 → 6 is taken, slot 7. 22 → 6, 7 taken, wrap to slot 0. Slots:
22 _ _ _ _ _ 6 14. -
In the table of W13-M13,
get(30, None)makes how many probes?30 % 8 = 6: probes 6 (6), 7 (14), 0 (22), 1 (
None) — four probes, then "not there". -
In open addressing,
deleteleaves a tombstone instead ofNonebecause:A search stops at
None, becauseputwould have used that slot. Emptying a slot in the middle of a probe sequence makes every key beyond it unreachable (test_open_addressing_delete_preserves_probe_chain). -
getmeets a tombstone while probing. It:A tombstone means "a key was here once, and others may have probed past it". Only
Noneends a search. -
putcounts tombstones in its load check because:Tombstones are not keys (a, c), but they are not
Noneeither. Uncounted, a table under many puts and deletes fills with tombstones: every miss probes the whole table, and a loop that waits forNonenever ends. -
Primary clustering is:
A run of length L is hit by any key whose home is in it or next to it, and the key lands at its end, making it longer. (b) is not clustering in the linear-probing sense.
-
For linear probing with a good hash, Knuth's formula for an unsuccessful search is 1/2(1 + 1/(1-α)2). At α = 0.5 it gives:
1/2(1 + 1/0.25) = 1/2 · 5 = 2.5. (a) is the successful search at 0.5; (d) the unsuccessful one at 0.9. Measured in Lecture 13 on 16,384 slots: 2.56.
-
The keys 0, 1024, 2048, 3072, … (n of them) are put into a
ChainingHashMap, whose capacity is always a power of two. While the capacity is at most 1,024, onegetcosts:Each key is a multiple of 1,024, so
key % capacityis 0 for every power-of-two capacity up to 1,024. Resizing does not help (a): the keys collide at every such capacity. One chain of n entries: O(n) perget, O(n2) to build. -
Python's
dictis:CPython's
Objects/dictobject.c: open addressing, probei = (5*i + 1 + perturb) % 2**kwithperturbtaken from the hash, a resize at about two-thirds, and "dummy" entries as tombstones. (b) is Java'sHashMap. -
Which question does a sorted array answer in O(log n) but a hash table cannot answer faster than O(n)?
A range query needs order, and hashing destroys order on purpose: 2027114 and 2027115 land far apart. A sorted array answers it with two
lower_bounds (Week 8). (a)–(c) are O(1) average in a hash table.
18 marks
Written questions
5 written questions (18 marks). Write your answer first, then open the model answer and its marking points, and mark yourself honestly: each point is worth about one mark.
Written total: 0 / 18
-
Explain how a hash table finds a key in O(1) time on average. State the assumption behind "on average", give the worst case, and name three things that can push a real table towards it.
Model answer and marking points
- Mechanism: the index
hash(key) % capacityis computed in O(1) and theArrayslot is reached in O(1); only the keys that share that slot are compared — a chain, or a short run of probes. - Assumption: the hash spreads the keys evenly, as if at random, and the load factor α is kept below a constant by resizing. Then a chain averages α entries (a probe run: a few slots), so
get,putanddeleteare O(1) expected, andputamortised because of resizes. - Worst case: all n keys in one bucket or one cluster: O(n) per operation.
- What pushes towards it (any three): a poor hash (sum of characters — anagrams collide); keys sharing their low bits on a power-of-two table (multiples of 1,024); an adversary who can predict the hash (hashDoS — hence string hash randomisation); no resizing, so α grows with n; open addressing near α = 1, or clogged with tombstones.
- Mechanism: the index
-
A student's class defines
__hash__to return 0 for every object. Is a hash table of these objects wrong, or only slow? Answer for chaining and for open addressing, and give the cost ofgetand of building a table of n keys.Model answer and marking points
- Only slow — never wrong. Every key hashes to 0 and lands in bucket (or home slot) 0; keys are still told apart by
==, so everygetfinds the right entry or correctly reports it missing. - Chaining: one chain holding all n keys.
getwalks it: O(n). Eachputwalks it too (to check for the key): building n keys is 1 + 2 + … + n = O(n2). Resizing never helps: 0 % capacity is always 0. - Open addressing: all keys form one cluster starting at slot 0; a
getprobes up to n slots, O(n); building is O(n2) — the same. - The only hash rule for correctness is "equal keys, equal hashes", and a constant keeps it. Every other quality of a hash function is about speed.
- Only slow — never wrong. Every key hashes to 0 and lands in bucket (or home slot) 0; keys are still told apart by
-
Compare chaining and open addressing: what a slot holds, the load factors each can tolerate, how each deletes, and one practical advantage of each.
Model answer and marking points
- A slot holds: chaining —
Noneor the head of a linked list ofEntrynodes; open addressing — one key (in_keys) and its value (in_values), orNone, or a tombstone. - Load factor: chaining still works above 1 (chains simply grow; cost about 1 + α), and resizes at 0.75 here; open addressing cannot exceed 1 at all and degrades sharply near it (a miss ≈ 1/2(1 + 1/(1-α)2)), so it resizes earlier — 0.66 here, about 2/3 in CPython.
- Delete: chaining unlinks a node (the head is the special case); open addressing must leave a tombstone, which later puts may reuse and a resize drops.
- Advantages: chaining — simple deletion, graceful at high load, never "full"; open addressing — no node per key (less memory, no allocation), and consecutive probes are neighbours in memory, which suits the cache. CPython's
dictandsetuse open addressing; Java'sHashMapuses chaining.
- A slot holds: chaining —
-
Explain tombstones. Why can an open-addressing
deletenot simply empty the slot? State howget,putand_resizeeach treat a tombstone, and why the load check must count them.Model answer and marking points
- Why not empty the slot: a search stops at
None. If keys a and b collide and b was placed beyond a, emptying a's slot cuts b's probe sequence:get(b)stops at the newNoneand reports b missing although it is still in the table. get/delete: skip a tombstone and keep probing; stop only at the key or atNone.put: remember the first tombstone passed, but keep probing toNone— the key may be further on (then overwrite it). If it is not there, insert at the remembered tombstone (reusing the space), else at theNone._resize: re-insert only live keys; tombstones are dropped, so the new table has none.- Load check: tombstones are not keys, but they fill slots, and only
Nonestops a probe. Counting them (size + tombstones + 1) forces a rebuild — at the same capacity if the live keys alone are within the limit — before the table runs out ofNone.
- Why not empty the slot: a search stops at
-
Show that a hash table that doubles its capacity when the load factor passes a fixed limit does amortised O(1) work per
puton rehashing. What happens if it grows by a fixed 8 slots instead?Model answer and marking points
- A resize at size s rehashes s keys. With doubling, the resizes before reaching size n happened at sizes of at most n, n/2, n/4, …, so the total rehashing is at most n + n/2 + n/4 + … < 2n: O(n) for n puts, amortised O(1) each. (Measured in Lecture 13: 3,075 keys rehashed for 3,000 puts in the chaining table, 5,396 in the open-addressing one — both under 2n.)
- Growing by 8 slots: a resize every 6 or so puts, each rehashing all keys so far: 6 + 12 + 18 + … ≈ n2/12 — Θ(n2) in total, Θ(n) amortised per put. The same argument as the
DynamicArraywith a constant growth step (Lecture 04).