Объяснение
Хеш-таблица преобразует ключ в номер корзины. Разные ключи могут иметь одинаковый хеш, поэтому после выбора корзины нужно сравнить сами ключи. Среднее O(1) зависит от распределения и коэффициента заполнения.
Задача для самостоятельного решения
В таблице из 4 корзин h(k)=k mod 4 разместите 2, 6, 9.
Показать разбор ответа
Корзина 2 содержит 2 и 6, корзина 1 — 9. При цепочках поиск 6 проверяет два ключа. Увеличение ёмкости требует пересчитать позиции, а не скопировать корзины.