Хеш-таблица — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 30 промежуточных версий 7 участников)
Строка 1: Строка 1:
−
{{Определение  
+
{{Определение
−
|definition=
+
|definition='''Хеш-табли́ца''' (англ. ''hash-table'') {{---}} структура данных, реализующая интерфейс ассоциативного массива. В отличие от [[Дерево_поиска,_наивная_реализация|деревьев поиска]], реализующих тот же интерфейс, обеспечивают меньшее время отклика в среднем. Представляет собой эффективную структуру данных для реализации словарей, а именно, она позволяет хранить пары (ключ, значение) и выполнять три операции: операцию добавления новой пары, операцию поиска и операцию удаления пары по ключу.
−
'''Хеш-табли́ца''' (англ. ''hash-table'') {{---}} структура данных, реализующая интерфейс ассоциативного массива. В отличие от деревьев поиска, реализующих тот же интерфейс, обеспечивают меньшее время отклика в среднем. Представляет собой эффективную структуру данных для реализации словарей, а именно, она позволяет хранить пары (ключ, значение) и выполнять три операции: операцию добавления новой пары, операцию поиска и операцию удаления пары по ключу.
 
 
}}
 
}}
  
 
=== Введение ===
 
=== Введение ===
−
Существует два основных вида хеш-таблиц: ''с цепочками'' и ''открытой адресацией''. Хеш-таблица содержит некоторый массив <tex>H</tex>, элементы которого есть пары (хеш-таблица с открытой адресацией) или списки пар (хеш-таблица с цепочками).
+
Существует два основных вида хеш-таблиц: [[Разрешение_коллизий#Разрешение коллизий с помощью цепочек|''с цепочками'']] и [[Разрешение_коллизий#Линейное разрешение коллизий|''открытой адресацией'']]. Хеш-таблица содержит некоторый массив <tex>H</tex>, элементы которого есть пары (хеш-таблица с открытой адресацией) или списки пар (хеш-таблица с цепочками).
  
 
Выполнение операции в хеш-таблице начинается с вычисления хеш-функции от ключа. Хеш-код <tex>i = h(key)</tex> играет роль индекса в массиве <tex>H</tex>, а зная индекс, мы можем выполнить требующуюся операцию (добавление, удаление или поиск).
 
Выполнение операции в хеш-таблице начинается с вычисления хеш-функции от ключа. Хеш-код <tex>i = h(key)</tex> играет роль индекса в массиве <tex>H</tex>, а зная индекс, мы можем выполнить требующуюся операцию (добавление, удаление или поиск).
  
−
Количество коллизий зависит от хеш-функции; чем лучше используемая хеш-функция, тем меньше вероятность их возникновения. При вставке в хеш-таблицу вероятность коллизии в общем случае превышает <tex>50%</tex><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>. Способ разрешения коллизий — важная составляющая любой хеш-таблицы.
+
|statement=Вероятность коллизий при вставке в хеш-таблицу превышает 50%
 +
|proof=
 +
 
 +
Пусть хеш-таблица имеет размер <tex>len</tex> и в нее добавляют <tex>n</tex> элементов. Рассмотрим <tex>{p}'(n)</tex> — вероятность того, что не возникнет ни одной коллизии. Добавим два любых элемента в нашу хеш-таблицу. Вероятность того, что они не попадут в одну и ту же ячейку таблицы равна <tex>1 - \dfrac{1}{len}</tex>. Возьмем еще один элемент. Тогда вероятность того, что третий элемент не попадет в одну из уже занятых ячеек равна <tex>1 - \dfrac{2}{len}</tex>. Рассуждая аналогичным образом, получим формулу:
 +
<tex>{p}'(n) = \left( 1 - \dfrac{1}{len}\right )\cdot \left( 1 - \dfrac{2}{len}\right )\dots\left( 1 - \dfrac{n - 1}{len}\right ) = \dfrac{len \cdot \left(len - 1 \right )\dots\left (len - n + 1 \right )}{len^{n}} = \dfrac{len!}{len^{n} \cdot \left (len - n \right)!}</tex>
 +
 
 +
Тогда <tex>{p}(n)</tex> — вероятность возникновения коллизии равна:
 +
<tex>p(n) = 1 - {p}'(n)</tex>,
 +
что в общем случае <tex> > \dfrac{1}{2}</tex>
 +
}}
 +
 
 +
Способ разрешения коллизий — важная составляющая любой хеш-таблицы.
  
 
Полностью избежать коллизий для произвольных данных невозможно в принципе, и хорошая хеш-функция в состоянии только минимизировать их количество. Но, в некоторых специальных случаях их удаётся избежать. Если все ключи элементов известны заранее, либо меняются очень редко, то можно подобрать хеш-функцию, с помощью которой, все ключи будут распределены по хеш-таблице без коллизий. Это хеш-таблицы с ''прямой адресацией''; в них все операции, такие как: поиск, вставка и удаление работают за <tex>O(1)</tex>.
 
