Load factor and expected probes

Why it exists

"Hashing takes expected constant time" needs a precise statement: constant provided the table is not too full. The load factor $\alpha = n/m$ is the one number that decides the cost, and GATE asks for it directly: the expected number of probes of a search in chaining, linear probing and double hashing as a function of $\alpha$. This page derives the formulas, checks them against measurements, and shows how quickly open addressing degrades as $\alpha \to 1$.

Prerequisites

You need the collision-resolution schemes (chaining and open addressing) and the idea of an expected value (sum of value times probability, and linearity of expectation).

Precise definitions

Load factor. $\alpha = n/m$, with $n$ keys in $m$ slots. For open addressing $0 \le \alpha < 1$; for chaining $\alpha$ may exceed $1$.

Model. Simple uniform hashing for chaining: every key is equally likely to hash into any slot, independently. Uniform hashing for open addressing: the probe sequence of every key is equally likely to be any of the $m!$ permutations of the slots. (Double hashing approximates it well; linear probing does not, which is why it has its own formulas.)

Cost measure. The number of probes of a search: for chaining the number of list nodes examined, for open addressing the number of table slots examined (including the final empty slot in an unsuccessful search and the slot with the key in a successful one).

How it works

Chaining

Under simple uniform hashing the list of the slot reached by a key not in the table has $n/m = \alpha$ nodes on average, and an unsuccessful search examines all of them: $\alpha$ nodes (plus the constant work of computing $h$). A successful search ends at the sought key. Suppose the keys were inserted at the front of their lists. The $i$-th inserted key is preceded in its list by exactly the keys inserted after it that hash to the same slot; each of the $n - i$ later keys does so with probability $1/m$, so the expected number of nodes examined to find it is $1 + (n - i)/m$. Averaging over $i = 1, \ldots, n$: $1 + \frac{1}{n} \sum_{i=1}^{n} \frac{n - i}{m} = 1 + \frac{n - 1}{2m} = 1 + \frac{\alpha}{2} - \frac{\alpha}{2n}.$ So a successful search costs about $1 + \alpha/2$, an unsuccessful one $\alpha$ (or $1 + \alpha$ counting the access of the slot). Both are $\Theta(1 + \alpha)$: constant if $n = O(m)$, which is why $m$ is chosen proportional to $n$. These two formulas were confirmed by enumerating every assignment of keys to slots for small $m$ and $n$. The worst case is $\Theta(n)$ (all keys in one list).

Open addressing with uniform hashing

Consider an unsuccessful search in a table with $n$ keys in $m$ slots. It makes more than $i$ probes exactly when the first $i$ slots of its (random) probe sequence are all occupied, which has probability $\frac{n}{m} \cdot \frac{n-1}{m-1} \cdots \frac{n-i+1}{m-i+1} \;\le\; \alpha^{\,i}.$ The expected number of probes is the sum of the probabilities of "more than $i$ probes" for $i = 0, 1, 2, \ldots$, so $E[\text{unsuccessful}] \;\le\; \sum_{i \ge 0} \alpha^{i} = \frac{1}{1 - \alpha}.$ (Exactly it equals $(m + 1)/(m - n + 1)$.) An insertion costs the same as an unsuccessful search, since it probes until the first empty slot. A successful search for a key repeats the probes made when the key was inserted. The key that was the $(j+1)$-th to be inserted found $j$ keys already present and needed at most $1/(1 - j/m)$ probes on average, so $E[\text{successful}] \;\le\; \frac{1}{n} \sum_{j=0}^{n-1} \frac{m}{m - j} \;\approx\; \frac{1}{\alpha} \int_0^{\alpha} \frac{dx}{1 - x} = \frac{1}{\alpha} \ln \frac{1}{1 - \alpha}.$ Values: at $\alpha = 0.5$ an unsuccessful search needs $2$ probes and a successful one $1.39$; at $0.9$ they need $10$ and $2.56$; at $0.99$ they need $100$ and $4.65$. The cost explodes as the table fills, but only for unsuccessful searches and insertions.

Linear probing

Linear probing does not follow the uniform hashing model: its runs of occupied slots keep growing (primary clustering), so it is worse. The classical result of Knuth for large tables is $E[\text{successful}] \approx \tfrac12\left(1 + \frac{1}{1 - \alpha}\right), \qquad E[\text{unsuccessful}] \approx \tfrac12\left(1 + \frac{1}{(1 - \alpha)^2}\right).$ At $\alpha = 0.5$: $1.5$ and $2.5$ probes. At $\alpha = 0.8$: $3$ and $13$. At $\alpha = 0.9$: $5.5$ and $50.5$. Compare with $10$ for uniform hashing at $0.9$: the square in the denominator is the price of clustering.

Measured

The C program fills tables of $10007$ slots with random keys up to a given load factor and averages the probes of every successful search and of $20000$ unsuccessful searches, over $5$ tables for each setting, for chaining, linear probing and double hashing (with $h_2(k) = 1 + k \bmod (m - 1)$).

#include <stdio.h>
#include <stdlib.h>
 
#define M 10007                    /* a prime number of slots */
#define TRIALS 5
#define MISSES 20000
 
static unsigned long long state = 88172645463325252ULL;
static unsigned long long next_key(void) {              /* xorshift64: 48-bit keys */
    state ^= state << 13; state ^= state >> 7; state ^= state << 17;
    return state >> 16;
}
 
