Gregory Friedman The Greg Wide Web on the name →
The Arc · lecture X of XIV

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 nn entries, O(n)O(n) for get and O(n)O(n) 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 nn 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 nn entries costs 1+2+⋯+n1 + 2 + \cdots + n comparisons, which is n(n+1)/2n(n+1)/2, which is O(n2)O(n^2). 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.

python runs in your browser · first run downloads ~240 kb
Plate I The complaint, measured. A Mapping backed by one list of entries, with every key comparison counted. The first key is found in one probe, the last in twenty, and a miss costs all twenty because absence can only be proved by looking everywhere. Press Run, then Trace to watch the scan.

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 kk at index kk. Lookup is slots[k]. One arithmetic step, no comparisons, no scan. O(1)O(1), 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 00 to m−1m-1, which is a table you can actually afford.

bucket(k)  =  h(k) mod m\text{bucket}(k) \;=\; h(k) \bmod m

Two steps, both O(1)O(1): 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.

python runs in your browser · first run downloads ~240 kb
Plate II Two hash functions, one table. The polynomial hash scatters ten words across eight buckets; hash_terrible answers 7 for every key, which keeps equal keys agreeing (the hard rule) while destroying the spread (the soft one), so the whole table degenerates into a single list. Press Run.

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 O(n)O(n). 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, then hash(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.

python runs in your browser · first run downloads ~240 kb
Plate III The disappearing entry. A key is hashed, filed in a bucket, and then mutated. Nothing is deleted and nothing is corrupt: the entry sits exactly where it was put, but the search now computes a different bucket and looks somewhere else entirely. This is the whole reason a list cannot be a dict key and a tuple can. Press Run.

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 mm buckets cannot hold more than mm 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

α  =  nm\alpha \;=\; \frac{n}{m}

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 α\alpha is exactly the average chain length: nn keys distributed across mm buckets puts n/mn/m in each. A lookup costs one hash computation, one array index, and then a scan of one chain, so the expected cost is

1+α1 + \alpha

comparisons. Read that formula carefully, because it says something surprising: the cost does not depend on nn. 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 α\alpha bounded by some constant. Choose a threshold, and the moment the table crosses it, make the table bigger. Sheehy uses ”α\alpha 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 1+α≤1+c1 + \alpha \le 1 + c, which is O(1)O(1).

The plate below is that arithmetic made physical. Feed it words and watch the load meter climb; the moment α\alpha 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.

The growth schedule of a chained hash table that starts with eight buckets and doubles whenever the load factor passes one.
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).

Plate IV The bucket counter. Every key prints its hash, its bucket, and whether it landed on an occupied one. The blue meter is the load factor α = n/mn/m against the ochre threshold at 1; cross it and the table doubles, re-placing every key in a single expensive step. Turn Rehash off to watch α climb past 2 and 3 with the chains growing to match. Then switch the feed to Adversarial. Play runs one event every 1.5 seconds.

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 h(k) mod mh(k) \bmod m, and mm has changed. Every key’s address is now potentially wrong. So growth means rehashing: build a fresh array of 2m2m buckets and re-place all nn 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 O(n)O(n) operation sitting inside a method we just promised was O(1)O(1), 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 m0m_0 buckets and doubles whenever α\alpha passes

  1. Then rehashes happen at n=m0+1n = m_0 + 1, then 2m0+12m_0 + 1, then 4m0+14m_0 + 1, and so on, and the ii-th of them re-places about 2im02^i m_0 keys. Insert nn keys altogether and the total re-placement work is
m0+2m0+4m0+⋯+n  ≤  2nm_0 + 2m_0 + 4m_0 + \cdots + n \;\le\; 2n

because a doubling series is dominated by its last term. At most 2n2n units of rehashing work spread over nn 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 nn. That is amortised O(1)O(1): 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 nn, so the total is 10+20+30+⋯+n10 + 20 + 30 + \cdots + n, which is O(n2)O(n^2) 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 O(n)O(n), 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 O(1)O(1)”, not "O(1)O(1)". 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