Полностью избежать коллизий для произвольных данных невозможно в принципе, и хорошая хеш-функция в состоянии только минимизировать их количество. Но, в некоторых специальных случаях их удаётся избежать. Если все ключи элементов известны заранее, либо меняются очень редко, то можно подобрать хеш-функцию, с помощью которой, все ключи будут распределены по хеш-таблице без коллизий. Это хеш-таблицы с ''прямой адресацией''; в них все операции, такие как: поиск, вставка и удаление работают за <tex>O(1)</tex>.
Строка 18: Строка 28:
  
 
=== Хеширование ===
 
=== Хеширование ===
−
{{Определение
+
'''Хеширование''' (англ. ''hashing'') {{---}} класс методов поиска, идея которого состоит в вычислении хеш-кода, однозначно определяемого элементом с помощью хеш-функции, и использовании его, как основы для поиска (индексирование в памяти по хеш-коду выполняется за <tex>O(1)</tex>). В общем случае, однозначного соответствия между исходными данными и хеш-кодом нет в силу того, что количество значений хеш-функций меньше, чем вариантов исходных данных, поэтому существуют элементы, имеющие одинаковые хеш-коды — так называемые коллизии, но если два элемента имеют разный хеш-код, то они гарантированно  
−
|definition=
+
различаются. Вероятность возникновения коллизий играет немаловажную роль в оценке качества хеш-функций. Для того чтобы коллизии не замедляли работу с таблицей существуют [[Разрешение коллизий|методы для борьбы с ними]].
−
'''Хеширование''' {{---}} класс методов поиска, идея которого состоит в вычислении хеш-кода, однозначно определяемого элементом с помощью хеш-функции, и использовании его, как основы для поиска (индексирование в памяти по хеш-коду выполняется за <tex>O(1)</tex>). В общем случае, однозначного соответствия между исходными данными и хеш-кодом нет в силу того, что количество значений хеш-функций меньше, чем вариантов исходных данных, поэтому существуют элементы, имеющие одинаковые хеш-коды — так называемые коллизии, но если два элемента имеют разный хеш-код, то они гарантированно  
 
−
различаются. Вероятность возникновения коллизий играет немаловажную роль в оценке качества хеш-функций. Для того чтобы коллизии не замедляли работу с таблицой существуют [[Разрешение коллизий|методы для борьбы с ними]].
 
−
}}
 
  
 
