Главная Промышленная автоматика.

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

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

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

На рис. 4.3 показана базовая структура данных при открытом хешировании. Основная идея заключается в том, что потенциальное множество (возможно, бесконечное) разбивается на конечное число классов. Для В классов, пронумерованных от О до 5 - 1, строится хеш-функция h такая, что для любого элемента х исходного множества функция A(jc) принимает целочисленное значение из интервала О, 5-1, которое, естественно, соответствует классу, которому принадлежит элемент х. Элемент X часто называют ключом, h(x) - хеш-значением х, а "классы" - сегментами. Мы будем говорить, что элемент х принадлежит сегменту h(x).

Список элементов каждого сегмента

Заголовки таблицы сегментов

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

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

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

Есть несколько классификаций методов хеширования по разным признакам. Мы оставляем здесь классификацию (и терминологию) авторов, поскольку она проста и непротиворечива. Отметим только, что открытое хеширование, как оно изложено далее, является частным случаем так называемого расширенного хеширования, а закрытое хеширование часто называют прямъии хешированием. - Прим. ред.

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



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

Здесь же мы введем хеш-функцию (которая будет "хорошей", но не "отличной"), оиределенную на символьных строках. Идея построения этой функции заключается в том, чтобы представить символы в виде целых чисел, используя для этого машинные коды символов. В языке Pascal есть встроенная функция ord(c), которая возврашает целочисленный код символа с. Таким образом, если х - это ключ, тип данных ключей определен как аггау[1..101 of char (в примере 4.2 этот тип данных назван nametype), тогда можно использовать хеш-функцию, код которой иредставлен в листинге 4.7. В этой функции суммируются все целочисленные коды символов, результат суммирования делится на В и берется остаток от деления, который будет целым числом из интервала от О до 5 - 1.

Листинг 4.7. Простая хеш-функция

function h ( х: nametype ): О..В-l; var

i, sum: integer; begin

sum:= 0;

for i:= 1 to 10 do

sum:= sum + ord(x[i]) ; h: = sum mod В end; { h }

В листинге 4.8 показаны объявления структур данных для открытой хеш-таблицы и процедуры, реализующие операторы, выполняемые над словарем. Тип данных элементов словаря - nametype (здесь - символьный массив), поэтому данные объявления можно непосредственно использовать в примере 4.2. Отметим, что в листинге 4.8 заголовки списков сегментов сделаны указателями на ячейки, а не "настояшими" ячейками. Это сделано для экономии пространства, занимаемого данными: если заголовки таблицы сегментов будут ячейками массива, а не указателями, то иод этот массив необходимо столько же места, сколько и иод списки элементов. Но за такую экономию пространства надо платить: код процедуры DELETE должен уметь отличать первую ячейку от остальных.

Листинг 4.8. Реализация словарей посредством открытой хеш-таблицы

const

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

type

celltype = record

element: nametype,-next: Tcelltype

end;

DICTIONARY = arraytO..B-1] of Tcelltype;

procedure MAKENULL { var A: DICTIONARY ); var

i:= integer;

begin

for i:= 0 to В - 1 do

A[i]:= nil end; j MAKENULL j



function MEMBER { x: nametype; var A: DICTIONi\RY ) : boolean; var

current: tcelltype;

begin

current:= Alh{x)];

{ начальное значение current равно заголовку сегмента,

которому принадлежит элемент х } while current о nil do

if currentT.element = x then return (true)

else

current: currentT.next; return(false) { элемент x не найден } end; { MEMBER }

procedure INSERT ( x: nametype; var A: DICTIONARY ); var

bucket: integer; { для номера сегмента } oldheader: tcelltype; begin

if not MEMBER(x A) then begin bucket: = h (x) ; oldheader: = [bucJcet]; new(A[bucket]) ; [bucretl T . element: = x; A[bucket]\.next:- oldheader

end; { INSERT }

procedure DELETE ( x: nametype; var A: DICTIONi\RY ); var

bucket: integer; curren t r Tcel1type; begin

bucJcet: = h (x) ;

if A[bucket] <> nil then begin

if A [bucJcet]T.element = x then { x в первой ячейке }

A[bucket]:= A[bucket]t.next { удаление x из сгшска else begin { x находится не в первой ячейке } current:= Albucket] ;

{ current указывает на предыдущую ячейку } while currentt.next о nil do

if currentt.nextt.element = x then begin curren tt. next: = curren tt. nex-tt. next;

{ удаление x из списка } return { останов }

else { X пока не найден }

current:= current?. next

end; { DELETE }





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 [35] 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123

0.0019