Изменения

'''ХешированиеХеш-табли́ца'''  {{-- класс методов -}} структура данных, реализующая интерфейс ассоциативного массива. Представляет собой эффективную структуру данных для реализации словарей, а именно, она позволяет хранить пары (ключ, значение) и выполнять три операции: операцию добавления новой пары, операцию поискаи операцию удаления пары по ключу. === Введение ===Существует два основных вида хеш-таблиц: ''с цепочками'' и ''открытой адресацией''. Хеш-таблица содержит некоторый массив <tex>H</tex>, идея элементы которого состоит есть пары (хеш-таблица с открытой адресацией) или списки пар (хеш-таблица с цепочками). Выполнение операции в хеш-таблице начинается с вычисления хеш-функции от ключа. Хеш-код <tex>i = h(key)</tex> играет роль индекса в использовании некоторой частичной информациимассиве <tex>H</tex>, а зная индекс, полученной из ключа мы можем выполнить требующуюся операцию (однозначно характеризующего элементдобавление, удаление или поиск). Количество коллизий зависит от хеш-функции; ключ чем лучше используемая хеш-функция, тем меньше вероятность их возникновения. При вставке в хеш-таблицу размером 365 ячеек всего лишь 23-х элементов вероятность коллизии превышает 50%<ref><tex>p(n) = 1 - 1 \cdot \left(1-\frac{1}{len}\right) \cdot \left(1-\frac{2}{len}\right) \cdots \left(1-\frac{n-1}{len}\right) = { len \cdot len-1 \cdots (len-n+1) \over len^n } </tex> <tex> = { len! \over len^n \cdot (len-n)!},</tex><br>где <tex>n</tex> {{---}} количество элементов в хеш-таблице является , а <tex>len</tex> {{---}} её размер.</ref> (при равномерном распределении значений хеш-кодомфункции)<ref>[http://ru.wikipedia.org/wiki/Парадокс_дней_рождения Парадокс дней рождения {{---}} Википедия]</ref>. Способ разрешения коллизий — важная составляющая любой хеш-таблицы. Полностью избежать коллизий для произвольных данных невозможно в принципе, и хорошая хеш-функция в качестве основы поискасостоянии только минимизировать их количество. Но, в некоторых специальных случаях их удаётся избежать. С Если все ключи элементов известны заранее, либо меняются очень редко, то можно подобрать хеш-функцию, с помощью которой, все ключи будут распределены по хеш-таблице без коллизий. Это хеш-таблицы с ''прямой адресацией''; в них все операции, такие как: поиск, вставка и удаление работают за <tex>O(1)</tex>. Если мы поделим число хранимых элементов на размер массива <tex>H</tex> (число возможных значений хеш-функции мы вычисляем ), то узнаем коэффициент заполнения хеш-таблицы (англ. ''load factor''). От этого параметра зависит среднее время выполнения операций. === Хеширование === '''Хеширование''' {{---}} класс методов поиска, идея которого состоит в вычислении хеш-кода, однозначно определяемого элементом с помощью хеш-код функции, и используем использовании его , как основы для проведения поиска(индексирование в памяти по хеш-коду выполняется за <tex>O(1)</tex>). В общем случае, однозначного соответствия между исходными данными и хеш-кодом нет в силу того, что количество значений хеш-функций меньше, чем вариантов исходных данных, поэтому существуют элементы, имеющие одинаковые хеш-коды — так называемые коллизии, но если два элемента имеют разный хеш-код, то они гарантированно

|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 = h(key)</tex> играет роль индекса в массиве <tex>H</tex>. Затем, зная индекс, мы можем выполнить требующуюся операцию (добавление, удаление или поиск). Ситуация, когда для различных ключей получается одинаковое хеш-значение, встречается не так уж и редко, и зависит от хеш-функции. Чем лучше, используемая хеш-функция, тем меньше вероятность возникновения коллизии. При вставке в хеш-таблицу размером 365 ячеек всего лишь 23-х элементов вероятность коллизии превышает 50 % (при равномерном распределении значений хеш-функции). Способ разрешения коллизий — важная составляющая любой хеш-таблицы. Полностью избежать коллизий для произвольных данных невозможно в принципе, и хорошая хеш-функция в состоянии только минимизировать их количество. Но, в некоторых специальных случаях их удаётся избежать. Если все ключи элементов известны заранее, либо меняются очень редко, то можно подобрать хеш-функцию, с помощью которой, все ключи будут распределены по хеш-таблице без коллизий. Это хеш-таблицы с ''прямой адресацией''; в них все операции, такие как: поиск, вставка и удаление работают за <tex>O(1)</tex>.

Если мы поделим число хранимых элементов на размер массива <tex>H</tex> (число возможных значений хеш-функции), то узнаем коэффициент заполнения === Свойства хеш-таблицы (load factor). От этого параметра зависит среднее время выполнения операций.===

== Свойства хеш-таблицы == На поиск элемента в хеш-таблице в худшем случае, может потребоваться столько же времени, как и в связанном списке, а именно <tex>\Theta(n)</tex>, но на практике хеширование исключительно более эффективно. При некоторых разумных допущениях математическое ожидание времени поиска элемента в хеш-таблице составляет <tex>O(1)</tex>. А все операции (поиск, вставка и удаление элементов) в среднем выполняются за время <tex>O(1)</tex>.При этом не гарантируется, что время выполнения отдельной операции мало́, так как при достижении некоторого значения коэффициента заполнения необходимо [[Перехеширование. Амортизационный анализ|перехешировать]] таблицу: увеличить размер массива <tex>H</tex> и заново добавить в новую хеш-таблицу все пары.

=== Хеширование цепочками Разрешение коллизий с помощью цепочек ===

Каждая ячейка <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>, как и вставка, при использовании двухсвязного списка.<ref>Анализ хеширования с цепочками, вы можете найти в книге Томаса Кормена: «Алгоритмы. Построение и анализ.»</ref>

=== Открытое хеширование с линейным разрешением Линейное разрешение коллизий ===

В массиве <tex>H</tex> Все элементы хранятся сами пары ключнепосредственно в хеш-значениетаблице, без использования связных списков. Алгоритм вставки элемента проверяет ячейки массива <tex>H</tex> в заданном порядке до тех порВ отличии от хеширования с цепочками, при использовании этого метода может возникнуть ситуация, когда хеш-таблица окажется полностью заполненной, пока не следовательно будет найдена первая свободная ячейка, невозможно добавлять в неё и будет записан новый элементновые элементы. Это позволяет сэкономить память на хранение указателейТак что при возникновении такой ситуации решением может быть динамическое увеличение размера хеш-таблицы, с одновременной её перестройкой.

Последовательность, в которой просматриваются ячейки хеш-таблицы, называется последовательностью пробРассмотрим один из таких методов. В общем случае, она зависит только от ключа элемента, то есть это последовательность <texref>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)</texref> — произвольные функции, сопоставляющие каждому ключу ячейку в хеш-таблице. Первый элемент в последовательности, как правило, равен значению некоторой хеш-функции от ключа, а остальные считаются от него каким-нибудь способом. Для успешной работы алгоритмов поиска последовательность проб должна быть такой, чтобы все ячейки хеш-таблицы оказались просмотренными ровно по одному разу.

В массиве <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> — произвольные функции, удалением является установка метки {{сопоставляющие каждому ключу ячейку в хеш-таблице. Первый элемент в последовательности, как правило, равен значению некоторой хеш-функции от ключа, а остальные считаются от него каким-}} удалённибудь способом. Для успешной работы алгоритмов поиска последовательность проб должна быть такой, для соответсвующей чтобы все ячейки хеш-таблицы, остаётся только модифицировать поиск (если удалён, то занято) и вставку (если удалён, то пусто) элементовоказались просмотренными ровно по одному разу.<ref>[[Поиск свободного места при закрытом хешировании | Поиск свободного места при закрытом хешировании]]</ref>

* Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. «Алгоритмы. Построение и анализ» {{---}} Издательство: «Вильямс», 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/Хеш-таблица Википедия: Хеш-таблица{{---}} Википедия]

[[Категория: Хеширование]]