Hashing, collisions, and the square-root law behind them

Turning anything into a number

A hash function takes an input of any size and returns a fixed-size number, in a way that scatters inputs evenly across the possible outputs and makes similar inputs land far apart. Change one character of a document and its 64-bit hash changes in about half its bits. That property, plus speed, is why hashing sits under half the data structures in a machine-learning pipeline.

The hash table is the first. Store an item in the bucket its hash points to; to check membership, hash the query and look in that one bucket. The lookup does not depend on how many items are stored. That is the O(1) from the Big-O lesson, and it is why item in some_set is a thousand times faster than item in some_list at a million items: the set hashes, the list scans.

Collisions are a counting problem

Two different inputs can hash to the same value. With n items and m possible hash values, the number of pairs is about n²/2 and each pair collides with probability 1/m, so

expected collisions ≈ n² / 2m
P(at least one)     ≈ 1 − exp(−n² / 2m)

Collisions become likely when n²/2m approaches 1, that is when n ≈ √(2m). This is the birthday bound: you need only the square root of the number of possible values before two items share one. In a room of 23 people, with 365 possible birthdays, the chance of a shared one is 50 per cent, and 1.18 × √365 = 22.5.

Apply it to hash sizes:

32-bit hash, m = 4.3 × 10^9:   collision likely by n ≈ 77,000 items
64-bit hash, m = 1.8 × 10^19:  collision likely by n ≈ 5 × 10^9 items
128-bit:                        n ≈ 2 × 10^19

A million documents keyed by a 32-bit hash will certainly collide: n²/2m = 116, so 1 − e^(−116) is 1 to every decimal place. The same million under a 64-bit hash collide with probability 2.7 × 10^-8. If a deduplication or caching system uses a 32-bit key, it is silently merging unrelated records somewhere past the first hundred thousand. This is a real and common bug, and the arithmetic above finds it before the data does.

The hashing trick

When a vocabulary is enormous, every distinct URL, user id or n-gram, you can skip building a dictionary and hash each feature directly to one of 2^20 positions in a vector. Collisions are tolerated: two features sharing a slot add their values, which acts as a small amount of noise. How much? With a million features in a million slots, the count per slot is Poisson with mean 1: 37 per cent of slots are empty, 37 per cent hold one feature, 26 per cent hold two or more. A quarter of the features share a slot with something. If that is too much, use 2^24 slots and the sharing falls to about 6 per cent; the arithmetic tells you the trade before you train.

Bloom filters: membership in a tenth of the space

To remember which of a billion URLs you have already fetched, a set of the URLs themselves is tens of gigabytes. A Bloom filter keeps a bit array of m bits and k hash functions; to add an item, set the k bits it hashes to; to query, check whether all k are set. It never says "absent" wrongly, but it can say "present" wrongly, with probability

P(false positive) ≈ (1 − e^(−kn/m))^k

At ten bits per item and k = 7, that is (1 − e^(−0.7))^7 = 0.8 per cent. A billion URLs in 1.25 GB, with under one wrong answer in a hundred, and no way to list what is in it. The formula lets you buy exactly the error rate you can afford.

Locality-sensitive hashing: collisions on purpose

Ordinary hashing scatters similar inputs apart. For deduplication and nearest-neighbour search you want the opposite: similar inputs should collide. Locality-sensitive schemes are built so that the probability two items share a hash equals, or tracks, their similarity. The MinHash signature of a document, for instance, collides with another's with probability equal to the Jaccard overlap of their word sets. Bucket by a few signature bands and only compare within buckets, and the all-pairs deduplication from two lessons ago becomes near-linear. The pairs that never shared a bucket were, with high probability, never near-duplicates.

The reproducibility trap

Python randomises its string hashing per process, so that adversarial inputs cannot force collisions. A consequence: the iteration order of a set of strings differs between runs. A pipeline that builds a vocabulary by iterating a set will assign different ids on Tuesday than on Monday, and a model trained on one will read garbage from the other. Set PYTHONHASHSEED=0 for reproducible runs, or, better, sort before assigning ids. The lesson on random numbers in module 8 has the rest of that story.

In code

import hashlib, math
h = int(hashlib.blake2b(b"some document", digest_size=8).hexdigest(), 16)  # 64-bit
n, m = 1_000_000, 2**32
print(1 - math.exp(-n*n / (2*m)))     # 1.0: a 32-bit key will collide

Use a 64-bit or 128-bit digest for anything you key on, size the Bloom filter from the formula, and read the birthday bound as the general warning it is: whenever something is drawn at random from m possibilities, a repeat is due after about √m draws, not m.