Структуры и алгоритмы обработки данных


Алгоритм - часть 2


Следовательно, в этом случае G(i)==i, а индексы hi, употребляемые при последующих попытках, таковы:

h0 := H(k)

hi := (hi + i) MOD N,         i  = 1 … N - 1

 

Такой прием называется линейными пробами, его недостаток заключается в том, что строки имеют тенденцию группироваться вокруг первичных ключей (т. е. ключей, для которых при включении конфликта не возникало). Конечно, хотелось бы выбрать такую функцию G, которая вновь равномерно рассеивала бы ключи по оставшимся строкам. Однако на прак­тике это приводит к слишком большим затратам, потому предпочтительнее некоторые компромиссные методы; будучи достаточно простыми с точки зрения вычислений, они все же лучше линейной функции. Один из них — использование квадратичной функ­ции, в этом случае последовательность пробуемых индексов такова:

 

h0 := H(k)

hi := (hi + i2) MOD N,         i  > 0

Если воспользоваться рекуррентными соотношениями  для hi = i2 и di = 2i + l при h0 = 0 и d0 = l, то при вычислении очередного индекса можно обойтись без операции возведения в квадрат.

hi+1 = hi + di

di+1 = di + 2 (i > 0)

Такой прием называется квадратичными пробами, существенно, что он позволяет избежать группирова­ния, присущего линейным пробам, не приводя прак­тически к дополнительным вычислениям. Небольшой же его недостаток заключается в том, что при поиске пробуются не все строки таблицы, т. е. при включе­нии элемента может не найтись свободного места, хотя на самом деле оно есть. Если размер N — про­стое число, то при квадратичных пробах просматри­вается по крайней мере половина таблицы. Такое утверждение можно вывести из следующих рассуж­дений. Если i-я и j-я пробы приводят к одной и той же строке таблицы, то справедливо равенство

i2 MOD N  = j2  MOD N

или

( i2 – j2 ) = 0 ( MOD N )

 

Разлагая разность на два множителя, получаем

 

( i + j )( i - j ) = 0 ( MOD N )

 

Поскольку i ¹ j, то либо i, либо j должны быть больше N/2, чтобы было справедливо равенство    i + j = cN, где с — некоторое целое число.


- Начало -  - Назад -  - Вперед -



Книжный магазин