В главе 6 было указано несколько представлений для
множеств, элементами которых являются целые числа произвольной
величины. Однако в любом из них хотя бы одна из операций
проверки принадлежности, добавления и удаления элемента
требовала количества действий, пропорционального числу элементов
множества. На практике это бывает слишком много. Существуют
способы, позволяющие получить для всех трех упомянутых операций
оценку . Один из таких способов мы рассмотрим в
следующей главе. В этой главе мы разберем способ, которые хотя и
приводит к Cn действиям в худшем случае, но зато << в
среднем>> требует значительно меньшего их числа. (Мы не будем
уточнять слов << в среднем>>, хотя это и можно сделать.) Этот
способ называется хешированием.
Пусть нам необходимо представлять множества элементов типа
T, причем число элементов в них заведомо меньше n. Выберем
некоторую функцию h, определенную на значениях типа T и
принимающую значения . Было бы хорошо, чтобы
эта функция принимала на элементах будущего множества по
возможности более разнообразные значения. (Худший случай -- это
когда ее значения на всех элементах хранимого множества
одинаковы.) Эту функцию будем называть хеш-функцией, или,
как еще говорят, функцией расстановки.
Введем два массива
val: array [0..n-1] of T; used: array [0..n-1] of boolean;(мы позволяем себе писать n-1 в качестве границы в определении типа, хотя в паскале это не разрешается). В этих массивах будут храниться элементы множества: оно равно множеству всех
Формально говоря, в любой момент должно соблюдаться такое требование: для любого элемента множества участок справа от его исконного места до его фактического места полностью заполнен.
Благодаря этому проверка принадлежности заданного элемента
t осуществляется легко: встав на h(t), двигаемся
направо, пока не дойдем до пустого места или до элемента t. В
первом случае элемент t отсутствует в множестве, во втором
-- присутствует. Если элемент отсутствует, то его можно добавить
на найденное пустое место. Если присутствует, то можно его
удалить (положив ).
11.1.1. В предыдущем абзаце есть ошибка. Найдите ее и исправьте.
11.1.2. Написать программы проверки принадлежности, добавления и
удаления.
function принадлежит (t: T): boolean; | var i: integer; begin | i := h (t); | while used [i] and (val [i] <> t) do begin | | i := (i + 1) mod n; | end; {not used [i] or (val [i] = t)} | принадлежит := used [i] and (val [i] = t); end;
procedure добавить (t: T); | var i: integer; begin | i := h (t); | while used [i] and (val [i] <> t) do begin | | i := (i + 1) mod n; | end; {not used [i] or (val [i] = t)} | if not used [i] then begin | | used [i] := true; | | val [i] := t; | end; end; procedure исключить (t: T); | var i, gap: integer; begin | i := h (t); | while used [i] and (val [i] <> t) do begin | | i := (i + 1) mod n; | end; {not used [i] or (val [i] = t)} | if used [i] and (val [i] = t) then begin | | used [i] := false; | | gap := i; | | i := (i + 1) mod n; | | {gap - дыра, которая может закрыться одним из i,i+1,...} | | while used [i] do begin | | | if i = h (val[i]) then begin {на своем месте} | | | | i := (i + 1) mod n; | | | end else if dist(h(val[i]),i) < dist(gap,i) then begin | | | | {gap...h(val[i])...i} | | | | i := (i + 1) mod n; | | | end else begin | | | | used [gap] := true; | | | | val [gap] := val [i]; | | | | used [i] := false; | | | | gap := i; | | | | i := (i + 1) mod n; | | | end; | | end; | end; end;
Здесь -- измеренное по часовой стрелке (слева
направо) расстояние от a до b, то есть
(Мы прибавили n, так как функция mod правильно работает
при положительном делимом.)
11.1.3. Существует много вариантов хеширования. Один из них таков:
обнаружив, что исконное место (обозначим его i ) занято, будем
искать свободное не среди
, а среди
, где r -- некоторое отображение
в себя. Какие при этом будут трудности?
11.1.4. Пусть для хранения множества всех правильных русских слов в
программе проверки
орфографии используется хеширование. Что нужно
добавить, чтобы к тому же уметь находить английский перевод
любого правильного слова?