Хеш-функции. Хеш-таблицы с прямой адресацией.

Определение

Хеш-функция — это функция, которая принимает на вход данные (ключ) и возвращает число, называемое хеш-значением или хеш-кодом. Это число используется для определения позиции ключа в хеш-таблице.

Свойства и требования

1. Детерминированность: Одинаковый вход должен всегда давать одинаковый выход.
2. Эффективность: Хеш-функция должна быть вычисляема за постоянное время O(1).
3. Равномерность: Хеш-функция должна равномерно распределять ключи по всей таблице, чтобы минимизировать количество коллизий.
4. Необратимость: Невозможность восстановления ключа по значению его функции.
5. Лавинность: при изменении одного бита последовательности меняется значительное кол-во выходных бит.

Коллизия

Коллизия происходит, когда два различных ключа хешируются в одну и ту же позицию. Существует несколько методов для разрешения коллизий:

1. Метод цепочек (Chaining): Каждая ячейка таблицы хранит список всех элементов, которые хешируются в эту ячейку.
2. Открытая адресация (Open Addressing): Все элементы хранятся в самой таблице, а в случае коллизии используется определённая стратегия для поиска следующей свободной ячейки (например, линейное или квадратичное пробирование).

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

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

Прямая адресация

1. Инициализация: Создается массив (хеш-таблица) достаточного размера для всех возможных ключей.
2. Вставка: Ключ используется напрямую как индекс для хранения значения.
3. Поиск: Ключ используется напрямую как индекс для получения значения.
4. Удаление: Ключ используется напрямую как индекс для удаления значения.