Хеш-таблицы с открытой адресацией.
Определение
Хеш-таблицы с открытой адресацией — это структура данных, использующая хеширование для организации данных, где все элементы хранятся непосредственно в самой хеш-таблице. В отличие от метода цепочек, при открытой адресации коллизии разрешаются путем поиска другой свободной ячейки в таблице.
При открытой адресации, если хеш-функция назначает элементу уже занятую ячейку, используется вторичный метод для нахождения другой свободной ячейки.
Основные методы открытой адресации:
- Линейное пробирование (Linear Probing): Если ячейка занята, проверяются следующие ячейки по порядку.
- Квадратичное пробирование (Quadratic Probing): Используется квадратичная функция для поиска следующей ячейки.
- Двойное хеширование (Double Hashing): Применяется вторая хеш-функция для вычисления шага смещения.