Hashing: functions and collisions

Why it exists

Searching an unsorted array takes $\Theta(n)$ and searching a sorted array takes $\Theta(\log n)$, but an array indexed by the key itself takes $\Theta(1)$: look at position $k$. Hashing keeps that speed for keys that are not small integers (names, long numbers, strings) by turning the key into an array index with a hash function. The expected cost of search, insert and delete is then constant, which is why hash tables are the default dictionary of most programming languages. The price: two keys can get the same index (a collision), and the order of the keys is lost.

Prerequisites

You need arrays with constant-time access by index (arrays).

Precise definitions

Dictionary. A set of keys (with attached data) supporting insert, search and delete.

Universe and table. The keys come from a universe $U$ that is usually huge ($U$ = all 32-bit numbers, all strings). The table is an array $T[0..m-1]$ of $m$ slots (buckets), with $m \ll |U|$.

Direct-address table. If $U = \{0, \ldots, u-1\}$ is small, store the record of key $k$ in $T[k]$. All three operations take $\Theta(1)$ time, but the space is $\Theta(u)$, hopeless when $u = 2^{64}$ and only a few thousand keys are present.

Hash function. A function $h : U \to \{0, 1, \ldots, m-1\}$. The key $k$ is stored in (or searched at) slot $h(k)$. It must be deterministic (the same key always gives the same value) and fast.

Collision. Two different keys $k_1 \ne k_2$ with $h(k_1) = h(k_2)$. Since $|U| > m$, collisions cannot be avoided for all inputs (pigeonhole): among any $m + 1$ distinct keys at least two collide.

Load factor. $\alpha = n/m$ for $n$ keys stored in $m$ slots. It is the average number of keys per slot.

Simple uniform hashing assumption (SUHA). Each key is equally likely to hash to any of the $m$ slots, independently of the other keys. Almost all average-case results on hashing are proved under this assumption; it is what a good hash function tries to imitate.

How it works

Collisions come early

By pigeonhole a collision is certain after $m + 1$ keys. But it is likely much sooner. Hash $k$ keys independently and uniformly into $m$ slots. The probability that no two collide is $P(\text{no collision}) = \prod_{i=0}^{k-1} \left(1 - \frac{i}{m}\right) \approx e^{-k(k-1)/(2m)},$ because the $i$-th key must avoid the $i$ slots already used. The expected number of colliding pairs is $\binom{k}{2}/m$ (each of the $\binom{k}{2}$ pairs collides with probability $1/m$). For $m = 365$ slots a collision becomes more likely than not with only $23$ keys (the birthday paradox; in general about $1.18\sqrt m$ keys), when the table is only $6\%$ full.

Hash functions

A good hash function spreads the keys of the application evenly, whatever pattern they have. The standard ones for integer keys:

Division method. $h(k) = k \bmod m$. Fast and simple, but the quality depends on $m$. If $m$ shares a factor with a pattern in the keys, whole buckets stay empty and others overflow. Advice: choose $m$ a prime not close to a power of $2$ (or $10$). Never take $m = 2^p$ if the keys' low bits are not random, since $k \bmod 2^p$ only looks at the last $p$ bits.

Multiplication method. $h(k) = \lfloor m\,(kA \bmod 1) \rfloor$ for a constant $0 < A < 1$ (Knuth suggests $A \approx (\sqrt 5 - 1)/2 = 0.6180339887\ldots$): multiply the key by $A$, keep the fractional part, multiply by $m$ and take the integer part. The value of $m$ is not critical, so $m$ can be a power of two, which makes the computation a multiplication and a shift on machine words. For $k = 1234$ and $m = 100$: $kA = 762.6\ldots$, fractional part $0.65\ldots$, so $h(k) = 65$.

Other ideas. Mid-square: square the key and take the middle digits. Folding: cut the key into pieces and add them. Strings: treat the characters as digits of a number in some base $B$ and reduce by Horner's rule, $h = (\cdots((s_0 B + s_1) B + s_2) \cdots) \bmod m$, so that all characters, in order, influence the result.

Universal hashing. Any single fixed function has a bad set of keys (an adversary can choose keys that all collide). Choosing the function at random from a family at the start defeats this. For a prime $p > |U|$, the family $h_{a,b}(k) = ((ak + b) \bmod p) \bmod m$ with random $a \in \{1, \ldots, p - 1\}$ and $b \in \{0, \ldots, p - 1\}$ has the property that for any two different keys the probability (over the choice of $a, b$) that they collide is at most $1/m$ (checked exhaustively on small cases), so the expected cost is as for SUHA whatever the keys are.

