Закрепление материала: Хеш-таблицы

Модуль "Хеш-таблицы" • урок 3 из 4 • ~5 минут

Краткое резюме модуля

В этом модуле мы изучили механизм работы хеш-таблиц под капотом:

• Хеш-таблица - структура данных, обеспечивающая поиск, вставку и удаление за амортизированное время O(1).
• Хеш-функция - алгоритм, преобразующий произвольный ключ (например, строку) в детерминированное целое число, которое затем сжимается до индекса массива.
• Метод цепочек - способ разрешения коллизий, при котором элементы с одинаковым индексом сохраняются в связный список (или дерево) внутри одной ячейки массива.
• Открытая адресация - способ разрешения коллизий, при котором все элементы хранятся непосредственно в самом массиве. При коллизии алгоритм ищет следующую свободную ячейку линейным или квадратичным пробированием.

Ключевые идеи

Важные концепции, которые необходимо понимать для эффективной работы с хеш-таблицами:

• Коллизия: неизбежная ситуация, когда два разных ключа получают один и тот же индекс в массиве. Хорошая хеш-функция минимизирует коллизии, но не исключает их полностью.
• Load Factor (коэффициент заполнения): отношение количества элементов к размеру массива. Чем он выше, тем больше коллизий и тем медленнее работает таблица.
• Рехеширование (Rehashing): процесс создания нового, увеличенного массива и полного пересчета индексов всех элементов. Выполняется автоматически при превышении допустимого Load Factor (обычно 0.7 - 0.75), чтобы спасти таблицу от деградации до O(N).
• Проблема удаления: в открытой адресации нельзя просто удалить элемент - это разорвет цепочку поиска для других элементов. Вместо этого используются специальные пометки "Удален" (tombstones).

Проверьте себя