Лекция 19. Перемешанные таблицы

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

Позволим данным располагаться в любых элементах массива, а не только в первых n. Чтобы отличать пустые элементы от занятых нам понадобится специальное значение ключа, которое мы будем заносить в ключевое поле всех пустых ячеек. Если ключ — число, а все полезные ключи положительны, то можно в качестве ключа пустой ячейки использовать 0, если ключи — строки, содержащие фамилии, то ключом пустой ячейки можно сделать пустую строку и т. п. Пусть в ключами являются строки, тогда для таблицы потребуются такие объявления:

const empty = '';

nmax = 1000;

type tKey = string;

tData =.....;

tItem = record

           key: tKey;

           data: tData;

         end;

tTable = array [0..nmax-1] of tItem;

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

Реализованная описанным способом таблица называется перемешанной (или hash-таблицей), а функция — функцией расстановки ключей (hash-функцией). Такие названия связаны с тем, что данные беспорядочно разбросаны по массиву.

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

function hash(key: tKey): integer;

var i: integer;

Begin

sum:=0;

for i:=1 to length(key) do sum:=sum+ord(key[i]);

hash:= sum mod nmax;

end;

Процедура добавления элемента в таблицу в предварительном варианте будет выглядеть так:

procedure AddItem(var t: tTable; item: tItem);

var h: integer;

Begin

h:=hash(item.key);

t[h]:=item.key;

end;

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

Наиболее простая хэш-функция будет добавлять к номеру занятой ячейки какое-нибудь постоянное число:

const HC = 7;

 

function hash2(n: integer, key: tKey): integer;

Begin

hash2:= (n + HC) mod nmax;

end;

Остаток от деления на nmax понадобилось вычислять по той же причине, что и в первичной хэш-функции.

Сейчас можно написать окончательный вариант процедуры добавления элемента данных в таблицу:

procedure AddItem(var t: tTable; item: tItem);

var h: integer;

Begin

h:=hash(item.key);

while t[h].key<>empty do h:=hash2(h,item.key);

t[h].key:=item.key;

t[h].data:=item.data;

end;

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

const notfound = -1;

continue = -2;

procedure Search(var t: tTable; key: tKey; var index: integer);

var h: integer;

Begin

h:=hash(key);

index:=continue;

Repeat

if t[h].key = key then index:=h

else if t[h].key = empty then index:= notfound

else h:=hash2(h,key);

until index<>сontinue;

end;

Процедура выдаёт ответ о результатах поиска через параметр-переменную index. При удачном поиске там будет лежать номер найденного элемента, при неудачном — константа notfound. Константа continue означает «пока не найден» и используется только внутри процедуры. При поиске сначала вычисляется значение первичной хэш-функции, а в index заносится значение continue Затем выполняется проверка на равенство ключей, если оно выполняется, то ячейка массива найдена, и мы записываем её номер в index, иначе, если ячейка пуста, то элемент не найден (в index записываем notfound), в третьем случае находим значение вторичной функции. Эти действия продолжаются до тех пор, пока index не перестанет быть равным continue.