6. Структуры данных, основанные на хеш-таблицах

Существует метод реализации словарей, который называется хешированием.

Формы хеширования:

1)открытое, или внешнее хеширование - позволяет хранить множества в потенциально бесконечном пространстве, снимая тем самым ограничения на размер множеств.

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

Открытое хеширование

Основная идея заключается в том, что потенциальное множество (возможно, бесконечное) разбивается на конечное число классов.

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

Элемент х часто называют ключом, h(x) - хеш-значением х, а "классы" - сегментами. Массив, называемый таблицей сегментов и проиндексированный номерами сегментов 0, 1, ..., В-1, содержит заголовки для В списков. Элемент х i-ro списка - это элемент исходного множества, для которого h(x)=i.

Если сегменты примерно одинаковы по размеру, то в этом случае списки всех сегментов должны быть наиболее короткими при данном числе сегментов. Если исходное множество состоит из N элементов, тогда средняя длина списков будет N/B элементов.

Если можно оценить величину N и выбрать В как можно ближе к этой величине, то в каждом списке будет 1-2 элемента. Тогда время выполнения операторов словарей будет малой постоянной величиной, зависящей от N (или, что эквивалентно, от В).

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

Ниже показан простой сп-б построения фун-и h, причем h(x) – случ-е значение.

Введем хеш-функцию, определенную на символьных строках.

В этой функции суммируются все целочисленные коды символов, результат суммирования делится на В и берется остаток от деления, который будет целым числом из интервала от 0 до В-1.

Закрытое хеширование

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

При закрытом хешировании применяется методика повторного хеширования.

Если мы попытаемся поместить элемент х в сегмент с номером h(x), который уже занят другим элементом (такая ситуация называется коллизией), то в соответствии с методикой повторного хеширования выбирается последовательность других номеров сегментов h1(x), h2(x), ..., куда можно поместить элемент х.

Каждое из этих местоположений последовательно проверяется, пока не будет найдено свободное.

Если свободных сегментов нет, то, следовательно, таблица заполнена и элемент х вставить нельзя.

7. Деревья двоичного поиска. Методы их реализации.

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

Это свойство называется характеристическим свойством дерева двоичного поиска и выполняется для любого узла дерева двоичного поиска, включая его корень.

Отметим интересное свойство деревьев двоичного поиска:

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

Пусть дерево двоичного поиска представляет некоторое множество элементов. Характеристическое свойство дерева двоичного поиска позволяет легко проверить принадлежность любого элемента исходному множеству.

• Для того чтобы определить, принадлежит ли элемент х исходному множеству, сначала сравним его с элементом r, находящимся в корне дерева.

• Если х = r, то вопрос о принадлежности элемента х множеству решен положительно.

• В случае х < r по характеристическому свойству дерева двоичного поиска элемент х может быть потомком только левого сына корня дерева.

• А налогично, если х > r, то элемент х может быть потомком только правого сына корня дерева.

На рисунке показаны два дерева двоичного поиска, представляющие одно и то же множество целых чисел.

Пусть дерево двоичного поиска представляет некоторое множество элементов. Характеристическое свойство дерева двоичного поиска позволяет легко проверить принадлежность любого элемента исходному множеству.

• Для того чтобы определить, принадлежит ли элемент х исходному множеству, сначала сравним его с элементом r, находящимся в корне дерева.

• Если х = r, то вопрос о принадлежности элемента х множеству решен положительно.

• В случае х < r по характеристическому свойству дерева двоичного поиска элемент х может быть потомком только левого сына корня дерева.

Аналогично, если х > r, то элемент х может быть потомком только правого сына корня дерева

Тип данных nodetype узлов дерева, содержащих поле element для элементов множества и два поля leftchild и rightchild указателей на левого и правого сыновей, определен следующим образом:

type nodetype = record

element: elementtype;

leftchild, rightchild: ^nodetype

end;

Тип данных SET (Множество) определен как указатель на узел, который будет корнем дерева двоичного поиска при представлении множества:

type SET: ^nodetype;

function MEMBER ( х: elementtype; A: SET ): boolean;

begin if A = nil then MEMBER:=false { x не может принадлежать  }

else if x = A^.element then MEMBER:= true

else if x < A^.element then MEMBER:=MEMBER(x, A^.leftchild)

else { x > A^.element } MEMBER:=(MEMBER(x, A^.rightchild))

end;