2
правки
Изменения
м
'''Хеширование''' {{---}} класс методов поиска, идея которого состоит в вычислении хеш-кода, однозначно определяемого элементом с помощью хеш-функции, и использовании его, как основы для поиска (индексирование в памяти по хеш-коду выполняется за <tex>O(1)</tex>). В общем случае, однозначного соответствия между исходными данными и хеш-кодом нет в силу того, что количество значений хеш-функций меньше, чем вариантов исходных данных, поэтому существуют элементы, имеющие одинаковые хеш-коды — так называемые коллизии, но если два элемента имеют разный хеш-код, то они гарантированно
различаются. Вероятность возникновения коллизий играет немаловажную роль в оценке качества хеш-функций.
** Статическое {{---}} фиксированное количество элементов. Один раз заполняем хеш-таблицу и осуществляем только проверку на наличие в ней нужных элементов., ** Динамическое {{---}} добавляем, удаляем и смотрим на наличие нужных элементов.
** Детерминированная хеш-функция., ** Случайная хеш-функция.
ПоследовательностьПочти во всех современных языках присутствуют классы, в которой просматриваются ячейки хеш-таблицы, называется последовательностью пробреализующие хеширование. Рассмотрим некоторые из них. В общем случае, она зависит только от ключа элемента, то есть это последовательность *Java**HashMap <texref>h_0(x)[http://docs.oracle.com/javase/7/docs/api/java/util/HashMap.html HashMap {{---}} Java Platform SE 7]</texref>{{---}} реализация интерфейса ассоциативного массива с использованием хеш-таблицы, **HashSet <texref>h_1(x)<[http://tex>, docs.oracle.com/javase/7/docs/api/java/util/HashSet.,<tex>h_nhtml HashSet {{---}} Java Platform SE 7]</texref> {{---}} реализация интерфейса множества с использованием хеш-таблицы,**LinkedHashMap <texref>_[http://docs.oracle.com/javase/7/docs/api/java/util/LinkedHashMap.html LinkedHashMap {{---}} Java Platform SE 7]</texref>{{---}} потомок класса HashMap. Позволяет просматривать значения в том порядке, в котором они были добавлены.*C++**unordered_map <texref>_1<[http://www.cplusplus.com/reference/unordered_map/unordered_map/tex><tex>(x)unordered_map {{---}} cplusplus.com]</texref>{{---}} реализация интерфейса ассоциативного массива с использованием хеш-таблицы, где **unordered_set <texref>x[http://www.cplusplus.com/reference/unordered_map/unordered_set/ unordered_set {{---}} cplusplus.com]</texref> — ключ элемента, а {{---}} реализация интерфейса множества с использованием хеш-таблицы.*Python (CPython)**dict <texref>h_i(x)[https://github.com/python/cpython/blob/main/Objects/dictobject.c#L1 dictobject.c {{---}} https://github.com/python/cpython]</texref> — произвольные функции, сопоставляющие каждому ключу ячейку в хеш{{-таблице. Первый элемент в последовательности, как правило, равен значению некоторой хеш-функции от ключа, а остальные считаются от него каким-нибудь способом. Для успешной работы алгоритмов поиска последовательность проб должна быть такой, чтобы все ячейки }} реализация интерфейса ассоциативного массива с использованием хеш-таблицы оказались просмотренными ровно по одному разу.,**set <ref>[[Поиск свободного места при закрытом хешировании | Поиск свободного места при закрытом хешировании]https://hg.python.org/releasing/3.6/file/tip/Objects/setobject.c setobject.c {{---}} https://hg.python.org ]</ref>{{---}} реализация интерфейса множества с использованием хеш-таблицы.
→Хеширование в современных языках программирования
{{Определение|definition='''Хеш-табли́ца'''(англ. ''hash-table'') {{---}} структура данных, реализующая интерфейс ассоциативного массива. В отличие от [[Дерево_поиска,_наивная_реализация|деревьев поиска]], реализующих тот же интерфейс, обеспечивают меньшее время отклика в среднем. Представляет собой эффективную структуру данных для реализации словарей, а именно, она позволяет хранить пары (ключ, значение) и выполнять три операции: операцию добавления новой пары, операцию поиска и операцию удаления пары по ключу.}}
=== Введение ===
Существует два основных вида хеш-таблиц: [[Разрешение_коллизий#Разрешение коллизий с помощью цепочек|''с цепочками'' ]] и [[Разрешение_коллизий#Линейное разрешение коллизий|''открытой адресацией'']]. Хеш-таблица содержит некоторый массив <tex>H</tex>, элементы которого есть пары (хеш-таблица с открытой адресацией) или списки пар (хеш-таблица с цепочками).
Выполнение операции в хеш-таблице начинается с вычисления хеш-функции от ключа. Хеш-код <tex>i = h(key)</tex> играет роль индекса в массиве <tex>H</tex>, а зная индекс, мы можем выполнить требующуюся операцию (добавление, удаление или поиск).
Количество коллизий зависит от хеш-функции; чем лучше используемая хеш-функция, тем меньше вероятность их возникновения. При {{Лемма|statement=Вероятность коллизий при вставке в хеш-таблицу размером 365 ячеек всего лишь 23-х элементов вероятность коллизии превышает 50%|proof= Пусть хеш-таблица имеет размер <tex>len<ref/tex>и в нее добавляют <tex>n</tex> элементов. Рассмотрим <tex>{p}'(n) = </tex> — вероятность того, что не возникнет ни одной коллизии. Добавим два любых элемента в нашу хеш-таблицу. Вероятность того, что они не попадут в одну и ту же ячейку таблицы равна <tex>1 - \dfrac{1}{len}</tex>. Возьмем еще один элемент. Тогда вероятность того, что третий элемент не попадет в одну из уже занятых ячеек равна <tex>1 - \cdot dfrac{2}{len}</tex>. Рассуждая аналогичным образом, получим формулу:<tex>{p}'(n) = \left(1-\fracdfrac{1}{len}\right) \cdot \left(1-\fracdfrac{2}{len}\right) \cdots dots\left(1-\fracdfrac{n-1}{len}\right) = \dfrac{ len \cdot \left(len-1 \cdots right )\dots\left (len-n+1\right ) \over }{len^{n } </tex> <tex> } = \dfrac{ len! \over }{len^{n } \cdot \left (len-n\right)!},</tex><br>где Тогда <tex>{p}(n)</tex> — вероятность возникновения коллизии равна:<tex>p(n) = 1 - {{---p}} количество элементов в хеш-таблице, а '(n)</tex>len,что в общем случае </tex> > \dfrac{1}{---}2} её размер.</reftex> (при равномерном распределении значений хеш-функции)<ref>[http://ru.wikipedia.org/wiki/Парадокс_дней_рождения Парадокс дней рождения {{---}} Википедия]</ref>. Способ разрешения коллизий — важная составляющая любой хеш-таблицы.
Полностью избежать коллизий для произвольных данных невозможно в принципе, и хорошая хеш-функция в состоянии только минимизировать их количество. Но, в некоторых специальных случаях их удаётся избежать. Если все ключи элементов известны заранее, либо меняются очень редко, то можно подобрать хеш-функцию, с помощью которой, все ключи будут распределены по хеш-таблице без коллизий. Это хеш-таблицы с ''прямой адресацией''; в них все операции, такие как: поиск, вставка и удаление работают за <tex>O(1)</tex>.
=== Хеширование ===
'''Хеширование''' (англ. ''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>
}}
==== Виды хеширования ====
* По способу хранения:
* По виду хеш-функции:
=== Свойства хеш-таблицы ===
На поиск элемента в хеш-таблице в худшем случае, может потребоваться столько же времени, как и в списке, а именно <tex>\Theta(n)</tex>, но на практике хеширование более эффективно. При некоторых разумных допущениях [[Математическое_ожидание_случайной_величины|математическое ожидание ]] времени поиска элемента в хеш-таблице составляет <tex>O(1)</tex>. А все операции (поиск, вставка и удаление элементов) в среднем выполняются за время <tex>O(1)</tex>.
При этом не гарантируется, что время выполнения отдельной операции мало́, так как при достижении некоторого значения коэффициента заполнения необходимо [[Перехеширование. Амортизационный анализ|перехешировать]] таблицу: увеличить размер массива <tex>H</tex> и заново добавить в новую хеш-таблицу все пары.
== Разрешение коллизий == === Разрешение коллизий с помощью цепочек ===[[Файл:open_hash.png|thumb|380px|right|Разрешение коллизий при помощи цепочек.]]Каждая ячейка <tex>i</tex> массива <tex>H</tex> содержит указатель на начало списка всех элементов, хеш-код которых равен <tex>i</tex>, либо указывает на их отсутствие. Коллизии приводят к тому, что появляются списки размером больше одного элемента. Время, необходимое для вставки в наихудшем случае равно <tex>O(1)</tex>. Это операция выполняет быстро, так как считается, что вставляемый элемент отсутствует Хеширование в таблице, но если потребуется, то перед вставкой мы можем выполнить поиск этого элемента. Время работы поиска в наихудшем случае пропорционально длине списка, а если все <tex>n</tex> ключей захешировались в одну и ту же ячейку (создав список длиной <tex>n</tex>) время поиска будет равно <tex>\Theta(n)</tex> плюс время вычисления хеш-функции, что ничуть не лучше, чем использование связного списка для хранения всех <tex>n</tex> элементов. Удаления элемента может быть выполнено за <tex>O(1)</tex>, как и вставка, при использовании двухсвязного списка. === Линейное разрешение коллизий современных языках программирования===[[Файл:close_hash.png|thumb|380px|right|Пример хеш-таблицы с открытой адресацией и линейным пробированием.]]Все элементы хранятся непосредственно в хеш-таблице, без использования связных списков. В отличии от хеширования с цепочками, при использовании этого метода может возникнуть ситуация, когда хеш-таблица окажется полностью заполненной, следовательно будет невозможно добавлять в неё новые элементы. Так что при возникновении такой ситуации решением может быть динамическое увеличение размера хеш-таблицы, с одновременной её перестройкой. Рассмотрим один из таких методов.<ref>Другой метод борьбы с коллизиями {{---}} [[Двойное хеширование | двойное хеширование]]</ref> В массиве <tex>H</tex> хранятся сами пары ключ-значение. Алгоритм вставки элемента проверяет ячейки массива <tex>H</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
* [http://ru.wikipedia.org/wiki/Хеш-таблица Хеш-таблица Википедия {{---}} ВикипедияХеш-таблица]
[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Хеширование]]
[[Категория:Структуры данных]]
