Хеш-таблица

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


Содержание

[править] Введение

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

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

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

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

Пусть хеш-таблица имеет размер len и в нее добавляют n элементов. Рассмотрим {p}'(n) — вероятность того, что не возникнет ни одной коллизии. Добавим два любых элемента в нашу хеш-таблицу. Вероятность того, что они не попадут в одну и ту же ячейку таблицы равна 1 - \dfrac{1}{len}. Возьмем еще один элемент. Тогда вероятность того, что третий элемент не попадет в одну из уже занятых ячеек равна 1 - \dfrac{2}{len}. Рассуждая аналогичным образом, получим формулу: {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)!}

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

что в общем случае > \dfrac{1}{2}
\triangleleft

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

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

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

[править] Хеширование

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


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

[править] Виды хеширования

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

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

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

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

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

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

[править] Свойства хеш-таблицы

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

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

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

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

[править] Примечания

  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

[править] Источники информации

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