Open addressing and load factor

The second plan for collisions keeps no chains at all. Every key sits in the array itself, one key per slot. When a key’s slot is taken, it tries other slots in a fixed order until it finds a free one. This plan is called open addressing. Python’s dict uses it.

One key per slot

Each key has a home slot, hash(key) % m. If the home slot is taken, the simplest rule is to try the next slot, then the next, wrapping round from the last slot to slot 0. This rule is called linear probing. Each look at a slot is a probe.

The order of slots a key tries is its probe sequence. Insert and find must use the same sequence. A find walks the sequence until it meets the key (found) or an empty slot (not there). An empty slot proves the key is missing, because the insert would have stopped at that slot, or earlier.

In the first variant, 23, 43 and 13 all have home slot 3. They fill slots 3, 4 and 5 in a row. A block of taken slots like this is called a cluster. Any new key whose home slot falls in the cluster must walk to its end, and then it makes the cluster one longer. Long clusters grow faster than short ones, because more home slots fall inside them. This is the main weakness of linear probing.

Removing needs a marker

The last variant of the figure shows the problem. Emptying the slot of a removed key cuts the probe sequence of every key stored after it. A later find stops at the new empty slot and wrongly says “not there”.

The fix is a deleted marker, often called a tombstone. The slot is not empty; it says “a key was here, keep going”. The three jobs treat it differently:

• Find skips markers and keeps going.
• Insert remembers the first marker it passes, but keeps going until an empty slot. Only then does it know the key is not already stored further on. Then it puts the key in the remembered marker’s slot.
• Remove finds the key and puts a marker in its slot.

DEL = object()                 # a unique marker, equal to nothing else

def find(slots, key):
    m = len(slots)
    i = hash(key) % m
    for _ in range(m):             # never more than m probes
        if slots[i] is None:
            return -1              # empty: the key is not here
        if slots[i] is not DEL and slots[i] == key:
            return i
        i = (i + 1) % m
    return -1

Markers still slow finds down, because finds must walk past them. When too many slots hold markers, the table is rebuilt: every live key is inserted into a fresh array, and the markers disappear.

How full is too full

With open addressing, the load factor α = n / m can never pass 1: there is one slot per key. As α nears 1, probe sequences get long. For a clean argument, imagine a perfect version of probing where every probe lands on a random slot not tried yet.

Look for a missing key. The first probe hits a taken slot with chance α. If it does, the second probe hits a taken slot with chance a little less than α, and so on. So the chance of needing more than j probes is at most j copies of α multiplied together, written α^j (and α⁰ is 1). Adding these chances up, the expected number of probes is at most 1 + α + α² + α³ + …. That sum equals 1 / (1 − α), the standard formula for adding up powers of a number below 1.

Linear probing does worse, because of clusters. Donald Knuth worked out its averages in 1963. The table compares them, including chaining (lesson 2) for reference:

So open-addressing tables grow early. Python’s dict grows when it is two-thirds full. Java’s HashMap (which uses chaining) grows at α = 0.75. Growing works as in lesson 2: double the array and reinsert every live key, O(1) amortised per insert. Markers count as taken when deciding to grow, because finds must walk past them.

Other probe orders

Linear probing is one choice of probe sequence. Two others are common:

• Quadratic probing tries home + 1, home + 4, home + 9, … (adding the square numbers). Keys that share a cluster spread out faster. It needs care: with a badly chosen m, the sequence can skip some slots for ever.
• Double hashing uses a second hash to choose the step size: home, home + s, home + 2s, …, where s comes from the key. Two keys with the same home slot usually get different steps, so they do not follow each other. If m is a power of 2 and s is odd, the sequence visits every slot. Lesson 8 uses this trick.

Linear probing is still widely used, because it reads neighbouring slots. Neighbouring slots sit together in memory, and the processor loads them together, so each probe after the first is very cheap. In practice this often beats the cleverer orders.