Хэш-таблица, или ассоциативный массив, — это структура данных, реализующая интерфейс ассоциативного массива, то есть она связывает ключи со значениями. Она использует хэш-функцию для вычисления индекса, или "хэша", корзины или слота, где искомое значение должно находиться.
Основные компоненты:
- Ключ: Уникальный идентификатор элемента.
- Значение: Данные, связанные с ключом.
- Хэш-функция: Преобразует ключ в числовое значение (хэш), которое используется для определения индекса корзины.
- Корзины (Buckets): Массив, где хранятся пары ключ-значение.
- Обработка коллизий (Collision Handling): Механизм разрешения ситуаций, когда разные ключи дают один и тот же хэш (и, следовательно, указывают на одну корзину). Распространенные методы:
- Метод цепочек (Chaining): В каждой корзине хранится список (например, связный список) элементов, хэши которых указывают на эту корзину.
- Метод открытой адресации (Open Addressing): При коллизии ищется следующая свободная корзина с использованием алгоритмов, таких как линейное, квадратичное или двойное хэширование.
Принцип работы:
- Вставка: Хэш-функция применяется к ключу для получения хэша. Хэш используется для определения индекса корзины. Пара ключ-значение хранится в этой корзине. При наличии коллизии применяется метод обработки коллизий.
javascript
- Поиск: Хэш-функция применяется к ключу для получения хэша. Хэш используется для определения индекса корзины. Затем в этой корзине осуществляется поиск элемента с заданным ключом. При использовании метода цепочек ищется в списке внутри корзины. При открытой адресации последовательно проверяются другие корзины, пока не будет найден нужный элемент или не будет определено его отсутствие.
javascript
Преимущества:
- Высокая скорость операций вставки, поиска и удаления в среднем случае (O(1)).
- Эффективное использование памяти по сравнению с прямым адресным массивом (если ключи распределены разреженно).
Недостатки:
- Производительность может снизиться в случае большого количества коллизий (в худшем случае O(n)).
- Не сохраняется порядок вставки элементов.
- Требуется хорошая хэш-функция для равномерного распределения ключей.
В JavaScript хэш-таблицы реализованы встроенным объектом Map и исторически Object. Map является предпочтительным, так как позволяет использовать любые типы данных в качестве ключей и сохраняет порядок добавления элементов. Object преобразует все ключи в строки.