Алгоритми та структури даних · Senior · Запитання 50 з 75
Яке твердження про середній і найгірший випадок операцій хеш-таблиці правильне?
- ✓Правильна відповідь: Середнє O(1) передбачає добрий хеш; найгірший випадок усе одно O(n)
- 2І середній, і найгірший випадок у сучасних рушіях O(1)
- 3Обидва O(log n), бо комірки - це дерева
Пояснення
Очікуване O(1) спирається на рівномірний розподіл ключів. Деякі реалізації (HashMap у Java 8) перетворюють довгі ланцюжки на дерева, обмежуючи найгірший випадок O(log n), але загалом хеш-таблиця обіцяє лише швидкість у середньому.