Hash tables: work out the bucket, look only there

You are signing up to a site with ten million accounts, and as you type a username it tells you at once whether the name is taken. Checking the names one by one would take up to ten million comparisons. Keeping them sorted and using binary search cuts that to about 24. A hash table usually needs one or two, however many names there are.

It borrows the trick that makes an array fast. An array never searches for index i: it works out where cell i is. A hash table works out where a key belongs, from the key itself, and looks only there.

hash function

Turns a key into a whole number, its hash. The same key always gives the same number; a good hash gives different keys unrelated-looking numbers.

bucket

The table is an array of m buckets, numbered 0 to m − 1. A key goes in bucket hash(key) mod m, the remainder when its hash is divided by m.

collision and chaining

A collision is two different keys landing in the same bucket. With chaining, each bucket keeps a list, its chain, of every key that landed there.

load factor

Keys per bucket: n keys divided by m buckets. With chaining it is the average chain length, and it can go above 1.

map and set

A map stores a value with each key, like a Python dict or a JavaScript Map. A set stores keys alone and says whether a key is there.

This table maps “cat” to 3, “dog” to 7 and “owl” to 5, in 7 buckets. Look up a stored key and a missing one, and count the keys each lookup compares.

Neither lookup touched another bucket. The table's hash function reads the character codes as the digits of a number in base 31: for “cat”, codes 99, 97 and 116, that is 99 × 31² + 97 × 31 + 116 = 98262. Then mod 7, the remainder after dividing by 7, turns any number into a bucket from 0 to 6: 98262 mod 7 = 3, so “cat” lives in bucket 3. put and get both work this out the same way, so they always agree.

Different keys can leave the same remainder: seven buckets can't give a million words one each, and even a handful of keys often clash. So each bucket holds a chain of its keys, and a lookup walks it, comparing keys, until it finds the one it wants or reaches the end.

Keeping the load factor down is the table's own job. This one, like Java's HashMap, lets it reach 0.75 and no more. A put that pushes past that moves the table to more buckets: here the first prime above twice the old count, so 7 buckets become 17 (Java's HashMap doubles instead). A key's bucket depends on m, so every key's bucket is worked out again: a rehash.

A set is the same table with keys alone, like Python's set and JavaScript's Set. For whole numbers the hash can simply be the number itself, so with 7 buckets, 20 goes in bucket 20 mod 7 = 6, easy to work out in your head.

This set holds 3, 10, 17 and 9. Before each step, predict the bucket, whether it is a collision, whether the table will resize, and whether a value is there. Add 24, run Contains on 31, then add 5.

Here is a whole chained map: buckets is a list of 5 chains of [key, value] pairs, and the hash is the sum of the key's character codes. put updates the pair holding its key or appends one, and get walks the same chain for the value. The program puts “no” and “on”, then gets “on”.

def bucket_of(key, m):
    total = 0
    for ch in key:
        total += ord(ch)
    return total % m

def put(buckets, key, value):
    chain = buckets[bucket_of(key, len(buckets))]
    for pair in chain:
        if pair[0] == key:
            pair[1] = value
            return
    chain.append([key, value])

def get(buckets, key):
    chain = buckets[bucket_of(key, len(buckets))]
    for pair in chain:
        if pair[0] == key:
            return pair[1]
    return -1

buckets = [[], [], [], [], []]
put(buckets, 'no', 4)
put(buckets, 'on', 9)
print(get(buckets, 'on'))

Summing the codes is a weak hash. It ignores letter order, so anagrams always collide, and it bunches short keys together: every three-letter lowercase word sums to between 291 and 366, so they land in at most 76 buckets however big the table. The visualiser's hash multiplies by 31 at each character, so position counts, and “cat” and “act” land in buckets 3 and 5 of 7.

Even the best general-purpose hash can't prevent collisions, and they come sooner than most people expect.

Short on average is not short always. Bad luck, a poor hash, or an attacker sending keys built to collide can pile many keys into one bucket (try it on Break it). That is why Python salts its string hash with a random seed each time it starts, and why Java's HashMap turns a very long chain into a balanced tree.

The limit is kept by resizing, and resizing has a trap of its own.

One thing a hash table can't do is sorted order: buckets scatter keys with no regard to which is smaller, so it can't list its keys in order or find the smallest quickly. That is a job for a binary search tree.

• A key lives in bucket hash(key) mod m, so put, get and delete search one bucket's chain, not every key.
• Collisions come early, long before the table is full. Chaining keeps each bucket's keys in a list.
• The load factor n/m is the average chain length. Kept below a limit, with an even hash, every operation is O(1) on average; if everything collides, it is O(n).
• Passing the limit grows the table by a constant factor and rehashes every key, because buckets depend on m: O(n) for that put, O(1) amortised.
• A set is the same table without values. Neither keeps its keys in sorted order.
• Next: Bloom filters, which hash each item to a few bits (the Bloom filter visualiser), and string matching, where Rabin–Karp hashes a sliding window of text. Hash maps also sit inside caches, and consistent hashing replaces mod N across servers. Practise with Two Sum, Spot a Repeated Number and Group Anagrams, or open the hash table and hash set visualisers to try more operations.