Lecture X · Data Structures & Algorithms
Hash tables, or: it’s too slow!
Last lecture we spent an hour making sorting fast, and the reward for that work
is that we can now stop sorting things. Today’s question is the one you will ask
of a computer more often than any other: I have a key, please give me the value
filed under it. A username to an account. A word to its definition. A URL to a
cached page. This is the Mapping, and it is the abstract data type Python
hands you as dict, so casually that most people never wonder what is inside.
Sheehy opens his chapter on it by writing the obvious implementation, showing it to an imaginary user, and reporting the user’s entire response: it’s too slow! That complaint is the whole lecture. We are going to build the slow thing on purpose, feel exactly why it is slow, and then fix it with an idea that sounds, the first time you hear it, like cheating.
The Mapping ADT
Start where we always start: not with code, but with a contract. Lecture IV argued that an ADT is a promise about behaviour, made independently of any implementation, and the Mapping’s promise is short.
class Mapping:
"""A collection of key-value pairs, each key appearing at most once.
get(key) the value filed under key; raise KeyError if absent
put(key, value) file value under key, replacing any previous value
remove(key) delete the entry; raise KeyError if absent
__len__() how many pairs are stored
__contains__(k) is there an entry for k?
keys() the keys, in no promised order
values() the values, in no promised order
items() the (key, value) pairs, in no promised order
"""
Three things in that docstring do real work, so read them again slowly.
First, each key appears at most once. Putting a key that is already present
is not an insertion, it is an overwrite. That single clause is what separates a
Mapping from a list of pairs, and it is the source of half the bugs students
write when they implement one, because append is easier to type than “search,
and only append if you did not find it.”
Second, raise KeyError if absent. This is the ADT lesson from Lecture IV
appearing again in a new costume. The interesting question is never only “what
does it do when it works,” it is “what does it do when it cannot.” Returning
None for a missing key is a defensible design, right up until somebody
legitimately stores None as a value and can no longer tell “absent” from
“present and empty.” Python chose to raise, and offered dict.get(key, default)
as the separate, opt-in, quieter answer. What matters is that the choice was
made out loud and written into the contract, not discovered in production.
Third, in no promised order. A Mapping is not a sequence. There is no
“third key”. Modern CPython does in fact preserve insertion order in dict, and
that became a language guarantee in 3.7, but it was an accident of an
implementation change before it was ever a promise, and the ADT itself does not
require it. Code that leans on iteration order without the contract saying so is
code that will break on the day someone swaps the backing store, which is
precisely the day an ADT exists to survive.
The honest slow version
The obvious implementation writes itself. Keep a list of entries. To find a key, walk the list and compare.
class Entry:
def __init__(self, key, value):
self.key = key
self.value = value
class ListMapping:
def __init__(self):
self._entries = []
def _find(self, key):
for e in self._entries:
if e.key == key:
return e
return None
def put(self, key, value):
e = self._find(key)
if e is not None:
e.value = value # the "at most once" clause, enforced
else:
self._entries.append(Entry(key, value))
def get(self, key):
e = self._find(key)
if e is None:
raise KeyError(key)
return e.value
This is correct. Every test you could write against the Mapping contract passes.
It is also, on a mapping of entries, for get and for put,
because both of them run _find, and _find is a linear scan. Worse, the cost
is worst exactly when you least want it: a miss, a key that is not there,
costs the full comparisons, because you cannot conclude “absent” until you
have looked everywhere. And a miss is not a rare event. Every put of a brand
new key is a miss.
So building a mapping of entries costs comparisons, which is , which is . That is the same quadratic we watched crawl out of a list-backed queue in Lecture IV, and it is the same one that made insertion sort unusable in Lecture VIII. It never announces itself on a small test.
Notice that nothing here is badly written. There is no wasted work, no redundant loop, no clumsy copy. The linear scan is optimal, given the one assumption we never questioned: that to find a key, you have to look for it. Everything that follows comes from refusing that assumption.
Let the key compute its own address
Here is the thought experiment that unlocks it. Suppose, for a moment, that all
our keys are integers between 0 and 99. Then we do not need a search at all: make
a list of 100 slots and store the value for key at index . Lookup is
slots[k]. One arithmetic step, no comparisons, no scan. , and not
amortised or expected or on-average, just flatly constant, because an array
index is constant.
That is a direct address table, and it is both perfect and useless. Perfect because it cannot be beaten. Useless because real keys are not small integers. They are strings, tuples, dates, user objects. And even when they are integers, they are the wrong integers: if your keys are nine-digit identifiers you would need a billion slots to store three of them.
The hash table is what you get when you keep the good half of that idea and
repair the bad half. Keep “the key computes its own address.” Repair “the address
space is enormous” by squashing it. A hash function takes any key and returns
an integer; then % m folds that integer down into the range to , which
is a table you can actually afford.
Two steps, both : compute a number from the key, take a remainder. No searching. The key told us where to look.
A hash function has exactly one hard requirement and one soft one. The hard requirement is agreement: if two keys are equal, they must hash to the same number. Break it and the structure is not slow, it is wrong, because you will store a value under a key and then fail to find it with an equal key. The soft requirement is spread: unequal keys should mostly land on different numbers. Break it and the structure is not wrong, just slow.
Here is a hash function you can read in one breath, the classic polynomial:
def hash_string(s):
h = 0
for ch in s:
h = (h * 31 + ord(ch)) % (2 ** 32)
return h
It treats the string as the digits of a number in base 31 and keeps the low 32
bits. Every character participates, and multiplying by 31 before adding the next
one means that moving a character to a different position changes the answer, so
"ab" and "ba" do not collide. It is not cryptographic, it is not clever, and
it is entirely good enough.
That second table is worth staring at, because it is the boundary of what
hashing promises. A constant hash function is correct. Every equal pair of keys
agrees. The mapping built on it returns exactly the right answers, forever. It is
merely a ListMapping wearing a costume, and every lookup is back to .
Correctness and cost are separate promises, and hashing only ever gives you the
first one for free.
__hash__ and __eq__ must agree
In Python the hard requirement has a name and an address. Every object has a
__hash__ method and an __eq__ method, and the language’s rule is a single
sentence:
If
a == b, thenhash(a) == hash(b).
Not the converse. Two unequal objects are perfectly entitled to share a hash;
that is a collision, and collisions are ordinary. But two equal objects landing
on the same number is not optional, it is the load-bearing wall. A dict finds a key by
computing its hash to pick the bucket, and then comparing with == inside that
bucket. If equal keys hash differently, the lookup goes to the wrong bucket and
the entry sitting quietly in the right one is never even considered.
This is why Python makes you keep the pair in step. Define __eq__ on your class
and Python removes the inherited __hash__, making your instances unhashable
until you define __hash__ too. It looks like an inconvenience. It is the
language refusing to let you build a structure that silently loses data.
class Point:
def __init__(self, x, y):
self.x, self.y = x, y
def __eq__(self, other):
return (self.x, self.y) == (other.x, other.y)
# Defining __eq__ alone would make Point unhashable. Define both,
# over the SAME fields, and the two agree by construction.
def __hash__(self):
return hash((self.x, self.y))
Note where the hash comes from: the same tuple of fields the equality uses. That is the discipline. Hash over exactly the fields you compare over, and agreement is not something you maintain, it is something you cannot break.
Which leads to the other half of the rule, and to the reason list is not
hashable while tuple is. Look at the definition again: hashing over the fields
means the hash depends on the contents. If the contents can change, the hash
can change, and a key whose hash changes after you have filed it is a key you can
no longer find. The entry does not move; the search does.
So “hashable” is not a technicality about which types Python happens to allow. It
is a promise the key makes: my hash will not change while you are holding me.
Immutable types can make that promise trivially. list, set, and dict cannot,
so they refuse to be keys at all, which is Python declining to let you file
something under an address that will not stay put. When you write a class of your
own and want it usable as a key, you are making the same promise, and the way to
keep it is to hash over fields you never mutate.
Buckets, chains, and what to do about collisions
Back to the table. We can turn a key into a bucket index in constant time; now we need somewhere for the value to live. The obstacle is that buckets cannot hold more than distinct hashes, so as soon as we have more keys than buckets, two keys must share. This is the pigeonhole principle, and it means collisions are not a design flaw to be avoided but a certainty to be handled.
The handling strategy we will build is chaining: each bucket holds not one entry but a little collection of them, and a lookup hashes to the bucket and then scans just that collection.
class HashMapping:
def __init__(self, m=8):
self._buckets = [ListMapping() for _ in range(m)]
self._length = 0
def _bucket(self, key):
return self._buckets[hash(key) % len(self._buckets)]
def get(self, key):
return self._bucket(key).get(key) # KeyError propagates
def put(self, key, value):
bucket = self._bucket(key)
n_before = len(bucket)
bucket.put(key, value)
self._length += len(bucket) - n_before # 1 for new, 0 for overwrite
Look at what the buckets are. They are ListMappings, the very class we built
and then complained about. This is Sheehy’s joke and it is a good one: the slow
mapping was never wrong, it was only ever asked to do too much. Hand it eight
entries instead of eight million and its linear scan is a perfectly fine way to
spend your afternoon. The hash function’s job is not to replace the linear scan
but to make sure the linear scan is always short.
That reframing is the actual idea of a hash table, so let me say it plainly. A hash table is a linear search you have arranged never to be long. Everything else in this lecture is bookkeeping in service of that one sentence.
Which raises the obvious question: what keeps the chains short?
The load factor
Define
the number of stored keys divided by the number of buckets. This is the load factor, and it is the single number that governs a hash table’s health.
If the hash function spreads keys evenly, then is exactly the average chain length: keys distributed across buckets puts in each. A lookup costs one hash computation, one array index, and then a scan of one chain, so the expected cost is
comparisons. Read that formula carefully, because it says something surprising: the cost does not depend on . It depends on the ratio. A table with a million keys and two million buckets is faster than a table with a hundred keys and ten buckets. Size is not the enemy; crowding is.
So keeping lookups constant reduces to keeping bounded by some constant.
Choose a threshold, and the moment the table crosses it, make the table bigger.
Sheehy uses ” above 1”; CPython’s dict grows at around two thirds full;
Java’s HashMap uses 0.75. The exact number is a memory-versus-speed dial, not a
correctness question. Any fixed ceiling gives you , which
is .
The plate below is that arithmetic made physical. Feed it words and watch the load meter climb; the moment passes 1 a rehash fires as its own visible step, doubling the table and re-placing every key. Then, when you have the feel of it, switch the Rehash checkbox off and keep feeding: the meter runs off the end, the chains lengthen in step, and the longest chain, which is the worst-case lookup, climbs without limit.
| keys n | buckets m | load α = n/m | event |
|---|---|---|---|
| 1 | 8 | 0.13 | · |
| 4 | 8 | 0.50 | · |
| 8 | 8 | 1.00 | · |
| 9 | 16 | 0.56 | rehash 1: 8 → 16 buckets, 9 keys re-placed |
| 12 | 16 | 0.75 | · |
| 16 | 16 | 1.00 | · |
| 17 | 32 | 0.53 | rehash 2: 16 → 32 buckets, 17 keys re-placed |
| 20 | 32 | 0.63 | · |
Rehashes get rarer as the table grows: doubling means the nth key can only trigger a rebuild at n = 9, 17, 33, and so on, so the total re-placement work across n insertions is under 2n. That is the amortised O(1).
Rehashing, and why doubling buys amortised constant time
Growing the table is not a resize. A hash table cannot simply allocate more buckets and carry on, because every key’s address was computed as , and has changed. Every key’s address is now potentially wrong. So growth means rehashing: build a fresh array of buckets and re-place all entries into it, one at a time.
def _rehash(self, new_m):
old = self._buckets
self._buckets = [ListMapping() for _ in range(new_m)]
for bucket in old:
for key, value in bucket.items():
self._bucket(key).put(key, value) # a NEW bucket index
That is an operation sitting inside a method we just promised was , and if you stopped reading here you would be right to be suspicious. The resolution is the same amortisation argument that rescued the two-stack queue in Lecture IV, and it is worth doing the accounting rather than waving at it.
Suppose the table starts with buckets and doubles whenever passes
- Then rehashes happen at , then , then , and so on, and the -th of them re-places about keys. Insert keys altogether and the total re-placement work is
because a doubling series is dominated by its last term. At most units of
rehashing work spread over insertions is at most 2 units each. Add the
constant cost of the insertion itself and the average cost per put is a
constant, even though individual put calls occasionally cost . That is
amortised : not “every operation is cheap”, but “any run of operations is
cheap on average, because the rare expensive one is paid for by all the cheap
ones that made it necessary.”
Now watch what happens if you grow by a fixed amount instead. Add 10 buckets each time you overflow and rehashes happen every 10 insertions, each costing the current , so the total is , which is all over again. The geometry is the whole trick. Growing by a factor makes the expensive events exponentially rarer as they get linearly more expensive, and those two curves cancel. Growing by a constant makes them steadily more expensive at a fixed rate, and nothing cancels.
When the keys are chosen by someone who dislikes you
Every cost claim so far has quietly assumed the hash function spreads your keys. That is a claim about the keys, not about the function, and it is the assumption an attacker attacks.
Consider the table sizes we have been using: 8, 16, 32, 64. All powers of two,
because % m on a power of two is a bitmask and therefore very fast. The price
of that convenience is that % m reads only the low bits of the hash and throws
the rest away. So if I can find keys whose hashes all agree in the bottom six
bits, they collide in a 64-bucket table, and in a 32-bucket table, and in 16, and
in 8. Doubling the table cannot separate them, because doubling only ever looks
at one more low bit, and I have fixed those too.
Finding such keys is not hard. If the hash function is public, and it always is, you sit in a loop generating candidate strings and keep the ones that land on your target. That is exactly what the Adversarial feed on Plate IV does, at page load, in a few milliseconds of your own browser’s time.
The answer is , and the structure is ListMapping. Every guarantee has
collapsed back to the linear scan we started the lecture trying to escape,
without a single line of the implementation being wrong. And this is not a
thought experiment. Around 2011 it was demonstrated that many web frameworks
could be knocked over by a single HTTP POST containing a few thousand
carefully-chosen form-field names, because the framework parsed them into a hash
table and the table went quadratic. It has a name, hash flooding, and it took
down real services.
The fix is to stop letting the attacker know the function. Modern Python seeds
its string hashing with a random value chosen at interpreter startup, so
hash("apple") differs between two runs of the same program on the same machine.
Try it: run python3 -c 'print(hash("apple"))' twice. An attacker who cannot
predict the hash cannot precompute collisions for it. This is also, incidentally,
a second reason never to rely on dict iteration order or to persist a hash to
disk: those numbers are not stable across runs, on purpose.
That randomisation is why the honest complexity claim for a hash table is “expected ”, not "". The expectation is over the random seed, not over the keys, and that distinction is what makes it a guarantee an adversary cannot strip away rather than a hope about well-behaved input.
Factoring out the superclass
Now step back and look at the two classes we have built. ListMapping and
HashMapping disagree about everything that matters for cost and agree about
everything that matters for meaning. Both answer get, put, keys, values,
items, __len__, __contains__, and both give the same answers, at wildly
different speeds.
Write them both out in full and you will notice something irritating: most of those methods are identical, and none of the identical ones touch the storage.
def __contains__(self, key):
try:
self.get(key)
return True
except KeyError:
return False
Nothing in that method knows or cares whether the entries live in one list or in
sixty-four buckets. It is written purely in terms of get, which is to say
purely in terms of the ADT. So it should not be written twice.
That is the refactor Sheehy builds the chapter toward, and it is the deepest idea
in the lecture, deeper than hashing. Split every Mapping into two layers. The
bottom layer is a small set of primitives that genuinely depend on the
storage: get, put, and some way to walk the entries. The top layer is
everything derived, written once in a superclass, in terms of the primitives
only.
class Mapping:
"""The derived half. Implement get, put, and _entryiter in a
subclass, and inherit the rest, correct by construction."""
def __contains__(self, key):
try:
self.get(key)
return True
except KeyError:
return False
def get_default(self, key, default):
try:
return self.get(key)
except KeyError:
return default
def keys(self):
return [e.key for e in self._entryiter()]
def values(self):
return [e.value for e in self._entryiter()]
def items(self):
return [(e.key, e.value) for e in self._entryiter()]
def __len__(self):
return len(self.items())
def __getitem__(self, key):
return self.get(key)
def __setitem__(self, key, value):
self.put(key, value)
class ListMapping(Mapping):
def __init__(self):
self._entries = []
def _entryiter(self):
return self._entries
def get(self, key): ...
def put(self, key, value): ...
class HashMapping(Mapping):
def __init__(self, m=8):
self._buckets = [ListMapping() for _ in range(m)]
def _entryiter(self):
return [e for b in self._buckets for e in b._entryiter()]
def get(self, key): ...
def put(self, key, value): ...
Three payoffs, and they are worth naming separately because students usually see only the first.
The obvious one is that you write less code. Six derived methods, two subclasses, so six methods saved. Fine.
The better one is that the derived methods can only be wrong once. If
__contains__ has a bug it has one bug, in one place, and fixing it fixes every
backing store at the same instant. Duplicated code does not have one bug; it has
one bug per copy, and they drift.
The best one, and the reason this belongs in a data structures course rather than
a software engineering one, is that the superclass is the ADT, made
executable. Before this refactor, “the Mapping contract” was a paragraph in a
docstring that you had to trust each implementation to honour. After it, the
contract is a class, and the primitives are exactly the places where an
implementation is allowed to have an opinion. Adding a third backing store, a
tree, a database table, a file on disk, means writing get, put, and
_entryiter, and everything else arrives already correct. The interface stopped
being a promise and became a piece of the program.
You have met this shape before without the name. The LinkedList wrapper in
Lecture V sealed the nodes so it could promise things about the length. This
seals the storage so it can promise things about the behaviour. Same move, one
level up.
What it costs
| Operation | ListMapping | HashMapping (expected) | HashMapping (adversarial) |
|---|---|---|---|
get(key), hit | |||
get(key), miss | |||
put, new key | amortised | ||
put, overwrite | |||
remove(key) | |||
| Build from keys | amortised | ||
| Iterate all keys | |||
| Extra memory | entries | entries plus buckets | same |
| Keys in sorted order | sort them, | sort them, | same |
Two rows deserve a second look.
Iterate all keys costs , not , because walking the table means visiting every bucket, including the empty ones. With held near 1 the two terms are comparable and nobody minds. Hold at 0.01 to make collisions vanish and you have bought fast lookups with a hundredfold slower iteration and a hundredfold memory bill. The load factor is a dial with a cost on both ends.
Keys in sorted order is the row that explains why the next lecture exists. A hash table scatters keys deliberately, so it has no notion of “the next key after this one”, no cheap minimum, no range query. If you want the ten users whose names start with “Fr”, the hash table can only offer you a full scan. That is the entire reason a course that already has lookup goes on to spend three weeks on trees: a balanced search tree is slower than a hash table at the one thing hash tables do, and it can answer questions a hash table cannot even express.
Problems
Work them in order. The last four run their own checks; make every row green.
Warm-up, on paper. A hash function returns 4 for every key. Which of the Mapping ADT’s promises does it break, and which does it keep? Then say what a mapping of keys built on it costs for a single
get, and name the class from this lecture it has become.The agreement rule. Suppose a class defines
__eq__over itsxandyfields but writes__hash__to returnid(self), which is different for every object. In two or three sentences, walk through what happens when you put a value underPoint(1, 2)and then look it up with a freshly built, equalPoint(1, 2). Is the entry lost, duplicated, or corrupted? Which of the two requirements from this lecture, agreement or spread, has been broken?The load factor, both directions. Using Plate IV with Rehash switched off, feed the words until passes 2. Record the longest chain. Explain why the expected lookup cost predicts what you are seeing, and then explain why the longest chain is bigger than even with a good hash function. Finally: what would buy you, and what would it cost?
Why doubling, precisely. A table grows by adding a fixed 16 buckets whenever it overflows, rather than doubling. Write down the total rehashing work over insertions as a sum, evaluate it, and give its order. Then do the same for doubling. In one sentence, say what property of the doubling series makes the difference.
The slow one, built properly. Implement
_find,put, andgetso the mapping keeps the contract: one entry per key, overwrite on repeat, andKeyErroron a miss. This is the class every bucket of the hash table will be, so get it right.The checks · run against your code
# a key put is a key found m = ListMapping() m.put("a", 1) assert m.get("a") == 1 # a repeated key overwrites and does NOT grow the mapping m.put("a", 99) assert m.get("a") == 99 assert len(m) == 1 # distinct keys coexist, in arrival order m.put("b", 2) m.put("c", 3) assert len(m) == 3 assert m.keys() == ["a", "b", "c"] assert m.get("b") == 2 # a missing key raises KeyError, it does not quietly return None raised = False try: m.get("zzz") except KeyError: raised = True assert raised # an empty mapping has length zero and misses everything e = ListMapping() assert len(e) == 0 try: e.get("a") ok = False except KeyError: ok = True assert okpython runs in your browser · first run downloads ~240 kbPlate V The Mapping contract, honoured slowly. Three stubs: find an entry, file a value, fetch a value. The checks pin down the two clauses people drop, that a repeated key overwrites rather than appends, and that a missing key raises rather than returning None. Press Run to grade. Hint one
_findis the loop you have written a dozen times: walkself._entries, and the momente.key == key, returne. Falling off the end of the loop means the key is absent, so returnNonethere.Hint two
Both
putandgetshould call_findfirst and then branch on whether it came backNone. Input, a found entry gets itsvaluereassigned in place; that is the “at most once” clause. Inget, aNonemeansraise KeyError(key).The solution
One search, reused by both callers:
def _find(self, key): for e in self._entries: if e.key == key: return e return None def put(self, key, value): e = self._find(key) if e is not None: e.value = value else: self._entries.append(Entry(key, value)) def get(self, key): e = self._find(key) if e is None: raise KeyError(key) return e.valueEvery one of these is , and that is not a defect to be apologised for: it is the honest cost of a structure that has no idea where anything is. Note that
putcosts a full scan even when the key is new, because proving a key absent means looking everywhere. Hold on to that, because it is exactly the work the hash function is about to delete.The address calculator. Implement the polynomial hash and the bucket index. The checks pin the hash to exact values, so read the docstring closely: the running value starts at 0, and each character multiplies by 31 before adding
ord(ch), all kept inside 32 bits.The checks · run against your code
# the empty string hashes to the seed, 0 assert hash_string("") == 0 # one character is just its code point assert hash_string("a") == 97 # each further character multiplies by 31 and adds assert hash_string("ab") == 3105 assert hash_string("abc") == 96354 # equal keys must hash equal, every single time assert hash_string("cedar") == hash_string("ced" + "ar") # order matters, so a rearrangement is a different key assert hash_string("ab") != hash_string("ba") # the answer stays inside 32 bits even for long keys assert 0 <= hash_string("a" * 200) < 2 ** 32 # bucket_of always lands inside the table for w in ["apple", "birch", "cedar", "dogma", "ember", ""]: assert 0 <= bucket_of(w, 8) < 8 assert 0 <= bucket_of(w, 16) < 16 # and it agrees with the hash it is derived from assert bucket_of("apple", 8) == hash_string("apple") % 8 assert bucket_of("apple", 16) == hash_string("apple") % 16python runs in your browser · first run downloads ~240 kbPlate VI Two functions, one contract. hash_string must be deterministic, must depend on every character, and must depend on their order; bucket_of must land inside the table for any key and any table size, including the empty string. Press Run to grade. Hint one
The hash is a three-line loop over the characters. Start
h = 0; for eachch, reassignh = (h * 31 + ord(ch)) % (2 ** 32); returnh. The empty string never enters the loop, which is why it hashes to the seed.Hint two
bucket_ofis one line and it is the formula from the lecture: hash the key, then take the remainder modm. The remainder is what guarantees the result is a legal index, which is precisely what the checks probe.The solution
Fold the characters in, then fold the result into the table:
def hash_string(s): h = 0 for ch in s: h = (h * 31 + ord(ch)) % (2 ** 32) return h def bucket_of(key, m): return hash_string(key) % mThe hash is linear in the length of the key, not constant, which is a detail worth being honest about: hashing a 300-character URL really does cost 300 steps. We call the whole thing constant time because key lengths are bounded in practice, but if your keys are megabyte strings, the hash is your bottleneck and no amount of table tuning will help.
The main event: growth.
getis written for you, and it assumes the invariant that every pair sits in the bucket its current hash says it should. Yourputmust maintain that invariant, which means firing_rehashwhen the load factor passes 1, and your_rehashmust double the table and re-place every pair.The checks · run against your code
# a key put is a key found h = HashMapping() h.put("apple", 1) assert h.get("apple") == 1 # overwriting a key does not grow the mapping h.put("apple", 2) assert h.get("apple") == 2 assert len(h) == 1 # four keys in four buckets is a load factor of exactly 1: no rehash yet h = HashMapping() for w in ["a", "b", "c", "d"]: h.put(w, w) assert len(h) == 4 assert h.buckets() == 4 assert h.rehashes == 0 # the fifth key pushes the load past 1 and fires exactly one rehash h.put("e", "e") assert h.buckets() == 8 assert h.rehashes == 1 assert len(h) == 5 # nothing is lost in a rehash: every key is still reachable for w in ["a", "b", "c", "d", "e"]: assert h.get(w) == w # and every key now sits where the NEW table size says it should for w in ["a", "b", "c", "d", "e"]: assert w in [p[0] for p in h._buckets[hash_string(w) % h.buckets()]] # nine keys double the table twice, and not once more than they must h = HashMapping() for i in range(9): h.put("k" + str(i), i) assert h.buckets() == 16 assert h.rehashes == 2 assert len(h) == 9 # a missing key still raises KeyError raised = False try: h.get("nope") except KeyError: raised = True assert raisedpython runs in your browser · first run downloads ~240 kbPlate VII Rehashing, checked. Four keys in four buckets is a load factor of exactly 1 and must not trigger anything; the fifth must double the table exactly once. The checks then reach into _buckets and verify that every key sits where the NEW table size puts it, which is the invariant a lazy rehash silently breaks. Press Run to grade. Hint one
puthas the same shape asListMapping.put, only it searches one bucket instead of everything. Get the bucket withself._buckets[hash_string(key) % len(self._buckets)], scan it for a matchingpair[0], and either overwritepair[1]and return, or append a fresh[key, value]and bumpself._length.Hint two
The growth test goes after the insertion, and the threshold is strict: rehash when
self._length / len(self._buckets) > 1, so a load factor of exactly 1 is still fine. Inside_rehash, collect every pair from the old buckets first, build a brand new list of twice as many empty buckets, and only then re-place the pairs. Re-placing into the old list while you are still walking it is how this goes wrong.The solution
Insert, then check the load; grow by rebuilding, never in place:
def put(self, key, value): b = self._buckets[hash_string(key) % len(self._buckets)] for pair in b: if pair[0] == key: pair[1] = value return b.append([key, value]) self._length += 1 if self._length / len(self._buckets) > 1: self._rehash() def _rehash(self): pairs = [] for b in self._buckets: for pair in b: pairs.append(pair) self._buckets = [[] for _ in range(2 * len(self._buckets))] for pair in pairs: self._buckets[hash_string(pair[0]) % len(self._buckets)].append(pair) self.rehashes += 1Two details carry the exercise. The overwrite branch returns early, so it never touches
_lengthand never triggers growth: an overwrite does not make the table more crowded. And_rehashrecomputes the bucket from scratch rather than reusing the old index, becauseh(key) % 8andh(key) % 16are different questions. Carrying the old index across is the single most common rehash bug, and it does not raise anything; it just loses keys.The superclass. Fill in the five derived methods on
Mapping, using onlyself.get,self.put, andself._entries(). The checks run the identical assertions against bothListMappingandHashMapping, so if your methods reach into either subclass’s storage, one of the two will fail.The checks · run against your code
# the derived methods work, unchanged, on BOTH backings for cls in [ListMapping, HashMapping]: m = cls() m.put("a", 1) m.put("b", 2) assert m.get_or("a", 0) == 1 assert m.get_or("zzz", 0) == 0 assert m.contains("a") assert not m.contains("zzz") assert sorted(m.keys()) == ["a", "b"] assert sorted(m.values()) == [1, 2] assert len(m) == 2 # get_or never swallows a real stored value, even a falsy one for cls in [ListMapping, HashMapping]: m = cls() m.put("zero", 0) assert m.get_or("zero", 999) == 0 assert m.contains("zero") # setdefault fills a hole once and then leaves it alone for cls in [ListMapping, HashMapping]: m = cls() assert m.setdefault("a", 1) == 1 assert m.setdefault("a", 999) == 1 assert m.get("a") == 1 assert len(m) == 1 # an empty mapping is empty by every route for cls in [ListMapping, HashMapping]: m = cls() assert len(m) == 0 assert m.keys() == [] assert m.values() == [] assert not m.contains("anything")python runs in your browser · first run downloads ~240 kbPlate VIII One contract, two backings. Every derived method is written once, against the primitives, and inherited by a flat list and a bucket table alike. The checks loop over both classes and assert the same things of each, including the falsy-value trap that catches a get_or written with a truthiness test. Press Run to grade. Hint one
get_orandcontainsare bothtry/except KeyErroraroundself.get. Resist the urge to writeif self.get(key): ...: a stored value of0or""is present and falsy, and the checks put a zero in the table specifically to catch that.Hint two
keysandvaluesare one comprehension each overself._entries(), takingpair[0]andpair[1]. Forsetdefault, try toget; onKeyError,putthe default and return it. Note that the base class never once mentions a list or a bucket, and that is the property the checks are really testing.The solution
Five methods, none of which knows where anything is stored:
def get_or(self, key, default): try: return self.get(key) except KeyError: return default def contains(self, key): try: self.get(key) return True except KeyError: return False def keys(self): return [pair[0] for pair in self._entries()] def values(self): return [pair[1] for pair in self._entries()] def setdefault(self, key, default): try: return self.get(key) except KeyError: self.put(key, default) return defaultNow count what you would have to write to add a third backing store, a mapping kept sorted in an array, or one that spills to a file. Three methods:
get,put,_entries. Everything above arrives already written and already correct, and the checks in this plate would pass for it unchanged. That is what it means for an ADT to stop being a paragraph of documentation and start being a piece of the program.The adversary, in writing. You are handed a hash table with a public, unseeded hash function and a power-of-two table size. Describe, in three or four sentences, how you would construct a set of keys that forces every lookup to cost , why doubling the table does not save it, and what change to the hash function (not the table) defeats your attack. Then say why the honest complexity claim for a real hash table is “expected ” rather than "", and what the expectation is taken over.