Chaining

The simplest plan for collisions: let a bucket hold more than one key. Each bucket keeps a short list of its keys, called a chain. This plan is called chaining.

A chain in every bucket

Every job starts the same way. Hash the key, take % m, and go to that one bucket. Then walk its chain and compare each key with ==:

• Find: walk the chain until you meet the key, or the chain ends.
• Insert: find first. If the key is there, change its value. If not, add it to the chain.
• Remove: find it, then take it out of the chain.

The chain can be a Python list, or a linked list as in the LINK station. Step through some inserts, finds and a removal. Then switch to “Grow the table”:

A small version in Python:

class ChainTable:
    def __init__(self, m=8):
        self.b = [[] for _ in range(m)]     # m empty chains

    def find(self, key):
        for k, v in self.b[hash(key) % len(self.b)]:
            if k == key:
                return v
        return None

The hash only chooses where to look. Whether a key matches is decided by ==. Two different keys can have the same hash, so a table must never treat equal hashes as equal keys.

The load factor and the cost

The cost of a job is one hash, plus the walk along one chain. So the question is: how long is a chain?

The load factor is the number of keys divided by the number of buckets. It is written α (the Greek letter alpha): α = n / m. With 6 keys in 5 buckets, α = 1.2.

To reason about chain lengths, assume the hash spreads keys perfectly: each key is equally likely to land in any of the m buckets, whatever the other keys did. Real hash functions are not perfect, but good ones behave close to this.

Now look for a key x that is not in the table. Its search walks the whole of one chain. Each of the n keys in the table is in that chain with chance 1/m. Adding these chances up, the chain is expected to hold n · (1/m) = α keys. So a search for a missing key costs O(1 + α) on average: 1 for the hash, α for the walk.

A search for a key that is there stops part way along its chain. On average it passes about half of the other keys in the chain, so it costs about 1 + α/2. That is also O(1 + α).

Growing the table

As keys arrive, n grows, and with it α. To keep α small, the table grows: when α passes a limit, make a new array with twice as many buckets and move every key. A key’s bucket depends on m, so every key must be hashed again into the new array. This is called rehashing.

One growth moves all n keys, which costs O(n). But growths are rare. Suppose the table starts with 8 buckets and doubles when n passes m. By the time it holds n keys, the growths have moved at most 8 + 16 + 32 + … + n keys, which is less than 2n. Shared out over the n inserts, that is less than 2 moves per insert. So insert is O(1) on average over a sequence of inserts. This kind of “average over a sequence” cost is called amortised cost (ARRS-1 and BIGO-7 used the same argument for a growing list).

The worst case

The O(1) is an average, and it depends on the hash spreading the keys. If every key lands in the same bucket, the table becomes one long chain, and every job costs O(n). Inserting n keys then costs 1 + 2 + … + n, which is O(n²).

This happens with a poor hash function, or when someone chooses the keys on purpose to collide. Lesson 4 shows that attack and the defence. Java’s HashMap adds a second defence: when one chain grows past 8 keys, it turns that chain into a balanced search tree (BALT station), so even the worst chain costs only O(log n).