Понедельник, Июль 5th, 2010

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

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, где с — некоторое целое число. На практике упомянутый недостаток не столь существен, так как N/2 вторичных попыток при разрешении конфликтов встречаются очень редко, главным образом в тех случаях, когда таблица почти заполнена.

Контрольные вопросы

1.Для чего предназначен метод расстановок ?
2.От чего зависит положение элемента в массива в методе расстановок ?
3.Какую функцию возможно использовать в качестве хэш-функции:
4.Что называется конфликтом ?
5.Какой из методов является методом разрешения конфликтов.
6.Какой из методов разрешения конфликтов позволяет более равномерно распределить элементы по массиву.
7.Почему невозможно применять в качестве H(k) функцию Trunc(sqrt(k5- i*tan(k))) MOD N ?

часть 2.
практикум по сруктурам и алгоритмам обработки данных в эвм

методическое руководство к лабораторным работам

Организационно-методические указания

1.Перед началом лабораторной работы проводится консультация по методике выполнения лабораторных работ по данной дисциплине.

Страницы: 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

Категория: Учебники