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

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

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

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

Рисунок 28. Организация данных при открытом хешировании

Рассмотрим алгоритмы основных операций с хеш-таблицей, при открытом хешировании. В этих алгоритмах будем использовать структуры данных и операции с линейными однонаправленными списками, которые были описаны в п. 2.2.6.1. Поле Data в элементах списка будет здесь исполнять роль ключа, а роль указателя на список ptrHead будет играть элемент хеш-таблицы.

const

В = {подходящая константа};

type

HTableOpen = array[0..B-1] of PElement;

Кроме того, здесь используется предопределенная функция h(x), которая и является собственно реализацией хеш-функции.

procedure Clear_HTableOpen(var A: HTableOpen);

{Процедура очистки хеш-таблицы}

var

IndexSeg: integer;

begin

for IndexSeg:=0 to B-1 do

while A[IndexSeg] <> nil do

Del_LineSingleList(A[IndexSeg], A[IndexSeg]);

end;

function Find_HTableOpen(x: TypeData;

var A: HtableOpen;

var current: PElement): boolean;

{функция поиска элемента x в хеш-таблице. Принимает значение true, если найден и возвращает указатель, который устанавливается на найденный элемент, или принимает значение false и возвращает nil}

var

IndexSeg: integer; {номер сегмента}

begin

IndexSeg := h(x);

{начало списка, в котором надо искать, это A[IndexSeg]}

if Find_LineSingleList(x, A[IndexSeg], current) then

Find_HTableOpen := true

else

Find_HTableOpen := false;

end;

procedure Add_HTableOpen(x: TypeData; var A: HTableOpen);

{Процедура добавления элемента x в хеш-таблицу}

var

IndexSeg: integer; {номер сегмента}

current: PElement;

begin

if not Find_HTableOpen(x, A, current) then begin

{Если в таблице элемент уже есть, то добавлять не надо}

IndexSeg := h(x);

{Добавляем всегда в начало списка}

InsFirst_LineSingleList(x, A[IndexSeg]);

end

end;

procedure Del_HTableOpen(x: TypeData; var A: HTableOpen);

{Процедура удаления элемента x из хеш-таблицы}

var

IndexSeg: integer; {номер сегмента}

current: PElement;

begin

if Find_HTableOpen(x, A, current) then begin

{Если в таблице элемент еще есть, то удаляем}

IndexSeg := h(x);

Del_LineSingleList(A[IndexSeg], current);

end

end;

Если есть B сегментов и N элементов, хранящихся в хеш-таблице, то каждый сегмент в среднем будет иметь N/B элементов и можно ожидать, что операции добавления, поиска и удаления будут выполняться в среднем за время, пропорциональное О(1+N/B). Здесь константа 1 соответствует поиску сегмента, а N/B — поиску элемента в сегменте. Если B примерно равно N, то время выполнения операторов становится константой, независящей от N.