Хеш-таблица использует хеш-функцию для преобразования ключа в индекс массива, называемого бакетом.
Основные шаги:
- Хеширование ключа: Ключ передается хеш-функции, которая возвращает числовое значение (хеш-значение).
- Вычисление индекса бакета: Хеш-значение используется для вычисления индекса в массиве (обычно с помощью операции по модулю).
index = хеш_значение % размер_массива.
- Хранение/Поиск: Данные (пара ключ-значение) хранятся или извлекаются по вычисленному индексу.
Разрешение коллизий:
Коллизия возникает, когда два разных ключа имеют одинаковое хеш-значение и, следовательно, вычисляют один и тот же индекс бакета. Основные методы:
- Метод цепочек (Separate Chaining): Каждый бакет хранит связный список или другую структуру данных, содержащую все пары ключ-значение, которые хешируются в этот бакет.
- Метод открытой адресации (Open Addressing): Если бакет занят, ищется следующий свободный бакет по определенному правилу (например, линейное или квадратичное пробирование).
Пример (концептуальный):
python
Хеш-таблица использует хеш-функцию для преобразования ключа в индекс массива, называемого бакетом.
Основные шаги:
- Хеширование ключа: Ключ передается хеш-функции, которая возвращает числовое значение (хеш-значение).
- Вычисление индекса бакета: Хеш-значение используется для вычисления индекса в массиве (обычно с помощью операции по модулю).
index = хеш_значение % размер_массива.
- Хранение/Поиск: Данные (пара ключ-значение) хранятся или извлекаются по вычисленному индексу.
Разрешение коллизий:
Коллизия возникает, когда два разных ключа имеют одинаковое хеш-значение и, следовательно, вычисляют один и тот же индекс бакета. Основные методы:
- Метод цепочек (Separate Chaining): Каждый бакет хранит связный список или другую структуру данных, содержащую все пары ключ-значение, которые хешируются в этот бакет.
- Метод открытой адресации (Open Addressing): Если бакет занят, ищется следующий свободный бакет по определенному правилу (например, линейное или квадратичное пробирование).
Пример (концептуальный):
python