277
правок
Изменения
Qqqq
,→Введение
Существует два основных варианта хеш-таблиц: с цепочками и открытой адресацией. Хеш-таблица содержит некоторый массив <tex>H</tex>, элементы которого есть пары (хеш-таблица с открытой адресацией) или списки пар (хеш-таблица с цепочками).
Выполнение операции в хеш-таблице начинается с вычисления хеш-функции от ключа. Получающееся хеш-значение <tex>i = hashh(key)</tex> играет роль индекса в массиве <tex>H</tex>. Затем выполняемая операция , зная индекс, мы можем выполнить требующуюся операцию (добавление, удаление или поиск) перенаправляется объекту, который хранится в соответствующей ячейке массива <tex>H[i]</tex>.
Ситуация, когда для различных ключей получается одно и то же одинаковое хеш-значение(коллизия), называется коллизией. Такие события встречается не так уж и редки — напримерредко, и зависит от хеш-функции. Чем лучше, используемая хеш-функция, при тем меньше вероятность возникновения коллизии. При вставке в хеш-таблицу размером 365 ячеек всего лишь 23-х элементов вероятность коллизии уже превысит превышает 50 % (если каждый элемент может равновероятно попасть в любую ячейкупри равномерном распределении значений хеш-функции). Поэтому механизм Способ разрешения коллизий — важная составляющая любой хеш-таблицы.
== Свойства хеш-таблицы ==
