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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Хеширование)
Строка 1: Строка 1:
'''Хеш-табли́ца''' {{---}} структура данных, реализующая интерфейс ассоциативного массива. Представляет собой эффективную структуру данных для реализации словарей, а именно, она позволяет хранить пары (ключ, значение) и выполнять три операции: операцию добавления новой пары, операцию поиска и операцию удаления пары по ключу.
+
'''Хеш-табли́ца''' (англ. ''hash-table'') {{---}} структура данных, реализующая интерфейс ассоциативного массива. Представляет собой эффективную структуру данных для реализации словарей, а именно, она позволяет хранить пары (ключ, значение) и выполнять три операции: операцию добавления новой пары, операцию поиска и операцию удаления пары по ключу.
  
 
=== Введение ===
 
=== Введение ===

Версия 20:20, 4 июня 2015

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

Введение

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

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

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

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

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

Хеширование

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

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

Примечания

  1. [math]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 } [/math] [math] = { len! \over len^n \cdot (len-n)!},[/math]
    где [math]n[/math] — количество элементов в хеш-таблице, а [math]len[/math] — её размер.
  2. Парадокс дней рождения — Википедия

Источники

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