Hash Functions
Chapter One Hundred One
Syllabus topic Module 2, "hash functions"
Pages 339 to 347 of 411
In one line
A hash function turns a key into a slot number; the four classical methods are division, mid-square, folding and multiplication, and strings are handled by combining their characters into a number first.
The job
h : any key -> an integer in { 0, 1, ... , m-1 }
Two absolute requirements, before any question of quality:
It must be deterministic. The same key must always give the same slot, or a stored record can never be found. This rules out anything involving the time, a random number or a memory address.
Its output must be in range. Every method below ends with mod m for exactly this reason.
Method 1: the division method
h(k) = k mod m
The remainder when the key is divided by the table size. The simplest method, the fastest, and the one used by default.
def division(k, m):
return k % m
M = 11
KEYS = [25, 37, 108, 1001, 56, 77, 92]
print("the division method, h(k) = k mod %d" % M)
print()
print("%8s %10s %8s %s" % ("key", "k mod m", "slot", "the arithmetic"))
for k in KEYS:
print("%8d %10d %8d %d = %d x %d + %d"
% (k, division(k, M), division(k, M), k, M, k // M, k % M))
print()
table = [[] for _ in range(M)]
for k in KEYS:
table[division(k, M)].append(k)
for i, chain in enumerate(table):
print(" [%2d] %s" % (i, chain if chain else ""))
print()
print("7 keys in 11 slots, and slot 0 took two of them (77 and 1001).")
print("77 mod 11 =", 77 % 11, "and 1001 mod 11 =", 1001 % 11)the division method, h(k) = k mod 11
key k mod m slot the arithmetic
25 3 3 25 = 11 x 2 + 3
37 4 4 37 = 11 x 3 + 4
108 9 9 108 = 11 x 9 + 9
1001 0 0 1001 = 11 x 91 + 0
56 1 1 56 = 11 x 5 + 1
77 0 0 77 = 11 x 7 + 0
92 4 4 92 = 11 x 8 + 4
[ 0] [1001, 77]
[ 1] [56]
[ 2]
[ 3] [25]
[ 4] [37, 92]
[ 5]
[ 6]
[ 7]
[ 8]
[ 9] [108]
[10]
7 keys in 11 slots, and slot 0 took two of them (77 and 1001).
77 mod 11 = 0 and 1001 mod 11 = 0The choice of m is not free, and this is the part worth marks. Two warnings:
Do not use a power of 10. With m = 1000, k mod m is the last three digits, so the rest of the key is ignored entirely.
Hash Functions
Do not use a power of 2. With m = 16, k mod m is the last four bits, so again most of the key is thrown away.
Use a prime, ideally not close to a power of 2. A prime mixes the whole key into the remainder. Chapter 102 measures how much difference this makes.
KEYS = [i * 10 for i in range(1, 41)] # 10, 20, 30 ... 400: realistic enough
print("40 keys, all multiples of 10:", KEYS[:6], "...", KEYS[-1])
print()
print("%10s %10s %12s %14s %s"
% ("table size", "kind", "slots used", "biggest slot", "empty slots"))
for m in (10, 16, 20, 11, 13, 41):
table = [0] * m
for k in KEYS:
table[k % m] += 1
kind = {10: "power of 10", 16: "power of 2", 20: "even"}.get(m, "PRIME")
print("%10d %10s %12d %14d %14d"
% (m, kind, sum(1 for c in table if c), max(table),
sum(1 for c in table if c == 0)))
print()
print("with m = 10 every one of the 40 keys landed in slot 0.")
print("with m = 41 the 40 keys spread over 40 different slots.")
print("same keys, same method: the table SIZE decided everything.")40 keys, all multiples of 10: [10, 20, 30, 40, 50, 60] ... 400
table size kind slots used biggest slot empty slots
10 power of 10 1 40 9
16 power of 2 8 5 8
20 even 2 20 18
11 PRIME 11 4 0
13 PRIME 13 4 0
41 PRIME 40 1 1
with m = 10 every one of the 40 keys landed in slot 0.
with m = 41 the 40 keys spread over 40 different slots.
same keys, same method: the table SIZE decided everything.Method 2: the mid-square method
Square the key, then take some digits from the middle of the square.
h(k) = the middle r digits of (k x k), taken mod m
The reasoning: the middle digits of a square depend on every digit of the key, because every digit contributes to the middle of the product. The ends do not have that property.
def mid_square(k, m, digits=2):
"""Square the key, take `digits` digits from the middle, then mod m."""
square = str(k * k)
if len(square) <= digits:
middle = square
else:
start = (len(square) - digits) // 2
middle = square[start:start + digits]
return int(middle) % m, square, middle
M = 11
print("the mid-square method, 2 middle digits, then mod %d" % M)
print()
print("%8s %14s %10s %8s" % ("key", "k x k", "middle 2", "slot"))
for k in (123, 456, 789, 321, 654):
slot, square, middle = mid_square(k, M)
print("%8d %14s %10s %8d" % (k, square, middle, slot))
print()
print("why the middle: 123 x 123 =", 123 * 123)
print(" the last digit, 9, comes only from 3 x 3.")
print(" the first digit, 1, comes mostly from 1 x 1.")
print(" the middle digits mix all three digits of the key.")
print()
near = (71234, 71235, 71236, 71237)
print("four keys differing only in the LAST digit:")
for k in near:
slot, square, middle = mid_square(k, 97)
print(" %d x %d = %-12s middle %s -> slot %d" % (k, k, square, middle, slot))
slots = [mid_square(k, 97)[0] for k in near]
print(" slots:", slots, " all different:", len(set(slots)) == len(slots))Hash Functions
the mid-square method, 2 middle digits, then mod 11
key k x k middle 2 slot
123 15129 51 7
456 207936 79 2
789 622521 25 3
321 103041 30 8
654 427716 77 0
why the middle: 123 x 123 = 15129
the last digit, 9, comes only from 3 x 3.
the first digit, 1, comes mostly from 1 x 1.
the middle digits mix all three digits of the key.
four keys differing only in the LAST digit:
71234 x 71234 = 5074282756 middle 28 -> slot 28
71235 x 71235 = 5074425225 middle 42 -> slot 42
71236 x 71236 = 5074567696 middle 56 -> slot 56
71237 x 71237 = 5074710169 middle 71 -> slot 71
slots: [28, 42, 56, 71] all different: TrueMethod 3: the folding method
Break the key into pieces of equal length, add the pieces, and take the remainder. Used when keys are long, such as a 10 digit phone number or a 16 digit card number, because the whole key contributes.
h(k) = (sum of the pieces of k) mod m
Two variants, and MU's papers use both words:
Shift folding, the pieces are simply added.
Boundary folding, alternate pieces are reversed before adding, so that the digit positions do not line up.
def shift_fold(k, m, piece=3):
digits = str(k)
pieces = [digits[i:i + piece] for i in range(0, len(digits), piece)]
total = sum(int(p) for p in pieces)
return total % m, pieces, total
def boundary_fold(k, m, piece=3):
digits = str(k)
pieces = [digits[i:i + piece] for i in range(0, len(digits), piece)]
turned = [p if i % 2 == 0 else p[::-1] for i, p in enumerate(pieces)]
total = sum(int(p) for p in turned)
return total % m, turned, total
M = 97
print("folding a 10 digit mobile number into a %d slot table, pieces of 3" % M)
print()
for k in (9820012345, 7700112233):
slot, pieces, total = shift_fold(k, M)
print("%d shift : %s -> sum %d -> slot %d" % (k, " + ".join(pieces), total, slot))
slot, turned, total = boundary_fold(k, M)
print("%d boundary: %s -> sum %d -> slot %d" % (k, " + ".join(turned), total, slot))
print()
print("the two keys that collided in chapter 99 under the division method:")
a, b = 9820012345, 7700112233
print(" division, m = 11 : %d -> %d, %d -> %d (collision)"
% (a, a % 11, b, b % 11))
print(" shift folding : %d -> %d, %d -> %d"
% (a, shift_fold(a, M)[0], b, shift_fold(b, M)[0]))
print(" they no longer collide:", shift_fold(a, M)[0] != shift_fold(b, M)[0])
print()
print("shift folding is blind to the ORDER of the pieces:")
REARRANGED = (120456789, 456120789, 789456120)
for k in REARRANGED:
slot, pieces, total = shift_fold(k, M)
print(" %d -> %s -> sum %d -> slot %d"
% (k, " + ".join(pieces), total, slot))
shift_slots = [shift_fold(k, M)[0] for k in REARRANGED]
print(" three rearrangements of the same pieces, slots %s: all equal %s"
% (shift_slots, len(set(shift_slots)) == 1))
print()
print("boundary folding reverses alternate pieces, which helps but does")
print("NOT cure it:")
for k in REARRANGED:
slot, turned, total = boundary_fold(k, M)
print(" %d -> %s -> sum %d -> slot %d"
% (k, " + ".join(turned), total, slot))
bound_slots = [boundary_fold(k, M)[0] for k in REARRANGED]
print(" slots %s: %d distinct, against %d for shift folding."
% (bound_slots, len(set(bound_slots)), len(set(shift_slots))))
print()
print("and here is a triple boundary folding still cannot separate:")
STILL = (123456789, 456123789, 789456123)
for k in STILL:
slot, turned, total = boundary_fold(k, M)
print(" %d -> %s -> sum %d -> slot %d"
% (k, " + ".join(turned), total, slot))
still_slots = [boundary_fold(k, M)[0] for k in STILL]
print(" slots %s: all equal %s" % (still_slots, len(set(still_slots)) == 1))
print(" reversing abc to cba changes the value by 99 x (c - a), and for")
print(" both 456 and 123 that is 99 x 2 = 198, so the two sums stay equal.")Hash Functions
folding a 10 digit mobile number into a 97 slot table, pieces of 3
9820012345 shift : 982 + 001 + 234 + 5 -> sum 1222 -> slot 58
9820012345 boundary: 982 + 100 + 234 + 5 -> sum 1321 -> slot 60
7700112233 shift : 770 + 011 + 223 + 3 -> sum 1007 -> slot 37
7700112233 boundary: 770 + 110 + 223 + 3 -> sum 1106 -> slot 39
the two keys that collided in chapter 99 under the division method:
division, m = 11 : 9820012345 -> 0, 7700112233 -> 0 (collision)
shift folding : 9820012345 -> 58, 7700112233 -> 37
they no longer collide: True
shift folding is blind to the ORDER of the pieces:
120456789 -> 120 + 456 + 789 -> sum 1365 -> slot 7
456120789 -> 456 + 120 + 789 -> sum 1365 -> slot 7
789456120 -> 789 + 456 + 120 -> sum 1365 -> slot 7
three rearrangements of the same pieces, slots [7, 7, 7]: all equal True
boundary folding reverses alternate pieces, which helps but does
NOT cure it:
120456789 -> 120 + 654 + 789 -> sum 1563 -> slot 11
456120789 -> 456 + 021 + 789 -> sum 1266 -> slot 5
789456120 -> 789 + 654 + 120 -> sum 1563 -> slot 11
slots [11, 5, 11]: 2 distinct, against 1 for shift folding.
and here is a triple boundary folding still cannot separate:
123456789 -> 123 + 654 + 789 -> sum 1566 -> slot 14
456123789 -> 456 + 321 + 789 -> sum 1566 -> slot 14
789456123 -> 789 + 654 + 123 -> sum 1566 -> slot 14
slots [14, 14, 14]: all equal True
reversing abc to cba changes the value by 99 x (c - a), and for
both 456 and 123 that is 99 x 2 = 198, so the two sums stay equal.Hash Functions
Shift folding treats the pieces as a bag and is blind to their order, which the output shows: three rearrangements, one slot. Boundary folding exists to attack exactly that, and the output also shows it only partly succeeding. It separated one of the three rearrangements of 120, 456 and 789, and it failed completely on 123, 456 and 789, because reversing abc to cba changes a three digit piece by 99 times (c - a), and that difference is 198 for both 456 and 123, so the sums stayed equal.
The honest statement is therefore the one to write in an answer: boundary folding reduces shift folding's order blindness, it does not remove it. Neither variant suits keys that are rearrangements of one another, such as part numbers assembled from a fixed set of codes.
Method 4: the multiplication method
h(k) = floor( m x fractional_part( k x A ) ), 0 < A < 1
Multiply the key by a constant A between 0 and 1, discard the whole number part, and scale what is left up to the table size. Unlike the division method this works well for any m, including a power of 2, which is why library implementations prefer it.
The recommended constant is A = (sqrt(5) - 1) / 2, about 0.6180339887, the reciprocal of the golden ratio. Knuth showed it spreads sequential keys unusually evenly, and the output below is that claim tested.
import math
A = (math.sqrt(5) - 1) / 2
def multiplication(k, m, a=A):
fractional = (k * a) % 1
return int(m * fractional)
print("A = (sqrt(5) - 1) / 2 = %.10f" % A)
print()
M = 16 # a power of 2: fatal for division, fine here
print("the multiplication method into a %d slot table" % M)
print("%8s %16s %14s %8s" % ("key", "k x A", "fractional", "slot"))
for k in (1, 2, 3, 4, 5, 100, 1000):
print("%8d %16.6f %14.6f %8d"
% (k, k * A, (k * A) % 1, multiplication(k, M)))
print()
print("the same 16 slot table, 16 CONSECUTIVE keys, both methods:")
print("%6s %12s %18s" % ("key", "division", "multiplication"))
div_slots, mul_slots = [], []
for k in range(1000, 1016):
d, u = k % M, multiplication(k, M)
div_slots.append(d)
mul_slots.append(u)
print("%6d %12d %18d" % (k, d, u))
print()
print("division used %d of %d slots, multiplication used %d"
% (len(set(div_slots)), M, len(set(mul_slots))))
print("both spread consecutive keys here. now try keys 16 apart,")
print("which is the division method's blind spot on a 16 slot table:")
step_keys = [1000 + 16 * i for i in range(16)]
d2 = [k % M for k in step_keys]
u2 = [multiplication(k, M) for k in step_keys]
print(" keys :", step_keys[:5], "...")
print(" division slots:", d2)
print(" multiplication:", sorted(u2))
print(" division used %d slot(s); multiplication used %d"
% (len(set(d2)), len(set(u2))))Hash Functions
A = (sqrt(5) - 1) / 2 = 0.6180339887
the multiplication method into a 16 slot table
key k x A fractional slot
1 0.618034 0.618034 9
2 1.236068 0.236068 3
3 1.854102 0.854102 13
4 2.472136 0.472136 7
5 3.090170 0.090170 1
100 61.803399 0.803399 12
1000 618.033989 0.033989 0
the same 16 slot table, 16 CONSECUTIVE keys, both methods:
key division multiplication
1000 8 0
1001 9 10
1002 10 4
1003 11 14
1004 12 8
1005 13 1
1006 14 11
1007 15 5
1008 0 15
1009 1 9
1010 2 3
1011 3 13
1012 4 7
1013 5 1
1014 6 10
1015 7 4
division used 16 of 16 slots, multiplication used 13
both spread consecutive keys here. now try keys 16 apart,
which is the division method's blind spot on a 16 slot table:
keys : [1000, 1016, 1032, 1048, 1064] ...
division slots: [8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8]
multiplication: [0, 0, 2, 4, 5, 5, 7, 7, 9, 9, 11, 11, 12, 12, 14, 14]
division used 1 slot(s); multiplication used 9That last block is the method's whole argument. Every key that is a multiple of 16 apart lands in the same slot under division with m = 16. The multiplication method, on the identical table, spreads them.
Hashing a string
None of the four methods accepts a string, so a string must first become a number. The standard way is to treat the characters as the digits of a number in some base, and compute it by Horner's rule so that no huge intermediate value is ever formed.
Hash Functions
h = 0
for each character c of the string:
h = (h x B + code_of(c)) mod m
B is a small constant, traditionally 31 or 33.
def string_hash(text, m, base=31):
h = 0
for ch in text:
h = (h * base + ord(ch)) % m
return h
def sum_hash(text, m):
"""The naive version: just add the character codes."""
return sum(ord(ch) for ch in text) % m
M = 101
NAMES = ["Aarti", "Bhavesh", "Chetna", "Devdatta", "Esha", "Farhan",
"Gauri", "Harsh", "Isha", "Jatin"]
print("hashing names into a %d slot table" % M)
print("%-12s %14s %14s" % ("name", "Horner (31)", "sum of codes"))
for name in NAMES:
print("%-12s %14d %14d" % (name, string_hash(name, M), sum_hash(name, M)))
print()
print("the sum method cannot tell an anagram from its rearrangement:")
for a, b in (("stop", "pots"), ("listen", "silent"), ("abc", "cba")):
print(" %-8s and %-8s : sum %3d and %3d Horner %3d and %3d"
% (a, b, sum_hash(a, M), sum_hash(b, M),
string_hash(a, M), string_hash(b, M)))
sum_clash = sum(1 for a, b in (("stop", "pots"), ("listen", "silent"), ("abc", "cba"))
if sum_hash(a, M) == sum_hash(b, M))
horner_clash = sum(1 for a, b in (("stop", "pots"), ("listen", "silent"), ("abc", "cba"))
if string_hash(a, M) == string_hash(b, M))
print()
print("of 3 anagram pairs, the sum method collided on %d; Horner on %d."
% (sum_clash, horner_clash))
print("position matters in a string, so the hash must be position-aware.")hashing names into a 101 slot table
name Horner (31) sum of codes
Aarti 70 93
Bhavesh 85 99
Chetna 79 90
Devdatta 61 5
Esha 36 82
Farhan 65 87
Gauri 26 100
Harsh 79 98
Isha 20 86
Jatin 35 98
the sum method cannot tell an anagram from its rearrangement:
stop and pots : sum 50 and 50 Horner 35 and 46
listen and silent : sum 49 and 49 Horner 94 and 90
abc and cba : sum 92 and 92 Horner 0 and 1
of 3 anagram pairs, the sum method collided on 3; Horner on 0.
position matters in a string, so the hash must be position-aware.The four methods side by side
| Method | Formula | Strength | Weakness |
|---|---|---|---|
| Division | k mod m | fastest, one operation | m must be chosen with care; a bad m ignores most of the key |
| Mid-square | middle digits of k x k | every digit of the key affects the result | the square can be large; needs a digit count chosen |
| Folding | sum of the pieces, mod m | handles very long keys; whole key used | shift folding is blind to the order of the pieces |
| Multiplication | floor(m x frac(k x A)) | works for any m, spreads sequential keys | floating point, and slower than one modulo |
Hash Functions
Quick revision
- A hash function must be deterministic and must land inside 0 to m-1, which is why every method ends in mod m.
- Division: h(k) = k mod m. Fastest. Never use a power of 10 or a power of 2 for m; use a prime.
- With 40 multiples of 10 and m = 10 every key landed in slot 0; with m = 41 they used 40 slots.
- Mid-square: square the key and take middle digits, because the middle of a square depends on every digit of the key.
- Folding: split the key into pieces and add them, then mod m. Shift folding adds the pieces as they are, so it cannot tell one arrangement of the pieces from another.
- Boundary folding reverses alternate pieces to attack that and only partly succeeds: it separated one of three rearrangements of 120, 456, 789 and none of 123, 456, 789, because reversing a three digit piece changes it by 99 times (last digit minus first), which is 198 for both 456 and 123.
- Multiplication: h(k) = floor(m x frac(k x A)) with A about 0.6180339887. Works for any m, including a power of 2, where division fails on keys m apart.
- Strings become numbers by Horner's rule, h = (h x 31 + code) mod m, which is position-aware; simply adding the character codes gives every anagram the same slot.
Test yourself
1. State the two absolute requirements on a hash function. It must be deterministic, so the same key always gives the same slot, and its result must lie within 0 to m-1.
2. Give the division method and hash 1001 into an 11 slot table, showing the arithmetic. h(k) = k mod m. 1001 = 11 x 91 + 0, so h(1001) = 0.
3. Why must the table size not be a power of 10 or of 2 in the division method? Because k mod 1000 is the last three digits and k mod 16 is the last four bits, so most of the key is ignored. The chapter put 40 multiples of 10 into a 10 slot table and all 40 landed in slot 0.
4. Explain the reasoning behind the mid-square method. The middle digits of k x k depend on every digit of k, since every digit contributes to the middle of the product, while the leading and trailing digits are dominated by the key's own leading and trailing digits.
5. Distinguish shift folding from boundary folding, and say how far the second fixes the first's weakness. Shift folding adds the pieces as they are, so it depends only on the multiset of pieces and 120456789, 456120789 and 789456120 all hash to one slot. Boundary folding reverses alternate pieces first, which separated one of those three but none of 123456789, 456123789 and 789456123: reversing a three digit piece changes it by 99 times (last digit minus first), and that is 198 for both 456 and 123, so those sums remain equal. Boundary folding reduces the order blindness; it does not remove it.
Hash Functions
6. Give the multiplication method and the recommended constant, and say what it is good at. h(k) = floor(m x fractional part of (k x A)) with A = (sqrt(5) - 1) / 2, about 0.6180339887. It works for any table size, including a power of 2, and it spreads consecutive keys well.
7. How is a string hashed, and what is wrong with adding the character codes? By Horner's rule: h = (h x B + code of the character) mod m, with B typically 31. Simply adding the codes ignores position, so every anagram hashes to the same slot: "listen" and "silent" collide.
The rest of this subject
These notes are cut from the University's printed syllabus. Open the syllabus itself, or the past papers, for the same subject.