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