Algorithms and Data Structures · Senior · Question 54 of 75
What is the expected number of comparisons for a successful lookup in a hash table with chaining and load factor α?
- 1Exactly α²
- 2About log α
- ✓Correct answer: About 1 + α/2
Explanation
With uniform hashing a chain has α elements on average, and a successful search scans about half of it. That's why tables keep α below a constant such as 0.75: lookups stay a few comparisons long.