 Load factor of a hash table

The number $n$ of stored records divided by the number $m>0$ of hash buckets. For separate chaining, this is the mean chain length over all hash buckets, including empty ones.

Consider two original separate chaining placements using the deterministic hash function $h_m(k)=k\mathrm{mod}m$ on nonnegative integer keys. With $m=8$, keys $0,1,\dots ,11$ give the balanced chain lengths $(2,2,2,2,1,1,1,1)$. Instead, keys $0,16,32,\dots ,176$ all select hash bucket $0$, giving $(12,0,0,0,0,0,0,0)$. Both store $n=12$ records, so both have $\alpha =12/8=1.5$. The maximum chain lengths are $2$ and $12$. These are constructed placements, not measured workloads.

For an absent query, separate chaining inspects every record in the selected hash bucket. Key $24$ selects hash bucket $0$ in both examples but is stored in neither, so it takes two key equality comparisons in the balanced placement and twelve in the concentrated placement. Key $15$ selects hash bucket $7$ and instead takes one comparison in the balanced placement and zero in the concentrated placement. If an absent query's bucket index has the uniform distribution on a finite set of eight indices, its mean comparison count is $1.5$ in either fixed placement. That average does not limit the cost of a particular query.

For successful lookups, suppose each of the twelve stored keys is queried with equal probability, with fixed chain order and no rearrangement on access. A chain of length $\ell$ contributes comparison counts $1,\dots ,\ell$, irrespective of its order. ThusThe balanced placement gives $(4\cdot 3+4\cdot 1)/12=4/3$ comparisons; the concentrated placement gives $(1+\cdots +12)/12=13/2$. Even this average depends on more than $\alpha$: concentration appears through the squared chain lengths. These exact counts exclude computing the hash function, locating the hash bucket, and allocating records. Elapsed lookup time also depends on the cost of key equality, key length, and memory access latency; $\alpha$ alone specifies none of them.

The expected $O(1+\alpha )$ time complexity bound for separate chaining needs a probabilistic assumption. Fix distinct stored keys and a query independently of the random choice of hash function, and require ${\mathrm{Pr}}_h[h_m(x)=h_m(y)]\le c/m$ for every unequal pair, where $c$ is a constant independent of $n,m$. With constant-cost hashing, array access and key equality, this suffices. The authored chaining analysis cited here uses this pairwise-collision argument; its multiplicative construction has $c=2$, rather than the $c=1$ of simple uniform hashing.^[ref]

For the proof outline, let $I_i$ be the indicator random variable that stored key $k_i$ shares an absent query $q$'s hash bucket. By linearity of expectation,A present query's full chain contains itself plus at most $n-1$ other records, giving $\mathbb{E}[C_{\mathrm{hit}}]\le 1+c(n-1)/m$. Stopping at the match can only improve this bound. Full independence is unnecessary for this calculation, but fixed known hash functions and keys chosen adaptively to collide are outside the stated assumption. Keeping $\alpha$ bounded then controls expected lookup work, while the concentrated example still explains why it gives no worst-case guarantee.

For the balanced twelve-record map, put(3,new_value) replaces a value, so $n=12$ and $\alpha =1.5$ remain unchanged. An absent key such as $19$ instead adds a thirteenth record, giving $\alpha =13/8$ if capacity stays fixed. Under a policy that stores every repeated-key record separately, another record with key $3$ would also increase $n$; all equal-key records necessarily share a hash bucket when the hash function respects key equality. State the map policy before interpreting the count.

The appeal of the hash table load factor is that one number helps tune a space-versus-search tradeoff: more hash buckets require more array storage and can reduce expected search work under the stated assumptions. The actual chain lengths and query choices still matter.

In open addressing, $m$ counts record slots and $n$ counts live records, so $\alpha =n/m\le 1$. A policy retaining at least one genuinely empty slot requires $\alpha <1$; being below one is not itself a speed guarantee. For deletion using a tombstone in open addressing, also track $t$, the number of marked slots: $(n+t)/m$ counts slots that cannot terminate an unsuccessful probe. For example, $m=8,n=3,t=4$ gives live occupancy $3/8$ but nonempty-or-marked occupancy $7/8$. These ratios answer different questions.^[ref]