static long table[M];                                   /* open addressing: 0 means empty */
static int head[M], nxt[M];                             /* chaining: nodes are numbered 1 ..., stored keys in node_key */
static long node_key[M + 1];
 
/* the three tables, with the number of array slots or list nodes examined by a search */
static int probes_open(long key, int double_hashing) {
    int h1 = (int)(key % M), h2 = double_hashing ? 1 + (int)(key % (M - 1)) : 1;
    int p = 0;
    for (int i = 0; i < M; i++) {
        int idx = (int)(((long)h1 + (long)i * h2) % M);
        p++;
        if (table[idx] == 0 || table[idx] == key) return p;
    }
    return p;
}
 
static void insert_open(long key, int double_hashing) {
    int h1 = (int)(key % M), h2 = double_hashing ? 1 + (int)(key % (M - 1)) : 1;
    for (int i = 0; i < M; i++) {
        int idx = (int)(((long)h1 + (long)i * h2) % M);
        if (table[idx] == 0) { table[idx] = key; return; }
    }
}
 
static int probes_chain(long key) {
    int p = 0;
    for (int node = head[key % M]; node; node = nxt[node]) {
        p++;
        if (node_key[node] == key) return p;
    }
    return p;
}
 
int main(void) {
    double loads[3] = {0.5, 0.8, 0.9};
    printf("%-9s %5s %12s %14s\n", "scheme", "alpha", "successful", "unsuccessful");
    for (int scheme = 0; scheme < 3; scheme++) {                /* 0 chaining, 1 linear probing, 2 double hashing */
        for (int a = 0; a < 3; a++) {
            int n = (int)(loads[a] * M);
            double succ = 0, miss = 0;
            for (int trial = 0; trial < TRIALS; trial++) {
                long *keys = malloc(sizeof(long) * n);
                for (int i = 0; i < M; i++) { table[i] = 0; head[i] = 0; }
                for (int i = 0; i < n; i++) {
                    keys[i] = (long)next_key() + 1;
                    if (scheme == 0) { node_key[i + 1] = keys[i]; nxt[i + 1] = head[keys[i] % M]; head[keys[i] % M] = i + 1; }
                    else insert_open(keys[i], scheme == 2);
                }
                long total = 0;
                for (int i = 0; i < n; i++) total += scheme == 0 ? probes_chain(keys[i]) : probes_open(keys[i], scheme == 2);
                succ += (double)total / n;
                total = 0;
                for (int q = 0; q < MISSES; q++) {
                    long key = (long)next_key() + 1;
                    total += scheme == 0 ? probes_chain(key) : probes_open(key, scheme == 2);
                }
                miss += (double)total / MISSES;
                free(keys);
            }
            printf("%-9s %5.2f %12.3f %14.3f\n", scheme == 0 ? "chaining" : scheme == 1 ? "linear" : "double", loads[a], succ / TRIALS, miss / TRIALS);
        }
    }
    return 0;
}

scheme    alpha   successful   unsuccessful
chaining   0.50        1.252          0.505
chaining   0.80        1.402          0.802
chaining   0.90        1.447          0.898
linear     0.50        1.505          2.500
linear     0.80        3.049         13.258
linear     0.90        5.640         52.883
double     0.50        1.388          1.994
double     0.80        2.002          4.985
double     0.90        2.548          9.994

Chaining stays near $\alpha$ and $1 + \alpha/2$ whatever the load. Double hashing follows $1/(1 - \alpha)$ and $(1/\alpha)\ln(1/(1 - \alpha))$: $2$ and $1.39$ at $0.5$, $10$ and $2.56$ at $0.9$. In probe counts linear probing is worse than double hashing at every load shown, and at $\alpha = 0.9$ an unsuccessful search needs about $50$ probes against $10$. Its advantage in practice is cache locality (consecutive slots), which probe counts do not capture.

Other expectations under uniform hashing

• Colliding pairs. Among $n$ keys the expected number of pairs that hash to the same slot is $\binom{n}{2}/m$ (each pair collides with probability $1/m$, then add by linearity of expectation).
• Empty slots. A given slot is empty after $n$ insertions with probability $(1 - 1/m)^n \approx e^{-\alpha}$, so the expected number of empty slots is $m(1 - 1/m)^n \approx m e^{-\alpha}$: with $n = m$ about $37\%$ of the slots remain empty, even though the table has as many keys as slots.
• Longest chain. With $n = m$ the expected length of the longest chain is $\Theta(\log n / \log \log n)$ (a result from the literature, not derived here), more than constant but far below $n$.
• Resizing. To keep $\alpha$ below a threshold, the table is doubled when it gets too full and everything is rehashed; since doubling happens after exponentially growing numbers of insertions, the amortized cost of an insertion remains constant.

Worked examples

Cheat box

Traps and GATE patterns

Connections

The collision-handling schemes analysed here are defined in chaining and open addressing and the functions in hashing. The probability tools (expectation, linearity) are those of expectation of random variables.

PYQs

Suppose we are given n keys, m hash table slots, and

Consider a hash table with 9 slots. The hash function
is h(k) = k mod 9. The collisions are resolved by
chaining. The following 9 keys are inserted in the
order: 5, 28, 19, 15, 20, 33, 12, 17, 10. The maximum,
minimum, and average chain lengths in the hash
table, respectively, are

Consider a hash table with 100 slots. Collisions are
resolved using chaining. Assuming simple uniform
DATA STRUCTURE

hashing, what is the probability that the first 3 slots
are unfilled after the first 3 insertions?

Self-check

Revision card

References