Хеш-таблица (или ассоциативный массив) хранит пары "ключ-значение". Принцип работы основан на использовании хеш-функции, которая преобразует ключ в числовой индекс (хеш), указывающий на место хранения значения в массиве (корзине).
Шаги:
- Вычисление хеша: Для заданного ключа вычисляется хеш.
php
- Определение индекса: Хеш преобразуется в индекс массива, обычно с помощью операции по модулю от размера массива.
php
- Доступ к корзине: По вычисленному индексу осуществляется доступ к соответствующей корзине в массиве.
- Разрешение коллизий: Поскольку разные ключи могут иметь одинаковый хеш (коллизия), корзина может содержать несколько пар "ключ-значение". Для разрешения коллизий используются разные методы:
- Метод цепочек (Separate Chaining): В каждой корзине хранится список (например, связанный список) пар "ключ-значение", хеши которых совпадают.
- Метод открытой адресации (Open Addressing): При коллизии производится повторный поиск свободной ячейки в массиве по определенному правилу (линейное, квадратичное пробирование, двойное хеширование).
Операции:
- Вставка: Вычисляется хеш ключа, определяется индекс, и пара "ключ-значение" помещается в соответствующую корзину. При коллизии добавляется в список (цепочки) или ищется свободное место (открытая индексация).
- Поиск: Вычисляется хеш ключа, определяется индекс. В соответствующей корзине ищется значение по ключу. При методе цепочек перебираются элементы списка; при открытой индексации производится последовательный поиск.
- Удаление: Вычисляется хеш ключа, определяется индекс. В соответствующей корзине находится и удаляется пара по ключу.
Преимущества:
- Быстрый доступ к элементам (в среднем O(1)).
- Эффективное использование памяти.
Недостатки:
- Производительность может ухудшаться при большом количестве коллизий.
- Размер таблицы может требовать регулировки (изменение размера - rehashing) для поддержания эффективности.