Изменения

<tex>q</tex> '''Хеширование''' - класс методов поиска , идея которого состоит в использовании некоторой частичной информации, полученной из ключа(однозначно характеризующего элемент), в качестве основы поиска.С помощью хеш-функции мы вычисляем хеш-код и используем его для проведения поиска.Если у двух элементов хеш-коды разные, элементы гарантированно различаются; если одинаковые — элементы, скорее всего, одинаковы. В общем случае однозначного соответствия между исходными данными и хеш-кодом нет в силу того, что количество значений хеш-функций меньше, чем вариантов исходных данных; существует , поэтому существуют элементы, дающие имеющие одинаковые хеш-коды — так называемые коллизии, но если два элемента имеют разный хеш-код, то они гарантированно различаются. Вероятность возникновения коллизий играет немаловажную роль в оценке качества хеш-функций.{{Определение|id=def1|definition=<tex>] U </tex> {{---}} множество объектов (универсум).<br> Тогда <tex>h : U \rightarrow S = \mathcal {f} 0 ... m - 1 \mathcal {g}</tex> называется хеш-функцией, где множество <tex>S</tex> хранит ключи из множества <tex>U</tex>.<br> Если <tex>x \in U</tex> значит <tex>h(x) \in S</tex> <br> Коллизия: <tex>\exists x \neq y : h(x) = h(y)</tex>}}