Хеширование — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Свойства хеш-таблицы)
Строка 1: Строка 1:
'''Хеширование''' - класс методов поиска, идея которого состоит в использовании некоторой частичной информации, полученной из ключа (однозначно характеризующего элемент), в качестве основы поиска. С помощью хеш-функции мы вычисляем хеш-код и используем его для проведения поиска. В общем случае, однозначного соответствия между исходными данными и хеш-кодом нет в силу того, что количество значений хеш-функций меньше, чем вариантов исходных данных, поэтому существуют элементы, имеющие одинаковые хеш-коды — так называемые коллизии, но если два элемента имеют разный хеш-код, то они гарантированно  
+
'''Хеширование''' {{---}} класс методов поиска, идея которого состоит в использовании некоторой частичной информации, полученной из ключа (однозначно характеризующего элемент; ключ в хеш-таблице является хеш-кодом), в качестве основы поиска. С помощью хеш-функции мы вычисляем хеш-код и используем его для проведения поиска. В общем случае, однозначного соответствия между исходными данными и хеш-кодом нет в силу того, что количество значений хеш-функций меньше, чем вариантов исходных данных, поэтому существуют элементы, имеющие одинаковые хеш-коды — так называемые коллизии, но если два элемента имеют разный хеш-код, то они гарантированно  
 
различаются. Вероятность возникновения коллизий играет немаловажную роль в оценке качества хеш-функций.
 
различаются. Вероятность возникновения коллизий играет немаловажную роль в оценке качества хеш-функций.
 
{{Определение
 
{{Определение
 
|id=def1
 
|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>
+
|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>
 
}}
 
}}
  
Строка 17: Строка 17:
 
== Хеш-таблица ==
 
== Хеш-таблица ==
  
'''Хеш-табли́ца''' — структура данных, реализующая интерфейс ассоциативного массива. Представляет собой эффективную структуру данных для реализации словарей, а именно, она позволяет хранить пары (ключ, значение) и выполнять три операции: операцию добавления новой пары, операцию поиска и операцию удаления пары по ключу.
+
'''Хеш-табли́ца''' {{---}} структура данных, реализующая интерфейс ассоциативного массива. Представляет собой эффективную структуру данных для реализации словарей, а именно, она позволяет хранить пары (ключ, значение) и выполнять три операции: операцию добавления новой пары, операцию поиска и операцию удаления пары по ключу.
  
== Введение ==
+
==== Введение ====
Существует два основных варианта хеш-таблиц: с цепочками и открытой адресацией. Хеш-таблица содержит некоторый массив <tex>H</tex>, элементы которого есть пары (хеш-таблица с открытой адресацией) или списки пар (хеш-таблица с цепочками).
+
Существует два основных варианта хеш-таблиц: ''с цепочками'' и ''открытой адресацией''. Хеш-таблица содержит некоторый массив <tex>H</tex>, элементы которого есть пары (хеш-таблица с открытой адресацией) или списки пар (хеш-таблица с цепочками).
  
 
Выполнение операции в хеш-таблице начинается с вычисления хеш-функции от ключа. Получающееся хеш-значение <tex>i = h(key)</tex> играет роль индекса в массиве <tex>H</tex>. Затем, зная индекс, мы можем выполнить требующуюся операцию (добавление, удаление или поиск).
 
Выполнение операции в хеш-таблице начинается с вычисления хеш-функции от ключа. Получающееся хеш-значение <tex>i = h(key)</tex> играет роль индекса в массиве <tex>H</tex>. Затем, зная индекс, мы можем выполнить требующуюся операцию (добавление, удаление или поиск).
  