What the choice of $m$ does. The program hashes the twenty keys $10, 20, \ldots, 200$ (multiples of $10$, a typical pattern) with several $m$ and counts how many buckets are used and how large the largest bucket is.

#include <stdio.h>
#include <math.h>
 
#define N 20
 
/* the keys are 10, 20, ..., 200: a pattern such as real keys often have (multiples of a round number) */
static void report(const char *name, int m, int (*h)(int, int)) {
    int load[64] = {0}, used = 0, max = 0;
    for (int i = 1; i <= N; i++) load[h(10 * i, m)]++;
    for (int b = 0; b < m; b++) {
        if (load[b] > 0) used++;
        if (load[b] > max) max = load[b];
    }
    printf("%-15s m = %2d  buckets used = %2d  largest bucket = %2d\n", name, m, used, max);
}
 
static int division(int key, int m) { return key % m; }
 
static int multiplication(int key, int m) {
    double a = 0.6180339887498949, x = key * a;      /* A = (sqrt(5) - 1) / 2 */
    return (int)(m * (x - floor(x)));
}
 
int main(void) {
    report("division", 10, division);
    report("division", 11, division);
    report("division", 16, division);
    report("division", 13, division);
    report("multiplication", 16, multiplication);
    printf("\nprobability that k keys, hashed uniformly into 365 slots, have a collision:\n");
    int ks[4] = {10, 23, 30, 50};
    for (int t = 0; t < 4; t++) {
        double none = 1.0;
        for (int i = 0; i < ks[t]; i++) none *= 1.0 - i / 365.0;
        printf("k = %2d  %.4f\n", ks[t], 1.0 - none);
    }
    return 0;
}

division        m = 10  buckets used =  1  largest bucket = 20
division        m = 11  buckets used = 11  largest bucket =  2
division        m = 16  buckets used =  8  largest bucket =  3
division        m = 13  buckets used = 13  largest bucket =  2
multiplication  m = 16  buckets used = 13  largest bucket =  2
 
probability that k keys, hashed uniformly into 365 slots, have a collision:
k = 10  0.1169
k = 23  0.5073
k = 30  0.7063
k = 50  0.9704

With $m = 10$ every key lands in bucket $0$: the table degenerates into one list. With $m = 16$ only even buckets are used (the factor $2$ of the keys is shared). Primes $11$ and $13$ spread the keys well. The multiplication method copes even with $m = 16$.

Resolving collisions

Because collisions happen, a hash table needs a rule for keys that share a slot: chaining (each slot holds a list of keys) or open addressing (a colliding key is put into another slot of the table, found by a probe sequence). They are the subject of the next page; the expected cost as a function of the load factor is in load factor and expected probes.

What a hash table cannot do well: keep keys in sorted order, find the next larger key, or report all keys in a range. A search tree does those in $O(\log n)$; a hash table needs $\Theta(n)$ time.

Worked examples

Cheat box

Traps and GATE patterns

Connections

Searching by hashing is compared with binary search (needs order) and with binary search trees (BST). The two ways to handle collisions are in chaining and open addressing and their costs in load factor and expected probes. Using the key as an array index is also the idea behind counting sort.

PYQs

An algorithm has to store several keys generated
by an adversary in a hash table. The adversary is
malicious who tries to maximize the number of
two simple uniform hash functions h1 and h2.
Further suppose our hashing scheme uses h1 for the
odd keys and h2 for the even keys. What is the
expected number of keys in a slot?

Consider a dynamic hashing approach for 4-bit
integer keys:
1. There is a main hash table of size 4.
2. The 2 least significant bits of a key is used to
index into the main hash table.
3. Initially, the main hash table entries are empty.
4. Thereafter, when more keys are hashed into it, to
resolve collisions, the set of all keys corresponding
to a main hash table. entry is organized as a binary
tree that grows on demand.
5. First, the 3rd least significant bit is used to divide
the keys into left and right subtrees.
6. To resolve more collisions, each node of the
binary tree is further sub-divided into left and right
subtrees based on the 4th least significant bit.
DATA STRUCTURE

7. A split is done only if it is needed, i.e., only
when there is a collision.

Consider the following state of the hash table.

Which of the following sequences of key
insertions can cause the above state of the hash
table (assume the keys are in decimal notation)?

Which one of the following hash functions on
integers will distribute keys most uniformly over 10
buckets numbered 0 to 9 for i ranging from 0 to 2020?

Self-check

Revision card

References