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>}} ==== Виды хеширования ====* По способу хранения** Статическое {{---}} фиксированное количество элементов. Один раз заполняем хеш-таблицу и осуществляем только проверку на наличие в ней нужных элементов.** Динамическое {{---}} добавляем, удаляем и смотрим на наличие нужных элементов.* По виду хеш-функции** Детерминированная хеш-функция и случайные входные данные** Случайная хеш-функция и произвольные входные данные
== Хеш-таблица ==
'''Хеш-табли́ца''' — это структура данных, реализующая интерфейс ассоциативного массива. Представляет собой эффективную структуру данных для реализации словарей, а именно, она позволяет хранить пары (ключ, значение) и выполнять три операции: операцию добавления новой пары, операцию поиска и операцию удаления пары по ключу.
== Введение ==
Существует два основных варианта хеш-таблиц: с цепочками и открытой адресацией. Хеш-таблица содержит некоторый массив <tex>H</tex>, элементы которого есть пары (хеш-таблица с открытой адресацией) или списки пар (хеш-таблица с цепочками).
Выполнение операции в хеш-таблице начинается с вычисления хеш-функции от ключа. Получающееся хеш-значение <tex>i = hashh(key)</tex> играет роль индекса в массиве <tex>H</tex>. Затем выполняемая операция , зная индекс, мы можем выполнить требующуюся операцию (добавление, удаление или поиск) перенаправляется объекту, который хранится в соответствующей ячейке массива <tex>H[i]</tex>.
Ситуация, когда для различных ключей получается одно и то же одинаковое хеш-значение(коллизия), называется коллизией. Такие события встречается не так уж и редки — напримерредко, и зависит от хеш-функции. Чем лучше, используемая хеш-функция, при тем меньше вероятность возникновения коллизии. При вставке в хеш-таблицу размером 365 ячеек всего лишь 23-х элементов вероятность коллизии уже превысит превышает 50 % (если каждый элемент может равновероятно попасть в любую ячейкупри равномерном распределении значений хеш-функции). Поэтому механизм Способ разрешения коллизий — важная составляющая любой хеш-таблицы.
== Свойства хеш-таблицы ==
== Разрешение коллизий ==
=== Открытое хеширование Хеширование цепочками ===
[[Файл:open_hash.png|thumb|380px|right|Разрешение коллизий при помощи цепочек.]]
Каждая ячейка <tex>i</tex> массива <tex>H</tex> является указателем содержит указатель на связный список(цепочку) пар ключ-значениеначало списка всех элементов, соответствующих одному и тому же хеш-значению значение ключакоторых равно <tex>i</tex>, иначе она содержит значение <tex>NIL</tex>. Коллизии просто приводят к тому, что появляются списки длиной более размером больше одного элемента.
Время работы поиска в наихудшем случае пропорционально длине списка, а если все <tex>n</tex> ключей хешированы в одну и ту же ячейку (создавая список длиной <tex>n</tex>) время поиска будет равно <tex>\Theta(n)</tex> плюс время вычисления хеш-функции, что ничуть не лучше, чем использование связного списка для хранения всех <tex>n</tex> элементов. Удаления элемента может быть выполнено за <tex>O(1)</tex>, как и вставка, при использовании двухсвязного списка.<ref>Анализ хеширования с цепочками, вы можете найти в книге Томаса Кормена: «Алгоритмы. Построение и анализ.»</ref> === Закрытое Открытое хеширование с линейным разрешением коллизий ===
[[Файл:close_hash.png|thumb|380px|right|Пример хеш-таблицы с открытой адресацией и линейным пробированием.]]
В массиве <tex>H</tex> хранятся сами пары ключ-значение. Алгоритм вставки элемента проверяет ячейки массива <tex>H</tex> в некотором заданном порядке до тех пор, пока не будет найдена первая свободная ячейка, в которую неё и будет записан новый элемент. Этот порядок вычисляется на лету, что Это позволяет сэкономить память на памяти для хранение указателей, требующихся в хеш-таблицах с цепочками.
Последовательность, в которой просматриваются ячейки хеш-таблицы, называется последовательностью проб. В общем случае, она зависит только от ключа элемента, то есть это последовательность <tex>h_0(x)</tex>, <tex>h_1(x)</tex>, ...,<tex>h_n</tex><tex>_-</tex><tex>_1</tex><tex>(x)</tex>, где <tex>x</tex> — ключ элемента, а <tex>h_i(x)</tex> — произвольные функции, сопоставляющие каждому ключу ячейку в хеш-таблице. Первый элемент в последовательности, как правило, равен значению некоторой хеш-функции от ключа, а остальные считаются от него каким-нибудь способом. Для успешной работы алгоритмов поиска последовательность проб должна быть такой, чтобы все ячейки хеш-таблицы оказались просмотренными ровно по одному разу.
Алгоритм поиска просматривает ячейки хеш-таблицы в том же самом порядке, что и при вставке, до тех пор, пока не найдется либо элемент с искомым ключом, либо свободная ячейка (что означает отсутствие элемента в хеш-таблице). Удаление элементов в такой схеме несколько затруднено. Можно поступить так: будем помечать каждую учейку по признаку, удалили мы из неё элемент, или нет. В этом случаем, удалением является установка метки {{---}} удалён, для соответсвующей ячейки хеш-таблицы, остаётся только модифицировать поиск (если удалён, то занято) и вставку (если удалён, то пусто) элементов.
=== Источники =Литература ==* Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. «Алгоритмы. Построение и анализ» {{---}} Издательство: «Вильямс», 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/Хеширование Википедия: Хеширование]* [http://ru.wikipedia.org/wiki/Хеш-таблица Википедия: Хеш-таблица]
[[Категория:Дискретная математика и алгоритмы]]
[[Категория: Хеширование]]