Ситуация, когда для различных ключей получается одинаковое хеш-значение (коллизия), встречается не так уж и редко, и зависит от хеш-функции. Чем лучше, используемая хеш-функция, тем меньше вероятность возникновения коллизии. При вставке в хеш-таблицу размером 365 ячеек всего лишь 23-х элементов вероятность коллизии превышает 50 % (при равномерном распределении значений хеш-функции). Способ разрешения коллизий — важная составляющая любой хеш-таблицы.
+
Ситуация, когда для различных ключей получается одинаковое хеш-значение, встречается не так уж и редко, и зависит от хеш-функции. Чем лучше, используемая хеш-функция, тем меньше вероятность возникновения коллизии. При вставке в хеш-таблицу размером 365 ячеек всего лишь 23-х элементов вероятность коллизии превышает 50 % (при равномерном распределении значений хеш-функции)<ref>[http://ru.wikipedia.org/wiki/Парадокс_дней_рождения Википедия: Парадокс дней рождений]</ref>. Способ разрешения коллизий — важная составляющая любой хеш-таблицы.
  
Полностью избежать коллизий для произвольных данных невозможно в принципе, и хорошая хеш-функция в состоянии только минимизировать их количество. Но, в некоторых специальных случаях их удаётся избежать. Если все ключи элементов известны заранее, либо меняются очень редко, то можно подобрать хеш-функцию, с помощью которой, все ключи будут распределены по хеш-таблице без коллизий. Это хеш-таблицы с ''прямой адресацией''; в них все операции, такие как: поиск, вставка и удаление {{---}} работают за <tex>O(1)</tex>.
+
Полностью избежать коллизий для произвольных данных невозможно в принципе, и хорошая хеш-функция в состоянии только минимизировать их количество. Но, в некоторых специальных случаях их удаётся избежать. Если все ключи элементов известны заранее, либо меняются очень редко, то можно подобрать хеш-функцию, с помощью которой, все ключи будут распределены по хеш-таблице без коллизий. Это хеш-таблицы с ''прямой адресацией''; в них все операции, такие как: поиск, вставка и удаление работают за <tex>O(1)</tex>.
  
 
Если мы поделим число хранимых элементов на размер массива <tex>H</tex> (число возможных значений хеш-функции), то узнаем коэффициент заполнения хеш-таблицы (load factor). От этого параметра зависит среднее время выполнения операций.
 
Если мы поделим число хранимых элементов на размер массива <tex>H</tex> (число возможных значений хеш-функции), то узнаем коэффициент заполнения хеш-таблицы (load factor). От этого параметра зависит среднее время выполнения операций.
  
== Свойства хеш-таблицы ==
+
==== Свойства хеш-таблицы ====
  
 
На поиск элемента в хеш-таблице в худшем случае, может потребоваться столько же времени, как и в связанном списке, а именно <tex>\Theta(n)</tex>, но на практике хеширование исключительно эффективно. При некоторых разумных допущениях математическое ожидание времени поиска элемента в хеш-таблице составляет <tex>O(1)</tex>. А все операции (поиск, вставка и удаление элементов) в среднем выполняются за время <tex>O(1)</tex>.
 
На поиск элемента в хеш-таблице в худшем случае, может потребоваться столько же времени, как и в связанном списке, а именно <tex>\Theta(n)</tex>, но на практике хеширование исключительно эффективно. При некоторых разумных допущениях математическое ожидание времени поиска элемента в хеш-таблице составляет <tex>O(1)</tex>. А все операции (поиск, вставка и удаление элементов) в среднем выполняются за время <tex>O(1)</tex>.
Строка 37: Строка 37:
 
== Разрешение коллизий ==
 
== Разрешение коллизий ==
  
=== Хеширование цепочками ===
+
=== Открытое хеширование ===
 
[[Файл:open_hash.png|thumb|380px|right|Разрешение коллизий при помощи цепочек.]]
 
[[Файл:open_hash.png|thumb|380px|right|Разрешение коллизий при помощи цепочек.]]
Каждая ячейка <tex>i</tex> массива <tex>H</tex> содержит указатель на начало списка всех элементов, хеш-значение ключа которых равно <tex>i</tex>, иначе она содержит значение <tex>NIL</tex>. Коллизии приводят к тому, что появляются списки размером больше одного элемента.
+
Открытое хеширование или хеширование цепочками. Каждая ячейка <tex>i</tex> массива <tex>H</tex> содержит указатель на начало списка всех элементов, хеш-значение ключа которых равно <tex>i</tex>, либо указывает на их отсутствие. Коллизии приводят к тому, что появляются списки размером больше одного элемента.
  
Время, необходимое для вставки в наихудшем случае равно <tex>O(1)</tex>. Это операция выполняет быстро, так как считается, что вставляемый элемент отсутствует в таблице, но если потребуется, то перед вставкой мы может выполнить поиск этого элемента.
+
Время, необходимое для вставки в наихудшем случае равно <tex>O(1)</tex>. Это операция выполняет быстро, так как считается, что вставляемый элемент отсутствует в таблице, но если потребуется, то перед вставкой мы можем выполнить поиск этого элемента.
  
 
Время работы поиска в наихудшем случае пропорционально длине списка, а если все <tex>n</tex> ключей хешированы в одну и ту же ячейку (создавая список длиной <tex>n</tex>) время поиска будет равно <tex>\Theta(n)</tex> плюс время вычисления хеш-функции, что ничуть не лучше, чем использование связного списка для хранения всех <tex>n</tex> элементов.
 
Время работы поиска в наихудшем случае пропорционально длине списка, а если все <tex>n</tex> ключей хешированы в одну и ту же ячейку (создавая список длиной <tex>n</tex>) время поиска будет равно <tex>\Theta(n)</tex> плюс время вычисления хеш-функции, что ничуть не лучше, чем использование связного списка для хранения всех <tex>n</tex> элементов.
Строка 47: Строка 47:
 
Удаления элемента может быть выполнено за <tex>O(1)</tex>, как и вставка, при использовании двухсвязного списка.<ref>Анализ хеширования с цепочками, вы можете найти в книге Томаса Кормена: «Алгоритмы. Построение и анализ.»</ref>
 
Удаления элемента может быть выполнено за <tex>O(1)</tex>, как и вставка, при использовании двухсвязного списка.<ref>Анализ хеширования с цепочками, вы можете найти в книге Томаса Кормена: «Алгоритмы. Построение и анализ.»</ref>
  
=== Открытое хеширование с линейным разрешением коллизий ===
+
=== Закрытое хеширование ===
 
[[Файл:close_hash.png|thumb|380px|right|Пример хеш-таблицы с открытой адресацией и линейным пробированием.]]
 
[[Файл:close_hash.png|thumb|380px|right|Пример хеш-таблицы с открытой адресацией и линейным пробированием.]]
 +
В случае метода открытой адресации (или по-другому {{---}} метод закрытого хеширования) все элементы хранятся непосредственно в хеш-таблице, без использования связных списков. В отличии от хеширования с цепочками, при использовании метода открытой адресации может возникнуть ситуация, когда хеш-таблица окажется полностью заполненной, следовательно будет невозможно добавлять в неё новые элементы. Так что при возникновении такой ситуации решением может быть динамическое увеличение размера хеш-таблицы, с одновременной её перестройкой.
 +
 +
Рассмотрим один из методов борьбы с коллизиями.
 +
 +
==== Линейное разрешение коллизий ====
 
В массиве <tex>H</tex> хранятся сами пары ключ-значение. Алгоритм вставки элемента проверяет ячейки массива <tex>H</tex> в заданном порядке до тех пор, пока не будет найдена первая свободная ячейка, в неё и будет записан новый элемент. Это позволяет сэкономить память на хранение указателей.
 
В массиве <tex>H</tex> хранятся сами пары ключ-значение. Алгоритм вставки элемента проверяет ячейки массива <tex>H</tex> в заданном порядке до тех пор, пока не будет найдена первая свободная ячейка, в неё и будет записан новый элемент. Это позволяет сэкономить память на хранение указателей.
  
Строка 60: Строка 65:
 
<references/>
 
<references/>
  
== Литература ==
+
== Источники ==
* Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. «Алгоритмы. Построение и анализ» {{---}} Издательство: «Вильямс», 2011 г. - 1296 стр. {{---}} ISBN 978-5-8459-0857-5, 5-8459-0857-4, 0-07-013151-1
+
* Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. «Алгоритмы. Построение и анализ» {{---}} «Вильямс», 2011 г. {{---}} 1296 стр. {{---}} ISBN 978-5-8459-0857-5, 5-8459-0857-4, 0-07-013151-1
* Дональд Кнут. «Искусство программирования, том 3. Сортировка и поиск» {{---}} Издательство: «Вильямс», 2007 г. 824 стр. {{---}} ISBN 0-201-89685-0
+
* Дональд Кнут. «Искусство программирования, том 3. Сортировка и поиск» {{---}} «Вильямс», 2007 г. {{---}} 824 стр. {{---}} ISBN 0-201-89685-0
 
* [http://ru.wikipedia.org/wiki/Хеширование Википедия: Хеширование]
 
* [http://ru.wikipedia.org/wiki/Хеширование Википедия: Хеширование]
 
* [http://ru.wikipedia.org/wiki/Хеш-таблица Википедия: Хеш-таблица]
 
* [http://ru.wikipedia.org/wiki/Хеш-таблица Википедия: Хеш-таблица]
  
 
[[Категория:Дискретная математика и алгоритмы]]
 
[[Категория:Дискретная математика и алгоритмы]]
[[Категория: Хеширование]]
+
[[Категория:Хеширование]]

Версия 21:04, 29 апреля 2012

Хеширование — класс методов поиска, идея которого состоит в использовании некоторой частичной информации, полученной из ключа (однозначно характеризующего элемент; ключ в хеш-таблице является хеш-кодом), в качестве основы поиска. С помощью хеш-функции мы вычисляем хеш-код и используем его для проведения поиска. В общем случае, однозначного соответствия между исходными данными и хеш-кодом нет в силу того, что количество значений хеш-функций меньше, чем вариантов исходных данных, поэтому существуют элементы, имеющие одинаковые хеш-коды — так называемые коллизии, но если два элемента имеют разный хеш-код, то они гарантированно различаются. Вероятность возникновения коллизий играет немаловажную роль в оценке качества хеш-функций.

Определение:
[math]U [/math] — множество объектов (универсум).
[math]h : U \rightarrow S = \mathcal {f} 0 ... m - 1 \mathcal {g}[/math] — называется хеш-функцией, где множество [math]S[/math] хранит ключи из множества [math]U[/math].
Если [math]x \in U[/math] значит [math]h(x) \in S[/math]
Коллизия: [math]\exists x \neq y : h(x) = h(y)[/math]


Виды хеширования

  • По способу хранения
    • Статическое — фиксированное количество элементов. Один раз заполняем хеш-таблицу и осуществляем только проверку на наличие в ней нужных элементов.
    • Динамическое — добавляем, удаляем и смотрим на наличие нужных элементов.
  • По виду хеш-функции
    • Детерминированная хеш-функция и случайные входные данные
    • Случайная хеш-функция и произвольные входные данные

Хеш-таблица

Хеш-табли́ца — структура данных, реализующая интерфейс ассоциативного массива. Представляет собой эффективную структуру данных для реализации словарей, а именно, она позволяет хранить пары (ключ, значение) и выполнять три операции: операцию добавления новой пары, операцию поиска и операцию удаления пары по ключу.

Введение

Существует два основных варианта хеш-таблиц: с цепочками и открытой адресацией. Хеш-таблица содержит некоторый массив [math]H[/math], элементы которого есть пары (хеш-таблица с открытой адресацией) или списки пар (хеш-таблица с цепочками).

Выполнение операции в хеш-таблице начинается с вычисления хеш-функции от ключа. Получающееся хеш-значение [math]i = h(key)[/math] играет роль индекса в массиве [math]H[/math]. Затем, зная индекс, мы можем выполнить требующуюся операцию (добавление, удаление или поиск).

Ситуация, когда для различных ключей получается одинаковое хеш-значение, встречается не так уж и редко, и зависит от хеш-функции. Чем лучше, используемая хеш-функция, тем меньше вероятность возникновения коллизии. При вставке в хеш-таблицу размером 365 ячеек всего лишь 23-х элементов вероятность коллизии превышает 50 % (при равномерном распределении значений хеш-функции)[1]. Способ разрешения коллизий — важная составляющая любой хеш-таблицы.

Полностью избежать коллизий для произвольных данных невозможно в принципе, и хорошая хеш-функция в состоянии только минимизировать их количество. Но, в некоторых специальных случаях их удаётся избежать. Если все ключи элементов известны заранее, либо меняются очень редко, то можно подобрать хеш-функцию, с помощью которой, все ключи будут распределены по хеш-таблице без коллизий. Это хеш-таблицы с прямой адресацией; в них все операции, такие как: поиск, вставка и удаление работают за [math]O(1)[/math].

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

Свойства хеш-таблицы

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

Разрешение коллизий

Открытое хеширование

Разрешение коллизий при помощи цепочек.

Открытое хеширование или хеширование цепочками. Каждая ячейка [math]i[/math] массива [math]H[/math] содержит указатель на начало списка всех элементов, хеш-значение ключа которых равно [math]i[/math], либо указывает на их отсутствие. Коллизии приводят к тому, что появляются списки размером больше одного элемента.

Время, необходимое для вставки в наихудшем случае равно [math]O(1)[/math]. Это операция выполняет быстро, так как считается, что вставляемый элемент отсутствует в таблице, но если потребуется, то перед вставкой мы можем выполнить поиск этого элемента.

Время работы поиска в наихудшем случае пропорционально длине списка, а если все [math]n[/math] ключей хешированы в одну и ту же ячейку (создавая список длиной [math]n[/math]) время поиска будет равно [math]\Theta(n)[/math] плюс время вычисления хеш-функции, что ничуть не лучше, чем использование связного списка для хранения всех [math]n[/math] элементов.

Удаления элемента может быть выполнено за [math]O(1)[/math], как и вставка, при использовании двухсвязного списка.[3]

Закрытое хеширование

Пример хеш-таблицы с открытой адресацией и линейным пробированием.

В случае метода открытой адресации (или по-другому — метод закрытого хеширования) все элементы хранятся непосредственно в хеш-таблице, без использования связных списков. В отличии от хеширования с цепочками, при использовании метода открытой адресации может возникнуть ситуация, когда хеш-таблица окажется полностью заполненной, следовательно будет невозможно добавлять в неё новые элементы. Так что при возникновении такой ситуации решением может быть динамическое увеличение размера хеш-таблицы, с одновременной её перестройкой.

Рассмотрим один из методов борьбы с коллизиями.

Линейное разрешение коллизий

В массиве [math]H[/math] хранятся сами пары ключ-значение. Алгоритм вставки элемента проверяет ячейки массива [math]H[/math] в заданном порядке до тех пор, пока не будет найдена первая свободная ячейка, в неё и будет записан новый элемент. Это позволяет сэкономить память на хранение указателей.

Последовательность, в которой просматриваются ячейки хеш-таблицы, называется последовательностью проб. В общем случае, она зависит только от ключа элемента, то есть это последовательность [math]h_0(x)[/math], [math]h_1(x)[/math], ...,[math]h_n[/math][math]_-[/math][math]_1[/math][math](x)[/math], где [math]x[/math] — ключ элемента, а [math]h_i(x)[/math] — произвольные функции, сопоставляющие каждому ключу ячейку в хеш-таблице. Первый элемент в последовательности, как правило, равен значению некоторой хеш-функции от ключа, а остальные считаются от него каким-нибудь способом. Для успешной работы алгоритмов поиска последовательность проб должна быть такой, чтобы все ячейки хеш-таблицы оказались просмотренными ровно по одному разу.

Алгоритм поиска просматривает ячейки хеш-таблицы в том же порядке, что и при вставке, пока не найдется элемент с искомым ключом, либо свободная ячейка (что означает отсутствие элемента в хеш-таблице).

Удаление элементов в такой схеме несколько затруднено. Можно поступить так: будем помечать каждую учейку по признаку, удалили мы из неё элемент, или нет. В этом случаем, удалением является установка метки — удалён, для соответсвующей ячейки хеш-таблицы, остаётся только модифицировать поиск (если удалён, то занято) и вставку (если удалён, то пусто) элементов.

Примечания

  1. Википедия: Парадокс дней рождений
  2. Перехеширование. Амортизационный анализ
  3. Анализ хеширования с цепочками, вы можете найти в книге Томаса Кормена: «Алгоритмы. Построение и анализ.»

Источники

  • Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. «Алгоритмы. Построение и анализ» — «Вильямс», 2011 г. — 1296 стр. — ISBN 978-5-8459-0857-5, 5-8459-0857-4, 0-07-013151-1
  • Дональд Кнут. «Искусство программирования, том 3. Сортировка и поиск» — «Вильямс», 2007 г. — 824 стр. — ISBN 0-201-89685-0
  • Википедия: Хеширование
  • Википедия: Хеш-таблица