Алгоритми та структури даних · Middle · Запитання 53 з 75
Що стається з хеш-таблицею, коли коефіцієнт заповнення стає завеликим?
- ✓Правильна відповідь: Вона збільшує масив і заново вставляє (перехешовує) всі записи
- 2Вона переходить на відсортований масив і бінарний пошук
- 3Вона відмовляє новим ключам, доки якісь не видалять
Пояснення
Коефіцієнт заповнення - це кількість записів, поділена на кількість комірок. Коли він перевищує поріг, колізії частішають, тож таблиця росте, зазвичай удвічі. Перехешування O(n), але рідкісне, тож вставки лишаються амортизовано O(1).