Задачи модуля "Хеш-таблицы": от хеш-функций до коллизий
Суть урока. Хеш-таблицы кажутся магией из-за времени работы O(1), но за этой магией стоит строгая математика и алгоритмы разрешения коллизий. В этом уроке мы закрепим теорию и решим задачу на ручную трассировку заполнения хеш-таблицы.
Теоретические вопросы
Какие абстрактные типы данных реализуются на базе хеш-таблиц?
Какой из методов разрешения коллизий НЕ требует выделения дополнительной динамической памяти под новые узлы при каждой вставке?
Что такое коэффициент заполнения (Load Factor) хеш-таблицы?
Задача: Трассировка коллизий
Представьте, что мы последовательно вставляем числа 12, 5, 22, 17 в пустую хеш-таблицу размером 5.
Хеш-функция: h(x) = x % 5. Разрешение коллизий: открытая адресация с линейным пробированием (шаг 1).
Каким будет итоговое состояние массива после завершения всех вставок?
Итоговая раскладка после всех вставок - тот же массив, но уже заполненный:
Как вам урок?
Спасибо за отзыв!