Under the uniform hashing model for open addressing, expected probe counts increase as the load factor approaches one. The expected unsuccessful-search probe bound is 1/(1 − α), while the corresponding successful-search bound is (1/α) ln[1/(1 − α)].
Open Addressing Probe Load Relation
Under the uniform hashing model for open addressing, expected probe counts increase as the load factor approaches one. The expected unsuccessful-search probe bound is 1/(1 − α), while the corresponding successful-search bound is (1/α) ln[1/(1 − α)].
\(E[P_{\mathrm{unsuccessful}}] \leq 1/(1 - \alpha); E[P_{\mathrm{successful}}] \leq (1/\alpha) \ln[1/(1 - \alpha)]\)
What this formula means
Scientific principle
Principle
Open addressing stores all entries directly inside the hash table. When a probe encounters an occupied position, it follows a probe sequence to find another position. As occupancy increases, the probability of encountering an empty position decreases, increasing the expected number of probes.
Derivation
1. Let α = n/m be the occupied fraction of the table.
2. The fraction of unoccupied positions is 1 − α.
3. Under the uniform hashing assumption, the expected unsuccessful-search probe count is bounded by 1/(1 − α).
4. For a successful search, the standard uniform-hashing analysis gives an upper bound of (1/α) ln[1/(1 − α)].
5. As α approaches one, 1 − α approaches zero.
6. Consequently, both expected probe bounds increase sharply as the table becomes full.
Final Result
E[P_unsuccessful] ≤ 1/(1 − α)
Successful Search Bound
E[P_successful] ≤ (1/α) ln[1/(1 − α)]
Load Factor
α = n/m
Asymptotic Behavior
Probe costs increase rapidly as α → 1
Variables and their meanings
| Symbol | Meaning | Unit |
|---|---|---|
E[P_unsuccessful] | Expected number of probes for an unsuccessful search | Probe operations |
E[P_successful] | Expected number of probes for a successful search | Probe operations |
α | Open-addressing load factor | Dimensionless |
n | Number of occupied table positions | Entries |
m | Total number of table positions | Slots |
SI units and conversions
Probe Count
Dimensionless operation count
Load Factor
Dimensionless
Input Size
Entries
Table Capacity
Slots
Conditions of use
The collision-resolution method is open addressing.
The load factor satisfies 0 ≤ α < 1.
The bounds use the uniform hashing model, in which probe sequences behave like random permutations of table positions.
The successful-search expression assumes the standard uniform-hashing analysis.
The formulas are expected probe bounds rather than exact counts for every hash table.
Limitations and assumptions
The bounds do not directly describe linear probing, which can suffer from primary clustering.
Quadratic probing and double hashing have different probe-distribution properties.
The formulas become unbounded as α approaches one, emphasizing the need to preserve empty slots.
The expressions are not exact predictions for a specific key distribution.
Actual performance also depends on cache behavior and the hash function.
Step-by-step worked examples
| Problem | Solution | Answer |
|---|---|---|
Estimate the expected unsuccessful-search probe bound for a uniformly hashed open-addressing table with load factor 0.5. |
| The expected unsuccessful-search probe bound is 2 probes. |
Calculate the successful-search probe bound for a uniformly hashed open-addressing table with load factor 0.5. |
| The successful-search probe bound is approximately 1.386 probes under the stated model. |
Real-world applications
Open-addressing hash table analysis
Double-hashing performance estimation
Hash table resizing decisions
Expected lookup-cost analysis
Memory-efficient dictionary implementations
Formula Meaning
Under the uniform hashing model for open addressing, expected probe counts increase as the load factor approaches one. The expected unsuccessful-search probe bound is 1/(1 − α), while the corresponding successful-search bound is (1/α) ln[1/(1 − α)].
Sources and further reading
No source has been supplied for this item yet. Treat the claim as needing editorial verification.