What Makes a Hash Function Good

300 keys into 101 buckets. ideal: 101 buckets used, biggest 3

function                      buckets      biggest    avg probes per find
first 3 digits only                 2          250                 108.83
last 2 digits only                100            4                   2.11
division, k mod 101               101            4                   2.09
folding, 3 + 3 digits             101            4                   2.10

the first-3-digits function used 2 buckets for 300 keys,
because almost every PRN begins 202. its biggest bucket holds 250,
so a search in it compares up to 250 records: the table became a list.
the last-2-digits function used 100 buckets, which looks fine, but it
can NEVER use more than 100 whatever the table size, so a bigger
table would not help it at all.

Two distinct failures there, and an answer should separate them.

The first three digits collapse the table, because the keys share that prefix. Three hundred records in two buckets is a linked list with extra steps.

The last two digits look acceptable at m = 101, and they are a trap: that function's range is only 0 to 99, so enlarging the table to 1009 buckets would leave 909 of them permanently empty. A function must be able to reach every bucket.

Test 5: avalanche, measured

M = 97


def last_two(k):
    return (k % 100) % M


def division(k):
    return k % M


def mid_square(k):
    square = str(k * k)
    start = (len(square) - 4) // 2
    return int(square[start:start + 4]) % M


NEAR = [700100, 700101, 700102, 700103, 700104, 700105, 700106, 700107]

print("eight keys differing only in the last digit, into %d buckets:" % M)
print("%-22s %s" % ("function", "slots"))
for name, fn in (("last 2 digits", last_two),
                 ("division, k mod 97", division),
                 ("mid-square", mid_square)):
    slots = [fn(k) for k in NEAR]
    print("%-22s %-40s %d distinct" % (name, str(slots), len(set(slots))))

print()
GROUPED = [700000 + i * 100 for i in range(8)]     # keys 100 apart
print("eight keys 100 apart (so the last two digits are IDENTICAL):")
print("%-22s %s" % ("function", "slots"))
for name, fn in (("last 2 digits", last_two),
                 ("division, k mod 97", division),
                 ("mid-square", mid_square)):
    slots = [fn(k) for k in GROUPED]
    print("%-22s %-40s %d distinct" % (name, str(slots), len(set(slots))))

print()
print("on the first set every function separated the keys.")
print("on the second, the last-2-digits function sent all eight to ONE slot,")
print("because the two digits it reads are the same in all eight keys.")
print("avalanche is not about random keys. it is about the keys you get.")

eight keys differing only in the last digit, into 97 buckets:
function               slots
last 2 digits          [0, 1, 2, 3, 4, 5, 6, 7]                 8 distinct
division, k mod 97     [51, 52, 53, 54, 55, 56, 57, 58]         8 distinct
mid-square             [24, 67, 13, 56, 2, 45, 88, 34]          8 distinct

eight keys 100 apart (so the last two digits are IDENTICAL):
function               slots
last 2 digits          [0, 0, 0, 0, 0, 0, 0, 0]                 1 distinct
division, k mod 97     [48, 51, 54, 57, 60, 63, 66, 69]         8 distinct
mid-square             [0, 24, 50, 69, 2, 25, 59, 95]           8 distinct

on the first set every function separated the keys.
on the second, the last-2-digits function sent all eight to ONE slot,
because the two digits it reads are the same in all eight keys.
avalanche is not about random keys. it is about the keys you get.

Test 3: cheap, measured against what it replaces

M = 1009
N = 4000
KEYS = [202000 + i * 7 for i in range(N)]


def count_division(k):
    return 1                                 # one modulo


def count_mid_square(k):
    return 4                                 # a multiply, a string cut, a parse, a modulo


def count_folding(k):
    return len(str(k)) // 3 + 2              # a cut and parse per piece, then a modulo


def count_horner(text):
    return 2 * len(text)                      # a multiply and an add per character


import math