OperationListMappingHashMapping (expected)HashMapping (adversarial)
get(key), hitO(n)O(n)O(1)O(1)O(n)O(n)
get(key), missO(n)O(n)O(1)O(1)O(n)O(n)
put, new keyO(n)O(n)O(1)O(1) amortisedO(n)O(n)
put, overwriteO(n)O(n)O(1)O(1)O(n)O(n)
remove(key)O(n)O(n)O(1)O(1)O(n)O(n)
Build from nn keysO(n2)O(n^2)O(n)O(n) amortisedO(n2)O(n^2)
Iterate all keysO(n)O(n)O(n+m)O(n + m)O(n+m)O(n + m)
Extra memorynn entriesnn entries plus mm bucketssame
Keys in sorted ordersort them, O(nlog⁡n)O(n \log n)sort them, O(nlog⁡n)O(n \log n)same

Two rows deserve a second look.

Iterate all keys costs O(n+m)O(n + m), not O(n)O(n), because walking the table means visiting every bucket, including the empty ones. With α\alpha held near 1 the two terms are comparable and nobody minds. Hold α\alpha 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 O(1)O(1) 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.

  1. 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 nn keys built on it costs for a single get, and name the class from this lecture it has become.

  2. The agreement rule. Suppose a class defines __eq__ over its x and y fields but writes __hash__ to return id(self), which is different for every object. In two or three sentences, walk through what happens when you put a value under Point(1, 2) and then look it up with a freshly built, equal Point(1, 2). Is the entry lost, duplicated, or corrupted? Which of the two requirements from this lecture, agreement or spread, has been broken?

  3. The load factor, both directions. Using Plate IV with Rehash switched off, feed the words until α\alpha passes 2. Record the longest chain. Explain why the expected lookup cost 1+α1 + \alpha predicts what you are seeing, and then explain why the longest chain is bigger than α\alpha even with a good hash function. Finally: what would α=0.1\alpha = 0.1 buy you, and what would it cost?

  4. 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 nn 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.

  5. The slow one, built properly. Implement _find, put, and get so the mapping keeps the contract: one entry per key, overwrite on repeat, and KeyError on 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 ok
    python runs in your browser · first run downloads ~240 kb
    Plate 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

    _find is the loop you have written a dozen times: walk self._entries, and the moment e.key == key, return e. Falling off the end of the loop means the key is absent, so return None there.

    Hint two

    Both put and get should call _find first and then branch on whether it came back None. In put, a found entry gets its value reassigned in place; that is the “at most once” clause. In get, a None means raise 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.value

    Every one of these is O(n)O(n), 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 put costs 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.

  6. 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") % 16
    python runs in your browser · first run downloads ~240 kb
    Plate 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 each ch, reassign h = (h * 31 + ord(ch)) % (2 ** 32); return h. The empty string never enters the loop, which is why it hashes to the seed.

    Hint two

    bucket_of is one line and it is the formula from the lecture: hash the key, then take the remainder mod m. 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) % m

    The 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.

  7. The main event: growth. get is written for you, and it assumes the invariant that every pair sits in the bucket its current hash says it should. Your put must maintain that invariant, which means firing _rehash when the load factor passes 1, and your _rehash must 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 raised
    python runs in your browser · first run downloads ~240 kb
    Plate 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

    put has the same shape as ListMapping.put, only it searches one bucket instead of everything. Get the bucket with self._buckets[hash_string(key) % len(self._buckets)], scan it for a matching pair[0], and either overwrite pair[1] and return, or append a fresh [key, value] and bump self._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 += 1

    Two details carry the exercise. The overwrite branch returns early, so it never touches _length and never triggers growth: an overwrite does not make the table more crowded. And _rehash recomputes the bucket from scratch rather than reusing the old index, because h(key) % 8 and h(key) % 16 are different questions. Carrying the old index across is the single most common rehash bug, and it does not raise anything; it just loses keys.

  8. The superclass. Fill in the five derived methods on Mapping, using only self.get, self.put, and self._entries(). The checks run the identical assertions against both ListMapping and HashMapping, 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 kb
    Plate 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_or and contains are both try/except KeyError around self.get. Resist the urge to write if self.get(key): ...: a stored value of 0 or "" is present and falsy, and the checks put a zero in the table specifically to catch that.

    Hint two

    keys and values are one comprehension each over self._entries(), taking pair[0] and pair[1]. For setdefault, try to get; on KeyError, put the 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 default

    Now 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.

  9. 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 nn keys that forces every lookup to cost O(n)O(n), 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 O(1)O(1)” rather than "O(1)O(1)", and what the expectation is taken over.

Keys on this page

A figure's keys are its own: they answer once the figure has focus, so tab to it or click it first. Esc closes this sheet.