Фундаментальные структуры данных. Хэш-таблицы. Пространственно-временной компромисс, страница 2

Заметим, что такой способ разрешения коллизий работает даже тогда, когда коэффициент заполнения превысит 1. Вместо списков для разрешения коллизий можно использовать деревья. Две другие важные операции – вставка и удаление – практически идентичны поиску. Следовательно, эффективность этих операций равна эффективности поиска Θ(1), если мало коллизий.

Хеш-таблицы

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

Хеш-таблицы

• Наиболее распространенными схемами открытой адресации являются:
• Линейная открытая адресация. В случае коллизии ячейки проверяются одна за другой. i = (Х(ключ) + с*j) % N, где с – константа. В то время как операции поиска и вставки весьма просты, этого нельзя сказать об удалении. Простейшим решением проблемы является «отложенное удаление», т.е. ранее занятая ячейка помечается специальным образом, чтобы можно было отличить ее от ячеек, которые никогда не были заняты.

Хеш-таблицы

Математический анализ линейного исследования – существенно более сложная задача, чем анализ хеширования с раздельными цепочками. Упрощенная версия полученных при таком анализе результатов гласит, что среднее количество обращений к хеш-таблице с коэффициентом заполнения ά в случае успешного и неудачного поиска равно соответственно S ≈ ½ (1+1/(1-ά)) и U ≈ ½ (1+1/(1-ά)²). По мере заполнения хеш-таблицы производительность линейного исследования ухудшается из-за эффекта кластеризации.

Хеш-таблицы

• Квадратичная открытая адресация. i = (Х(ключ) + с*j² + d*j, где с и d – константы.
• Открытая адресация с двойным хешированием. По этой схеме i = Х(ключ) + j*h(ключ). Например, если Х(ключ) = ключ % N, то h(ключ) = 1 + ключ % (N-2).

B-деревья

Идея использования дополнительной памяти для ускорения доступа к данным особенно важна, если рассматриваемый набор данных содержит большое количество записей, которые требуется хранить на диске. Основной метод организации таких наборов данных – индексы, которые представляют определенную информацию о размещении записей с указанными значениями ключей. Для наборов данных, состоящих из структурированных записей наиболее важной организацией индексов являются B-деревья, разработанные Р. Бойером и Э. Мак-Грейтом. Они расширяют идею 2-3-деревьев.

B-деревья

• В В-деревьях все данные хранятся в листьях, в возрастающем порядке ключей, а родительские узлы используются для индексирования. В частности, каждый родительский узел содержит n-1 упорядоченных ключей К1<…<Kn-1 (которые для простоты полагаем различными). Ключи разделены n указателями на дочерние узлы, так что все ключи в поддереве Ti , больше Кi и меньше Ki+1. Кроме того, В-дерево порядка m≥2 должно удовлетворять следующим свойствам:
• Корень либо является листом, либо имеет от 2 до m потомков.

B-деревья

• Каждый узел, за исключением корня и листьев, имеет от [m/2] до m потомков (и следовательно, от [m/2]-1 до m-1 ключей).
• Дерево идеально сбалансировано, т.е. все листья находятся на одном и том же уровне.
• Поиск в В-дереве является операцией, принадлежащей классу эффективности Ο(log2n). Наиболее простой алгоритм вставки новой записи в В-дерево очень похож на алгоритм вставки в 2-3-дерево. Сначала мы используем процедуру поиска нового ключа К, для того чтобы найти лист для его вставки.

B-деревья

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

B-деревья

Существуют и другие алгоритмы для реализации вставки информации в В-дерево. Например, мы можем избежать возможного рекурсивного разделения заполненных узлов, если будем разделять при поиске листа для новой записи. Еще одна возможность избежать рекурсивного разделения заполненных узлов заключается в перемещении ключа в «братский» узел.

Спасибо за внимание