{{Определение
 
{{Определение
 
|id=def1
 
|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> '''Коллизия:''' <tex>\exists x \neq y : h(x) = h(y)</tex>
+
|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>\Theta(n)</tex>, но на практике хеширование более эффективно. При некоторых разумных допущениях [[Математическое_ожидание_случайной_величины|математическое ожидание]] времени поиска элемента в хеш-таблице составляет <tex>O(1)</tex>. А все операции (поиск, вставка и удаление элементов) в среднем выполняются за время <tex>O(1)</tex>.
 
При этом не гарантируется, что время выполнения отдельной операции мало́, так как при достижении некоторого значения коэффициента заполнения необходимо [[Перехеширование. Амортизационный анализ|перехешировать]] таблицу: увеличить размер массива <tex>H</tex> и заново добавить в новую хеш-таблицу все пары.
 
При этом не гарантируется, что время выполнения отдельной операции мало́, так как при достижении некоторого значения коэффициента заполнения необходимо [[Перехеширование. Амортизационный анализ|перехешировать]] таблицу: увеличить размер массива <tex>H</tex> и заново добавить в новую хеш-таблицу все пары.
  
Строка 45: Строка 54:
 
Почти во всех современных языках присутствуют классы, реализующие хеширование. Рассмотрим некоторые из них.
 
Почти во всех современных языках присутствуют классы, реализующие хеширование. Рассмотрим некоторые из них.
 
*Java
 
*Java
−
**HashMap {{---}} реализация интерфейса ассоциативного массива с использованием хеш-таблицы,
+
**HashMap  <ref>[http://docs.oracle.com/javase/7/docs/api/java/util/HashMap.html HashMap {{---}} Java Platform SE 7]</ref> {{---}} реализация интерфейса ассоциативного массива с использованием хеш-таблицы,
−
**HashSet {{---}} реализация интерфейса множества с использованием хеш-таблицы,
+
**HashSet <ref>[http://docs.oracle.com/javase/7/docs/api/java/util/HashSet.html HashSet {{---}} Java Platform SE 7]</ref>  {{---}} реализация интерфейса множества с использованием хеш-таблицы,
−
**LinkedHashMap {{---}} потомок класса HashMap. Позволяет просматривать значения в том порядке, в котором они были добавлены.
+
**LinkedHashMap <ref>[http://docs.oracle.com/javase/7/docs/api/java/util/LinkedHashMap.html LinkedHashMap {{---}} Java Platform SE 7]</ref> {{---}} потомок класса HashMap. Позволяет просматривать значения в том порядке, в котором они были добавлены.
 
*C++
 
*C++
−
**hash_map {{---}} реализация интерфейса ассоциативного массива с использованием хеш-таблицы,
+
**unordered_map <ref>[http://www.cplusplus.com/reference/unordered_map/unordered_map/ unordered_map {{---}} cplusplus.com]</ref> {{---}} реализация интерфейса ассоциативного массива с использованием хеш-таблицы,
−
**hash_set {{---}} реализация интерфейса множества с использованием хеш-таблицы.
+
**unordered_set  <ref>[http://www.cplusplus.com/reference/unordered_map/unordered_set/ unordered_set {{---}} cplusplus.com]</ref>  {{---}} реализация интерфейса множества с использованием хеш-таблицы.
 +
*Python (CPython)
 +
**dict <ref>[https://github.com/python/cpython/blob/main/Objects/dictobject.c#L1 dictobject.c {{---}} https://github.com/python/cpython]</ref> {{---}} реализация интерфейса ассоциативного массива с использованием хеш-таблицы,
 +
**set <ref>[https://hg.python.org/releasing/3.6/file/tip/Objects/setobject.c setobject.c {{---}} https://hg.python.org ] </ref> {{---}} реализация интерфейса множества с использованием хеш-таблицы.
  
 
== Примечания ==
 
== Примечания ==
Строка 58: Строка 70:
 
* Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. «Алгоритмы. Построение и анализ» {{---}} «Вильямс», 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/Хеш-таблица Википедия {{---}} Хеш-таблица]
  
 
[[Категория:Дискретная математика и алгоритмы]]
 
[[Категория:Дискретная математика и алгоритмы]]
 
[[Категория:Хеширование]]
 
[[Категория:Хеширование]]
 +
[[Категория:Структуры данных]]

Текущая версия на 19:42, 4 сентября 2022

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


Введение

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

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

Количество коллизий зависит от хеш-функции; чем лучше используемая хеш-функция, тем меньше вероятность их возникновения.

Лемма:
Вероятность коллизий при вставке в хеш-таблицу превышает 50%
Доказательство:
[math]\triangleright[/math]

Пусть хеш-таблица имеет размер [math]len[/math] и в нее добавляют [math]n[/math] элементов. Рассмотрим [math]{p}'(n)[/math] — вероятность того, что не возникнет ни одной коллизии. Добавим два любых элемента в нашу хеш-таблицу. Вероятность того, что они не попадут в одну и ту же ячейку таблицы равна [math]1 - \dfrac{1}{len}[/math]. Возьмем еще один элемент. Тогда вероятность того, что третий элемент не попадет в одну из уже занятых ячеек равна [math]1 - \dfrac{2}{len}[/math]. Рассуждая аналогичным образом, получим формулу: [math]{p}'(n) = \left( 1 - \dfrac{1}{len}\right )\cdot \left( 1 - \dfrac{2}{len}\right )\dots\left( 1 - \dfrac{n - 1}{len}\right ) = \dfrac{len \cdot \left(len - 1 \right )\dots\left (len - n + 1 \right )}{len^{n}} = \dfrac{len!}{len^{n} \cdot \left (len - n \right)!}[/math]

Тогда [math]{p}(n)[/math] — вероятность возникновения коллизии равна: [math]p(n) = 1 - {p}'(n)[/math],

что в общем случае [math] \gt \dfrac{1}{2}[/math]
[math]\triangleleft[/math]

Способ разрешения коллизий — важная составляющая любой хеш-таблицы.

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

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

Хеширование

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


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

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

  • По способу хранения:

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

Динамическое — добавляем, удаляем и смотрим на наличие нужных элементов.

  • По виду хеш-функции:

Детерминированная хеш-функция,

Случайная хеш-функция.

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

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

Хеширование в современных языках программирования

Почти во всех современных языках присутствуют классы, реализующие хеширование. Рассмотрим некоторые из них.

  • Java
    • HashMap [1] — реализация интерфейса ассоциативного массива с использованием хеш-таблицы,
    • HashSet [2] — реализация интерфейса множества с использованием хеш-таблицы,
    • LinkedHashMap [3] — потомок класса HashMap. Позволяет просматривать значения в том порядке, в котором они были добавлены.
  • C++
    • unordered_map [4] — реализация интерфейса ассоциативного массива с использованием хеш-таблицы,
    • unordered_set [5] — реализация интерфейса множества с использованием хеш-таблицы.
  • Python (CPython)
    • dict [6] — реализация интерфейса ассоциативного массива с использованием хеш-таблицы,
    • set [7] — реализация интерфейса множества с использованием хеш-таблицы.

Примечания

  1. ↑ HashMap — Java Platform SE 7
  2. ↑ HashSet — Java Platform SE 7
  3. ↑ LinkedHashMap — Java Platform SE 7
  4. ↑ unordered_map — cplusplus.com
  5. ↑ unordered_set — cplusplus.com
  6. ↑ dictobject.c — https://github.com/python/cpython
  7. ↑ setobject.c — https://hg.python.org

Источники информации

  • Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. «Алгоритмы. Построение и анализ» — «Вильямс», 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://neerc.ifmo.ru/wiki/index.php?title=Хеш-таблица&oldid=85846»