Алгоритми та структури даних · Senior · Запитання 54 з 75
Яка очікувана кількість порівнянь для успішного пошуку в хеш-таблиці з ланцюжками й коефіцієнтом заповнення α?
- 1Рівно α²
- 2Приблизно log α
- ✓Правильна відповідь: Приблизно 1 + α/2
Пояснення
За рівномірного хешування ланцюжок має в середньому α елементів, а успішний пошук переглядає приблизно половину. Тому таблиці тримають α нижче константи на кшталт 0.75: пошук займає кілька порівнянь.