Разрешение коллизий с помощью цепочек

Технология сцепления элементов (chaining) состоит в том, что элемент множества, которым соответствует одно и то же хеш-значение, связывают в цепочку-список. В позиции номер j хранится указатель на голову списка тех элементов, у которых хеш-значение ключа равно j если таких элементов в множестве нет, в позиции j записан NIL. Операции добавления, поиска и удаления реализуются легко:

Рисунок 4.4 – Использование цепочек для разрешения коллизий

Листинг 4.2 – Словарные операции при хешировании с цепочками

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

const

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

type

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

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

procedure Clear_ChainedHashTable (var A: ChainedHashTable);

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

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_ChainedHashTable(x: TypeData;

var A: ChainedHashTable;

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_ChainedHashTable := true

else

Find_ChainedHashTable := false;

end;

procedure Add_ChainedHashTable(x: TypeData; var A: ChainedHashTable);

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

var

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

current: PElement;

begin

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

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

IndexSeg := h(x);

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

InsFirst_LineSingleList(x, A[IndexSeg]);

end

end;

procedure Del_ChainedHashTable(x: TypeData; var A: ChainedHashTable);

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

var

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

current: PElement;

begin

if Find_ChainedHashTable(x, A, current) then begin

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

IndexSeg := h(x);

Del_LineSingleList(A[IndexSeg], current);

end

end;

Листинг 4.3 – Словарные операции при хешировании с цепочками

Операция добавления работает в худшем случае за время О(1). Максималь­ное время работы операции поиска пропорционально длине списка (ниже мы рассмотрим этот вопрос подробнее). Наконец, удаление элемента можно прове­сти за время О(1) – при условии, что списки двусторонне связаны (если списки связаны односторонне, то для удаления элемента х надо предварительно найти его предшественника, для чего необходим поиск по списку; в таком случае стоимость удаления и поиска примерно одинаковы).