Хеш-таблица | Структуры данных и алгоритмы | Изучение алгоритмов

YOUTUBE · 30.11.2025 05:59

Ключевые темы и таймкоды

Введение в хэш-таблицы

0:00

Хэш-таблицы — популярная структура данных, используемая в многих проектах.
Они применяются для быстрого поиска данных, например, в индексах баз данных.
Пример использования: хранение идентификаторов пользователей и их счетов.

Прямой доступ

0:59

Создание массива пар: идентификатор пользователя как индекс, счёт как значение.
Проблема: массив может быть разряженным из-за пропусков между индексами.
Ограничения: массив должен быть достаточно большим, что может быть неэффективно.

Хэш-функции

2:35

Хэш-функции преобразуют большое множество значений в маленькое для эффективного использования памяти.
Свойства хэш-функций: быстрота, необратимость, распределённость, детерминированность.
Пример примитивной хэш-функции: остаток от деления числа на максимальный размер массива.

Применение хэш-функций

5:27

Вставка данных: вычисление хэш-значения ключа и сохранение его в соответствующем индексе массива.
Поиск данных: использование хэш-значения для нахождения индекса и извлечения значения.
Ячейки в хэш-таблице называются бакетами.

Хэш-коллизии

8:23

Хэш-коллизия возникает, когда два разных ключа имеют одинаковое хэш-значение.
Задача разработчиков: научиться работать с хэш-коллизиями для корректной работы хэш-таблицы.
Два основных подхода: механизм на основе цепочек и открытая адресация.

Механизмы решения хэш-коллизий

9:23

Механизм на основе цепочек: использование цепочек для управления коллизиями.
Открытая адресация: различные механизмы пробирования линейное, квадратичное, дабл-хэшинг.
Начало обсуждения с механизма на основе цепочек как более простого подхода.

Введение в хэш-таблицу

9:44

Обсуждение метода на основе цепочек в хэш-таблице.
Внутри массива хранятся указатели, а не сами значения.
Пример вставки данных: пользователь с индексом 5 и счётом 200.

Реализация хэш-таблицы

10:44

Возможные реализации: связанный список, бинарное дерево, динамический массив.
Типичный подход: использование связанных списков.
Объяснение необходимости хранения ключа.

Коллизии и их разрешение

11:53

Создание коллизии при вставке элемента с индексом 9 и счётом 900.
Добавление дополнительного звена к связанному списку при коллизии.

Поиск и удаление элементов

12:33

Процесс поиска элемента по ключу: вычисление хэш-функции и проверка связанного списка.
Пример поиска элемента с индексом 9.
Удаление элемента: нахождение, удаление и обновление ссылок.

Лод-фактор и реиндексирование

14:22

Определение лод-фактора: коэффициент загруженности хэш-таблицы.
Операция реиндексирования при достижении критического значения лод-фактора.
Перевыделение памяти и перераспределение элементов.

Итерация по хэш-таблице

17:31

Проблема неэффективной итерации по пустым ячейкам.
Использование набора динамический массив + связанный список для улучшения производительности.

Алгоритм разрешения коллизий

18:02

Вставка элементов в отдельный связанный список.
Перенос связей при коллизии.
Преимущества алгоритма: быстрая итерация и эффективность поиска.

Поиск и удаление в алгоритме разрешения коллизий

20:32

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

Заключение

21:32

Упоминание алгоритма разрешения коллизий как основного подхода в большинстве языков программирования.
Анонс обсуждения открытого адресации как альтернативного подхода.

Вставка элементов в хэш-таблицу

21:48

Использование динамического массива и открытой адресации.
Пример вставки элемента: 5 и 500, хэш равен 1.
Вставка элемента 3 и 300, хэш равен 3.

Коллизии и пробирование

22:49

Пример коллизии: 9 и 900, хэш равен 1, но первый индекс занят.
Пробирование: поиск свободной ячейки, переход к следующей.
Ограничение количества пробирований для оптимизации.

Методы пробирования

24:56

Линейное пробирование: последовательный поиск ячеек.
Квадратичное пробирование: поиск с увеличением на 2.
Дабл-хэшинг: использование двух хэш-функций для равномерного распределения коллизий.

Поиск и удаление элементов

25:56

Поиск элемента: расчёт хэша, поиск до пустой ячейки.
Удаление элемента: расчёт хэша, поиск и удаление.
Оптимизация: использование булевых флагов для пометке удалённых элементов.

Дополнительные оптимизации

27:40

Сдвиг коллизий влево при линейном пробировании.
Метод открытой адресации как популярный вариант.
Ссылка на реализацию хэш-таблиц на GitHub.