277
правок
Изменения
Нет описания правки
'''Хеширование''' - класс методов поиска, идея которого состоит в использовании некоторой частичной информации, полученной из ключа (однозначно характеризующего элемент; ключ в хеш-таблице является хеш-кодом), в качестве основы поиска. С помощью хеш-функции мы вычисляем хеш-код и используем его для проведения поиска. В общем случае, однозначного соответствия между исходными данными и хеш-кодом нет в силу того, что количество значений хеш-функций меньше, чем вариантов исходных данных, поэтому существуют элементы, имеющие одинаковые хеш-коды — так называемые коллизии, но если два элемента имеют разный хеш-код, то они гарантированно
различаются. Вероятность возникновения коллизий играет немаловажную роль в оценке качества хеш-функций.
{{Определение
|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>
}}
=== Хеширование цепочками ===
[[Файл:open_hash.png|thumb|380px|right|Разрешение коллизий при помощи цепочек.]]
Каждая ячейка <tex>i</tex> массива <tex>H</tex> содержит указатель на начало списка всех элементов, хеш-значение ключа которых равно <tex>i</tex>, иначе она содержит значение <tex>NIL</tex>либо указывает на их отсутствие. Коллизии приводят к тому, что появляются списки размером больше одного элемента.
Время, необходимое для вставки в наихудшем случае равно <tex>O(1)</tex>. Это операция выполняет быстро, так как считается, что вставляемый элемент отсутствует в таблице, но если потребуется, то перед вставкой мы может выполнить поиск этого элемента.
<references/>
== Литература Источники ==
* Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. «Алгоритмы. Построение и анализ» {{---}} Издательство: «Вильямс», 2011 г. - 1296 стр. {{---}} ISBN 978-5-8459-0857-5, 5-8459-0857-4, 0-07-013151-1
* Дональд Кнут. «Искусство программирования, том 3. Сортировка и поиск» {{---}} Издательство: «Вильямс», 2007 г. — 824 стр. {{---}} ISBN 0-201-89685-0
