Изменения
→Введение
== Введение ==
Существует два основных варианта хеш-таблиц: с цепочками и открытой адресацией. Хеш-таблица содержит некоторый массив <mathtex>H</mathtex>, элементы которого есть пары (хеш-таблица с открытой адресацией) или списки пар (хеш-таблица с цепочками).
Выполнение операции в хеш-таблице начинается с вычисления Хеш-функция|хеш-функции от ключа. Получающееся хеш-значение <mathtex>i = \mbox{hash}(key)</mathtex> играет роль индекса в массиве <mathtex>H</mathtex>. Затем выполняемая операция (добавление, удаление или поиск) перенаправляется объекту,который хранится в соответствующей ячейке массива <mathtex>H[i]</mathtex>.
Ситуация, когда для различных ключей получается одно и то же хеш-значение, называется Коллизия коллизией. Такие события не так уж и редки — например, при вставке в хеш-таблицу размером 365 ячеек всего лишь 23-х элементов вероятность коллизии уже превысит 50 % (если каждый элемент может равновероятно попасть в любую ячейку). Поэтому механизм разрешения коллизий — важная составляющая любой хеш-таблицы.
В некоторых специальных случаях удаётся избежать коллизий вообще. Например, если все ключи элементов известны заранее (или очень редко меняются), то для них можно найти некоторую совершенную хеш-функцию, которая распределит их по ячейкам хеш-таблицы без коллизий. Хеш-таблицы, использующие подобные хеш-функции, не нуждаются в механизме разрешения коллизий, и называются хеш-таблицами с ''прямой адресацией''.
Число хранимых элементов, делённое на размер массива <mathtex>H</mathtex> (число возможных значений хеш-функции), называется '''коэффициентом заполнения хеш-таблицы''' (load factor) и является важным параметром, от которого зависит среднее время выполнения операций.
== Свойства хеш-таблицы ==
