Отметим, что вычисление следующего индекса не требует юзведения в квадрат, если использовать рекуррентное соот-

шение (4.92) для /г, = и di = 2t + 1:

с fto = о и do = 1. Этот метод называется квадратичным опробированием, он успешно позволяет избежать первичного скопления, хотя практически не требует никаких дополнительных вычислений. Небольшой недостаток заключается в том, что при опробировании рассматриваются не все строки таблицы, так что при включении можно не встретить свободного места, 3£Отя такие места еще остаются. Фактически если ее размер N - простое число, то при квадратичном опробировании используется по меньшей мере половина таблицы. Это можно получить из следующих рассуждений: если i-я и /-я пробы приводят к одной и той же строке таблицы, то справедливо равенство

f mod = f mod N

или

Разбивая разность на два множителя, мы получаем \ (/ + /)( -/) О (mod Л^).

Поскольку i ф \, мы видим, что либо /, либо / должно быть не менее N/l, чтобы получить i + / = cN, где с - целое число.

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

Чтобы на примере продемонстрировать метод рассеянных Таблиц, мы переписали программу 4.5 -формирование таблицы перекрестных ссылок - в виде программы 4.8. Принципиальное отличие заключается в формулировке процедуры Поиска (search) и в замене ссылочного типа wordref таблицей клов Т. Функция расстановки Н есть модуль размера таблицы; для разрешения конфликтов выбрано квадратичное

дается методам, представляющим компромисс; будучи простыми для вычисления, они все же лучше линейной функции (4.90). Один из них состоит в использовании квадратичной функции, такой, что последовательность индексов для опробирования есть

h, = (Ло + i) mod N (i > 0).

program crossref(f,output);

[построение ma6mifbi перекрестных ссылок с иагользовапиел, расстановки] j

label 13;

const cl = 10; [длина слова]

c2 = 8; [количество слов в строке]

сЗ = 6; [количество цифр в числе]

с4 ~ 9999; [максимальный номер строки]

р = 997; [простое число]

free =

type index = О. .р;

itemref = ptem;

word - xtcarAkey: alfa;

-------firstJast: itemref; .

fol: index

end ;

item = packed record

Ino: 0.. c4; next: itemref

end ;

таг /, top: index;

k,kl: integer;

n: integer; [номер текущей строки]

id: alfa; f: text;

a: array [1.. cl] aichar;

t: array ]p. .p] of word; [массив для расстановки] procedure search; var h,d,i: index;

x: itemref; f: boolean; [глобальные переменные: t, id, top] begin h := ord(id) mod p; f := false; d := 1; new(x); x].lno := n; xl.next := nil; repeat

if t[h].key = id then -

begin [найдено] f:- true;

t[h] .last\.next := x; t[h].last := x end else if t[h].key = free then

begin [новый элемент] f := true; with t[h] do

begin Arc; := id; first ;= x;last :=> л;/<?/:== iP

end ;

top := A enelse

begin {конфликт] h := A+Vf; d := if A > /; then A := A-i?; n d p then

begin w e/n(TABLE OVERFLOW); goto 13 end

end-----

until/ 3id {лшгсА} : locedure printtable; var rj,m: index; froceuateprintwotd(w. word);

var /: integer; x: itemref; begin wn7e( w.key); X := w.rj/; / := 0; repeat if I = c2 then begin writeln;

1 := 0; writeC :cl+I) end ;

/ := write(x\-ino:c3); x . x1,next until л = nil; writeln end {printword] ;

rm i := /op; while i Ф p do

begin [просмотр связанного списка и поиск минима.ЛЬН020 КЛЮЧа] т := i; j := t[i].fol; while j Ф p йо

begin if f[y]./cev < t[m].key then г := у;

end ;

printword(t[m]); ii m Ф г then

begin t[m],key :== Т^ф';

t[m].first := t[fi.first; t[m].last := rH.tof

end ;

ttd {printtable} ;

Шп n :~ 0; fcl cl; top := p; re5e/(/);