Hash Table Load Factor Calculator (Expected Probes: Linear Probing, Double Hashing, Chaining)
The load factor of a hash table and the average number of probes a lookup needs — for linear probing, double hashing and chaining — plus the table size that keeps you under a chosen load.
Results
The dashed line marks the value you entered.
What this tool does
A hash table is fast only while it is not too full. With linear probing a lookup for a missing key takes 2.5 probes on average at a load factor of 0.5, but 50.5 at 0.9; double hashing is kinder (10 at 0.9) and chaining degrades smoothly, since a load above 1 just means longer chains. Open-addressing tables therefore resize long before they fill — commonly somewhere between 50 % and 75 % load. These are Knuth's averages for a good hash function.
Formula
α = n ÷ m · linear probing: hit ½(1 + 1/(1−α)), miss ½(1 + 1/(1−α)²) · double hashing: hit (1/α) ln(1/(1−α)), miss 1/(1−α) · chaining: hit 1 + α/2, miss α
Variables
| Symbol | Meaning | Unit |
|---|---|---|
n | Items stored | — |
m | Table size (slots or buckets) | — |
ml | Largest load factor you want to allow | — |
LU | Linear probing: probes when the item is absent | — |
LF | Load factor α (items ÷ slots) | — |
LS | Linear probing: probes to find an item | — |
DS | Double hashing: probes to find an item | — |
DU | Double hashing: probes when the item is absent | — |
CS | Chaining: comparisons to find an item | — |
CU | Chaining: comparisons when the item is absent | — |
SZ | Table size that keeps the load at your limit | — |
Worked example
- Items stored700
- Table size (slots or buckets)1000
- Largest load factor you want to allow0.7
- Linear probing: probes when the item is absent6.06
- Load factor α (items ÷ slots)0.700
- Linear probing: probes to find an item2.17
- Double hashing: probes to find an item1.72
- Double hashing: probes when the item is absent3.33
- Chaining: comparisons to find an item1.35
- Chaining: comparisons when the item is absent0.70
- Table size that keeps the load at your limit1000
Limitations
- The formula assumes ideal conditions: no friction losses, no air resistance and no efficiency losses unless you enter them.
- The result is an estimate based only on the values you type. Real situations often include factors this calculator does not know about.