print("what a hash costs, in rough arithmetic operations per lookup:")
print("%-28s %12s" % ("function", "operations"))
for name, ops in (("division, k mod m", count_division(0)),
                  ("mid-square", count_mid_square(0)),
                  ("folding a 6 digit key", count_folding(202000)),
                  ("Horner over a 12 char string", count_horner("a" * 12))):
    print("%-28s %12d" % (name, ops))

print()
print("what it replaces: a balanced tree search over %d records needs" % N)
print("about %d key comparisons." % math.ceil(math.log2(N)))
print()
print("so a hash costing 1 to 4 operations is clearly worth it, and a hash")
print("costing more than about %d would not be. that is the whole test:" % math.ceil(math.log2(N)))
print("a hash function must be cheaper than the search it removes.")

what a hash costs, in rough arithmetic operations per lookup:
function                       operations
division, k mod m                       1
mid-square                              4
folding a 6 digit key                   4
Horner over a 12 char string           24

what it replaces: a balanced tree search over 4000 records needs
about 12 key comparisons.

so a hash costing 1 to 4 operations is clearly worth it, and a hash
costing more than about 12 would not be. that is the whole test:
a hash function must be cheaper than the search it removes.

That is the practical boundary. A cryptographic hash such as SHA-256 is beautifully uniform and costs hundreds of operations, so it is the wrong tool for a hash table, and the right tool when the uniformity has to hold against an attacker. Chapter 109 returns to that.

Measuring uniformity properly

Counting the biggest bucket is a blunt instrument. The standard measure compares the observed bucket sizes with what a perfectly even spread would give.

A perfectly even spread scores 0 when m divides n exactly, and a little above 0 otherwise, since the buckets then cannot all hold the same number. A spread no better than pure chance scores about m-1. A function that dumps every key into one bucket scores n x (m-1), which is the maximum. Lower is better, and the score means something only against those three landmarks, which the listing prints.

M = 101
KEYS = [202000 + i for i in range(250)] + [201000 + i * 3 for i in range(50)]


def spread(fn, keys, m):
    table = [0] * m
    for k in keys:
        table[fn(k)] += 1
    expected = len(keys) / m
    return sum((c - expected) ** 2 for c in table) / expected


