✦ScienexySCIENCE KNOWLEDGE LIBRARY
General science · SCI-FORM-COM-2072

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

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.

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

SymbolMeaningUnit

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

ProblemSolutionAnswer

A separate-chaining hash table stores 300 keys in 100 buckets. Calculate its expected chain length.

  • Given: n = 300.

  • m = 100.

  • Calculate α = n/m.

  • α = 300/100 = 3.

  • Expected chain length E[L] = α = 3.

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.

  • Given: n = 800 and m = 200.

  • α = n/m = 800/200 = 4.

  • Expected unsuccessful-search chain comparisons ≈ α = 4.

  • Approximate successful-search comparisons ≈ 1 + α/2.

  • ≈ 1 + 4/2 = 3.

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.

← Back to Formula Hub · Suggest a correction or source