Изменения

'''Хеширование''' — преобразование входного массива данных произвольной длины - класс методов поиска идея которого состоит в использовании некоторой частичной информации, полученной из ключа(однозначно характеризующего элемент), в короткое число фиксированной длиныкачестве основы поиска. Такие преобразования также называются С помощью хеш-функциями или функциями свёртки, а их результаты называют хешем, функции мы вычисляем хеш-кодом или дайджестом сообщениякод и используем его для проведения поиска. Хеширование применяется для сравнения данных: если Если у двух массивов элементов хеш-коды разные, массивы элементы гарантированно различаются; если одинаковые — массивыэлементы, скорее всего, одинаковы. В общем случае однозначного соответствия между исходными данными и хеш-кодом нет в силу того, что количество значений хеш-функций меньше, чем вариантов входного массиваисходных данных; существует множество массивовэлементы, дающих дающие одинаковые хеш-коды — так называемые коллизии. Вероятность возникновения коллизий играет немаловажную роль в оценке качества хеш-функций.

Выполнение операции в хеш-таблице начинается с вычисления хеш-функции от ключа. Получающееся хеш-значение <tex>i = hash(key)</tex> играет роль индекса в массиве <tex>H</tex>. Затем выполняемая операция (добавление, удаление или поиск) перенаправляется объекту,который хранится в соответствующей ячейке массива <tex>H[i]</tex>.

Ситуация, когда для различных ключей получается одно и то же хеш-значение, называется Коллизия коллизией. Такие события не так уж и редки — например, при вставке в хеш-таблицу размером 365 ячеек всего лишь 23-х элементов вероятность коллизии уже превысит 50 % (если каждый элемент может равновероятно попасть в любую ячейку). Поэтому механизм разрешения коллизий — важная составляющая любой хеш-таблицы.