Under uniform hashing with separate chaining, the expected number of entries in a particular bucket is equal to the hash table load factor. The expected chain length therefore depends on the number of stored entries divided by the number of buckets.
Expected Hash Chain Length
Under uniform hashing with separate chaining, the expected number of entries in a particular bucket is equal to the hash table load factor. The expected chain length therefore depends on the number of stored entries divided by the number of buckets.
\(E[L] = \alpha = n/m\)
What this formula means
Scientific principle
Principle
Uniform hashing distributes keys independently and uniformly among the available buckets. Each key has probability 1/m of being assigned to a particular bucket. The expected number of keys assigned to that bucket is therefore n/m.
Derivation
1. Consider a hash table with n stored keys and m buckets.
2. Define an indicator variable Xᵢ that equals 1 if key i maps to a selected bucket and 0 otherwise.
3. Under uniform hashing, E[Xᵢ] = 1/m.
4. The chain length is L = X₁ + X₂ + ⋯ + Xₙ.
5. By linearity of expectation, E[L] = ΣE[Xᵢ].
6. Therefore, E[L] = n/m.
7. Since α = n/m, the expected chain length is E[L] = α.
Final Result
E[L] = α = n/m
Expected Unsuccessful Search Comparisons
E[C_unsuccessful] = α
Expected Successful Search Comparisons
E[C_successful] ≈ 1 + α/2 under uniform insertion and search assumptions
Variables and their meanings
| Symbol | Meaning | Unit |
|---|---|---|
E[L] | Expected number of entries in a selected bucket | Entries |
L | Actual chain length | Entries |
α | Hash table load factor | Dimensionless |
n | Number of stored keys | Keys |
m | Number of buckets | Buckets |
SI units and conversions
Expected Chain Length
Entries per bucket
Load Factor
Dimensionless
Input Size
Keys
Bucket Count
Buckets
Conditions of use
The collision-resolution strategy is separate chaining.
Keys are distributed uniformly and independently among buckets.
The selected bucket is treated as an ordinary bucket with no special selection bias.
The unsuccessful-search comparison estimate assumes a search examines the selected chain.
The successful-search estimate assumes a uniformly positioned target within its chain under a conventional insertion model.
Limitations and assumptions
The expected chain length does not guarantee that every bucket has approximately α entries.
Poor hash functions can produce significantly longer chains.
The successful-search comparison estimate depends on the insertion and search model.
The relation does not describe open-addressing probe sequences.
An average chain length can hide substantial variation among individual buckets.
Step-by-step worked examples
| Problem | Solution | Answer |
|---|---|---|
A separate-chaining hash table stores 300 keys in 100 buckets. Calculate its expected chain length. |
| The expected chain length is 3 entries per bucket. |
A hash table contains 800 keys distributed uniformly across 200 buckets. Estimate the expected unsuccessful-search chain comparisons and the approximate successful-search comparisons. |
| The expected chain length is 4. An unsuccessful search examines approximately 4 chain entries, while the stated successful-search model gives approximately 3 comparisons. |
Real-world applications
Hash map lookup analysis
Dictionary data structures
Database hash indexing
Collision-resolution performance estimation
Hash table capacity planning
Formula Meaning
Under uniform hashing with separate chaining, the expected number of entries in a particular bucket is equal to the hash table load factor. The expected chain length therefore depends on the number of stored entries divided by the number of buckets.
Sources and further reading
No source has been supplied for this item yet. Treat the claim as needing editorial verification.