Хеш-таблица

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 16:57, 17 января 2019.

Введение

TemplateDifinitionIcon.svg Определение «Хеш-таблица»

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

Изначально дано множество из ключей и хеш-функция, которая отображает множество ключей в множество хешей. Выполнение операции в хеш-таблице начинается с вычисления хеш-функции от ключа. Вычисленное значение играет роль индекса в массиве, которым фактически и является хеш-таблица. Естественной проблемой хеш-таблиц является неинъективность хеш-функции, что ведет к возникновению коллизий(см. Рисунок 1).

TemplateDifinitionIcon.svg Определение «Коллизия»

Коллизией назовем ситуацию, при которой значения хеш-функции на двух или более различных ключах совпадают

Таким образом, мы сталкиваемся с проблемой, так как в одной ячейке массива не может храниться более 1 элемента. Проблема коллизий является основной проблемой в реализации данной структуры данных, вопросы связанные с этой проблемой будут затронуты дальше, пока что предлагаем ознакомиться с примером хеш-таблицы:

TemplateExampleIcon.svg Пример Пример 1- хеш-таблица

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

  1. Мы видим, что при попытке добавить последний элемент в хеш-таблицу произошла коллизия.
Рисунок 1 - коллизия в хеш-таблице

Вероятности коллизии

Пусть имеется хеш-таблица длины , в которую последовательно добавляется элементов, оценим вероятность возникновения коллизии.[Источник 1] Оценим вероятность того, что 2 первых элемента при добавлении будут обладать разными индексами, то есть того, что при этом добавлении не произошло ошибок, она равна: . Нетрудно обобщить и понять, что после добавления i-ого элемента вероятность того, что не произошло коллизии непосредственно при его добавлении, при условии что до его добавления их не было, равна . Итого вероятность того, что не произошло ни одной коллизии при добавлении всех элементов равна . Это легко обобщается до следующего вида . Тогда вероятность того, что все-таки произошла хотя бы одна коллизия будет равна разнице единицы и вычисленной вероятности: .

TemplateExampleIcon.svg Пример Пример 2- вероятность коллизий для примера 1

Посчитаем вероятность возникновения коллизии в примере 1: .

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

С коллизиями можно и нужно бороться. Существует несколько способов разрешения коллизий:[Источник 2]

Метод цепочек

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

Рисунок 2 - Разрешение коллизий при помощи цепочек

Для подсчета вычислительной сложности основных операций взаимодействия с хеш-таблицей введем следующее определение.

TemplateDifinitionIcon.svg Определение «Коэффициент заполнения таблицы»

Коэффициентом заполнения таблицы называется отношения числа занятых индексов в таблице к ее длине . .

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

Открытая адресация

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

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

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

Рисунок 3 - Пример хеш-таблицы с открытой адресацией

Основные типы последовательностей проб

Ниже приведены некоторые распространенные типы последовательностей проб.[Источник 3]

Линейное пробирование

TemplateDifinitionIcon.svg Определение «Линейное пробирование»

Линейным пробированием называется метод разрешения коллизий в хеш-таблице с открытой адресацией, при котором i-ый элемент последовательности проб это , где - размер таблицы, - некоторая фиксированная константа.

TemplateStatementIcon.svg Утверждение Об ограничениях на

должно выбираться таким образом, чтобы быть взаимно простым с . Докажем это утверждение:

  1. Пусть , тогда является порождающим элементом в циклической группе и при первых коллизиях числа все будут различными.
  2. Таким образом, если эти совпадения могли произойти только в том случае, если разница между и по модулю не меньше чем .
  3. В итоге, последовательность проб зациклится только при идущих подряд n-1 коллизиях, что само по себе уже является неразрешимой, в рамках данной таблицы, ситуацией.
TemplateExampleIcon.svg Пример Пример 3- линейное пробирование

Пусть дано следующее множество ключей: . Пусть хеш-функция представляется в виде: . Заполним нашу хеш-таблицу H.

  1. новая ячейка для 20 будет вычислена следующим образом: .

Поиск элемента в таблице осуществляется аналогично добавлению: мы проверяем ячейку i и другие, в соответствии с выбранной стратегией, пока не найдём искомый элемент или свободную ячейку. Аналогично реализовано удаление.

Квадратичное пробирование

TemplateDifinitionIcon.svg Определение «Квадратичное пробирование»

Квадратичным пробированием называется метод разрешения коллизий в хеш-таблице с открытой адресацией, при котором i-ый элемент последовательности проб это , где - размер таблицы, - некоторая фиксированная константа.

Выполнение всех основных операции в хеш-таблице с квадратичной последовательностью проб совпадает с их реализацией при линейном пробировании.

Двойное хеширование

TemplateDifinitionIcon.svg Определение «Двойное хеширование»

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

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

Заключение

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

Источники

  1. Хеш-таблица // Викиконспекты. Дата обновления: 10.03.2018 URL: https://neerc.ifmo.ru/wiki/index.php?title=Хеш-таблица (дата обращения: 25.12.2018).
  2. Разрешение коллизий // Викиконспекты. Дата обновления: 11.06.2018 URL: https://neerc.ifmo.ru/wiki/index.php?title=Разрешение_коллизий (дата обращения: 25.12.2018).
  3. Хеш-таблица // Википедия [2018-2018]. Дата обновления: 17.02.2018 URL:https://ru.wikipedia.org/wiki/Хеш-таблица (дата обращения: 25.12.2018).