Hash functions, universal hashing and flooding

A hash function turns a key into a number of fixed size, and a hash table uses that number to choose a bucket, so the function decides whether keys spread out or pile up. Hash functions for tables must be fast, give equal keys equal hashes and spread different keys evenly. Spreading is easy to achieve for ordinary data and impossible to promise for every input: anyone who knows a fixed hash function can choose keys that all collide, and a server fed such keys turns each O(1) operation into O(n). Feeding a table keys that collide on purpose is called hash flooding. Universal hashing picks the table’s hash function at random from a family, so no fixed set of keys is bad for every run. This lesson builds a polynomial hash for strings, shows how collisions arise, how flooding works and which hashes of real languages resist it.

What a hash function for a table must do

1. Consistent within a run: C++’s std::hash only has to agree with itself during one execution, which leaves room for salted hashes.
2. Equal keys, equal hashes, as the previous lessons showed.
3. Spread: different keys share a bucket about as rarely as random choices would.
4. Fast: every insert, find and delete computes it.

Cryptographic hash functions such as SHA-256 solve a different problem: nobody should be able to find two inputs with the same output, which costs far more work per key than a table can spend. Table hashes may collide, as long as collisions stay rare for the keys the table receives.

A polynomial hash for strings

A common hash for a string s of length n treats its character codes as the digits of a number in base B:

Horner’s rule computes it in one pass: multiply the running value by B and add the next code. M is usually a large prime and B larger than any character code, and a character’s position matters, so “ab” and “ba” hash differently.

"""A polynomial hash for strings, computed with Horner's rule, and a search for two strings with the same hash.

h(s) = s[0]·B^(n−1) + s[1]·B^(n−2) + … + s[n−1] (mod M), where s[i] is the code of the i-th character.
"""
import random


def poly_hash(text, base, mod):
    h = 0
    for ch in text:
        h = (h * base + ord(ch)) % mod
    return h


B, M = 131, 1_000_000_007
h = 0
for ch in "kochi":
    h = (h * B + ord(ch)) % M
    print(f"after {ch!r}: h = {h:,}")
print(f"poly_hash('kochi') = {poly_hash('kochi', B, M):,}")

# With a small modulus, two different strings soon share a hash: hash random six-letter strings until two collide.
small = 1_009
rng = random.Random(4)
seen = {}
count = 0
while True:
    word = "".join(rng.choice("abcdefghijklmnopqrstuvwxyz") for _ in range(6))
    if word in seen.values():
        continue
    count += 1
    code = poly_hash(word, B, small)
    if code in seen:
        print(f"modulus {small:,}: '{seen[code]}' and '{word}' both hash to {code}, after {count} strings")
        break
    seen[code] = word

after 'k': h = 107
after 'o': h = 14,128
after 'c': h = 1,850,867
after 'h': h = 242,463,681
after 'i': h = 762,742,099
poly_hash('kochi') = 762,742,099
modulus 1,009: 'picrja' and 'bgfvtk' both hash to 889, after 50 strings

The second part shows why M must be large: with only 1,009 possible hashes, two random six-letter strings shared one after 50 strings, close to the birthday estimate of about 40. With M = 2⁶¹ − 1 the same effect needs billions.

Hash flooding: collisions chosen on purpose

A fixed hash function is public: it is in the language’s documentation or source code. An attacker can compute, offline, thousands of keys that land in one bucket and send them as the fields of a web form or the keys of a JSON object. Each insertion then compares the new key with all the earlier ones, and n keys cost O(n²) work. Crosby and Wallach described such algorithmic complexity attacks in 2003; in 2011 the oCERT-2011-003 advisory reported hash flooding against many web platforms at once.

The defences fall into a few families, each in one sentence:

• Universal hashing chooses the hash function at random from a family when the table is created, so the attacker cannot know which keys collide.
• Keyed hashes such as SipHash mix a secret random key into every hash; CPython does this for strings and bytes.
• Tree bins turn a long bucket into a balanced tree, as Java’s HashMap has done since JEP 180.
• Input limits cap how many keys a single request may create, which bounds the damage.

Which hashes are salted: a check in CPython

Python’s data model says that str and bytes hashes are salted with a random value, constant within one process, to protect a dict against chosen inputs. Other types are not covered:

"""Which of CPython's hashes are salted: str changes from process to process, int does not.

Each line marked "process" comes from a fresh Python started with a fixed PYTHONHASHSEED, so this file prints the
same every time, while three ordinary runs would print three unpredictable values.
"""
import os
import subprocess
import sys

show = "print(hash('kochi'), hash(12345))"
for seed in ("1", "2", "3"):
    env = {**os.environ, "PYTHONHASHSEED": seed}
    out = subprocess.run([sys.executable, "-c", show], env=env, capture_output=True, text=True, check=True).stdout.split()
    print(f"process with PYTHONHASHSEED={seed}: hash('kochi') = {int(out[0]):>20}, hash(12345) = {out[1]}")

info = sys.hash_info
print(f"string algorithm: {info.algorithm}, hash width: {info.width} bits")
print(f"int hashes are taken modulo {info.modulus:,} (2**61 - 1)")
for k in (2**61 - 1, 2**61, 3 * (2**61 - 1)):
    print(f"hash({k:,}) = {hash(k)}")

process with PYTHONHASHSEED=1: hash('kochi') = -4334537901555037316, hash(12345) = 12345
process with PYTHONHASHSEED=2: hash('kochi') =   245045104673291647, hash(12345) = 12345
process with PYTHONHASHSEED=3: hash('kochi') = -8355054294460551174, hash(12345) = 12345
string algorithm: siphash13, hash width: 64 bits
int hashes are taken modulo 2,305,843,009,213,693,951 (2**61 - 1)
hash(2,305,843,009,213,693,951) = 0
hash(2,305,843,009,213,693,952) = 1
hash(6,917,529,027,641,081,853) = 0

Three processes with different PYTHONHASHSEED values gave three unrelated hashes for “kochi” and the same 12345 for the number 12345. On a 64-bit build an int’s hash is the number modulo 2⁶¹ − 1, so every multiple of 2⁶¹ − 1 hashes to 0, and a table keyed by numbers that an outsider chooses is open to flooding.

Universal hashing in brief

Carter and Wegman introduced universal hashing in 1979. A family of hash functions is universal if, for any two different keys x and y, a function picked at random from the family makes them collide with probability at most 1/m, where m is the number of buckets. One such family for integer keys takes a prime p larger than any key and random numbers a and b:

The guarantee is about the random choice, not the keys: whatever keys an attacker picks in advance, each pair collides with probability at most 1/m. A random base B does the same for the polynomial string hash.

Check yourself

Universal hashing: the collision bound, proved and measured Pro: opens with a Pro, Premium or Ultimate pass

Hash flooding reproduced in Python, Java and C++, and the defences that work Pro: opens with a Pro, Premium or Ultimate pass

Interview questions

Key takeaways

• A table’s hash must be consistent within a run, equal for equal keys, well spread and fast, but not cryptographic.
• A polynomial hash reads a string’s codes as digits in base B modulo a large prime M.
• A fixed, known hash can be flooded: chosen keys make n insertions cost O(n²).
• Universal hashing picks the function at random, so every pair of keys collides with probability at most 1/m.
• CPython salts str and bytes hashes but not int hashes.