def first_three(k):
    return (k // 1000) % M


def last_two(k):
    return (k % 100) % M


def division(k):
    return k % M


def folded(k):
    d = str(k)
    return (int(d[:3]) + int(d[3:])) % M


perfect = [0] * M
for i, _ in enumerate(KEYS):
    perfect[i % M] += 1
expected = len(KEYS) / M
best = sum((c - expected) ** 2 for c in perfect) / expected
all_in_one = ((len(KEYS) - expected) ** 2 + (M - 1) * expected ** 2) / expected

print("%d keys into %d buckets. lower is better. three landmarks:" % (len(KEYS), M))
print("   best possible, an even spread     : %8.1f" % best)
print("   a spread no better than chance    : %8.1f" % (M - 1))
print("   everything in one bucket, n(m-1)  : %8.1f" % all_in_one)
print("(the best is not 0 because %d does not divide evenly into %d buckets.)"
      % (len(KEYS), M))
print()
print("%-26s %14s" % ("function", "spread score"))
for name, fn in (("first 3 digits only", first_three),
                 ("last 2 digits only", last_two),
                 ("division, k mod 101", division),
                 ("folding, 3 + 3 digits", folded)):
    print("%-26s %14.1f" % (name, spread(fn, KEYS, M)))

print()
good = [spread(fn, KEYS, M) for fn in (last_two, division, folded)]
print("the three usable functions score %.1f to %.1f, well under the %d of a"
      % (min(good), max(good), M - 1))
print("chance spread, so all three beat chance on these keys.")
bad = spread(first_three, KEYS, M)
print("the first-3-digits function scores %.0f, which is %.0f%% of the way to"
      % (bad, 100 * bad / all_in_one))
print("the %.0f of putting every key in one bucket. it is not merely worse;"
      % all_in_one)
print("it is most of the way to having no hash function at all.")

300 keys into 101 buckets. lower is better. three landmarks:
   best possible, an even spread     :      1.0
   a spread no better than chance    :    100.0
   everything in one bucket, n(m-1)  :  30000.0
(the best is not 0 because 300 does not divide evenly into 101 buckets.)

function                     spread score
first 3 digits only               21583.3
last 2 digits only                   25.2
division, k mod 101                  20.5
folding, 3 + 3 digits                22.5

the three usable functions score 20.5 to 25.2, well under the 100 of a
chance spread, so all three beat chance on these keys.
the first-3-digits function scores 21583, which is 72% of the way to
the 30000 of putting every key in one bucket. it is not merely worse;
it is most of the way to having no hash function at all.

The rule that matters most

A hash function is good or bad only with respect to a key set. k mod 101 is excellent on the PRNs above and catastrophic on keys that are all multiples of 101. There is no function that is uniform on every possible input, because a function with m outputs and a larger domain must send many inputs to each output, and an adversary or an unlucky data source can pick them.

So the practical procedure is:

1. find out what the keys actually look like;
2. choose a method that uses all of a key of that shape;
3. choose m as a prime away from powers of 2;
4. measure, with a spread score or at least the biggest bucket, on real keys;
5. where an attacker chooses the keys, use a randomised or keyed hash, chapter 109.

Quick revision

• Five tests: uniform, deterministic, cheap, uses the whole key, and avalanche.
• A search costs the length of its bucket, so the BIGGEST bucket sets the worst case, not the average.
• Using part of the key is the commonest failure: the first three digits of 300 PRNs that share a prefix filled 2 buckets, the biggest holding 250 records.
• A function whose range is smaller than the table can never fill it: a last-two-digits hash is stuck at 100 buckets however large m is.
• Avalanche is about the keys you actually get: the last-two-digits hash sent eight keys 100 apart to one slot.
• Cheap means cheaper than the search it replaces: 1 to 4 operations against about 12 comparisons for a balanced tree over 4,000 records.
• A cryptographic hash is uniform and far too slow for a hash table, and is the right choice only when an attacker chooses the keys.
• Uniformity is measured by the spread score, sum of (observed - expected) squared over expected; lower is better, read against three landmarks: the best achievable, about m-1 for a chance spread, and n(m-1) for everything in one bucket.
• On 300 PRNs in 101 buckets the three usable functions scored 20.5 to 25.2 against a best of 1.0 and a chance figure of 100, while the first-three-digits function scored 21,583 of a possible 30,000.
• No function is uniform on all inputs, so a function is only good relative to a key set: measure on real keys.

Test yourself

1. List the five properties of a good hash function. Uniform over the actual keys; deterministic; cheap to compute; uses every part of the key; and avalanche, so similar keys reach unrelated slots.

2. Why does the biggest bucket matter more than the average? Because a search costs the length of the bucket it lands in, so the longest bucket fixes the worst case cost.

3. Give the measured failure of a hash that uses only part of the key. Three hundred PRNs mostly beginning 202, hashed on their first three digits, filled only 2 of 101 buckets, and the largest bucket held 250 records, so a search in it compared up to 250 keys.

4. Why is a hash function whose range is 0 to 99 unacceptable even when it spreads keys evenly? Because it can never reach any bucket above 99, so enlarging the table cannot reduce the bucket lengths.

5. What is avalanche, and give the chapter's example of its absence. Keys that differ slightly should land in unrelated slots. A last-two-digits hash sent eight keys exactly 100 apart to a single slot, because the digits it reads are identical in all eight.

6. State the cost test precisely. The hash must cost less than the search it removes. Division costs one modulo against about 12 comparisons for a balanced tree over 4,000 records, so it passes easily; a cryptographic hash costing hundreds of operations fails.

7. How is uniformity measured? By the spread score: the sum over buckets of (observed minus expected) squared divided by expected, where expected is n/m. Lower is better, judged against three landmarks: the best achievable for those n and m, which is 0 only when m divides n exactly; about m-1 for a spread no better than chance; and n(m-1) for every key in one bucket.

8. Why can no hash function be uniform on every input? Because the set of possible keys is larger than the set of m slots, so many keys must share each slot, and a key set can be drawn entirely from one of those groups.