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

О 2,0


0.2 0.4 0.6 0.8

а= N/B-доля заполнения таблицы Рис. 4.5. Средние числа проб, необходимые для выполнения операторов

„Случайные" методики разрешения коллизий

Мы ранее видели, что методика линейного повторного хеширования приводит к группированию заполненных сегментов в большие непрерывные блоки. Можно предложить хеш-функции с более "случайным" поведением, например, ввести целочисленную константу с > 1 и определить hi(x) = (h(x) + ci) mod В. В этом случае для В = 8, с = 3 и h(x) = 4 получим "пробные" сегменты в следующем порядке: 4, 7, 2, 5, О, 3, 6 и 1. Конечно, если Вис имеют обшие делители (отличные от единицы), то эта методика не позволит получить все номера сегментов, например при В = 8 и с = 2. Но более сушественно, что даже если Вис взаимно простые числа (т.е. не имеют общих делителей), то все равно сушествует проблема "группирования", как и при линейном хешировании, хотя здесь разделяются блоки заполненных сегментов, соответствующие различным константам с. Этот феномен увеличивает время выполнения операторов словарей (как и при линейном хешировании), поскольку попытка вставить новый элемент в заполненный сегмент приводит к просмотру цепочки заполненных сегментов, различных для различных с, и длина этих цепочек при каждой вставке увеличивается на единицу.

Фактически любая методика повторного хеширования, где очередная проба зависит только от предыдушей (например, как зависимость от числа предыдущих "неудачных" проб, от исходного значения h{x) или от самого элемента х), обнаруживает группирующие свойства линейного хеширования. Возможна простейшая методика, для которой проблема "группирования" не сушествует: для этого достаточно положить hi(x)= (h(x)+ rf,) mod В, где rf,, йг. i - "случайные" перестановки

чисел 1, 2, В - 1. Конечно, такой набор чисел di, йг, ds-i должен использоваться при реализации всех операторов, выполняемых над словарями, а "случайное" перемешивание целых чисел должно быть сделано (выбрано) еще при разработке алгоритма хеширования.

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



При наличии такого генератора случайных чисел можно воспроизводить требуемую последовательность rfj, йг. при каждом выполнении операторов, работающих

с хещ-таблицей.

Одним из эффективных методов "перемещивания" целых чисел является метод "последовательных сдвигов регистра". Пусть В является степенью числа Ink- константа из интервала от 1 до 5 - 1. Начнем с некоторого числа d,, взятого из интервала от \ по В - 1. Далее генерируется последовательность чисел d,- путем удвоения предыдущего значения до тех пор, пока последнее значение не превысит В. Тогда для получения следующего числа di из последнего значения отнимается число В и результат суммируется побитово по модулю 2 с константой к. Сумма по модулю 2 чисел хну (записывается как X ® у) определяется следующим образом: числа хну записываются в двоичном виде с возможным приписыванием ведущих нулей так, чтобы числа имели одинаковую длину. Результат формируется по правилу логической операции "исключающего ИЛИ", т.е. 1 в какой-либо позиции результата будет стоять тогда и только тогда, когда только в одной аналогичной позиции слагаемых стоит 1, но не в обеих.

Пример 4.7. 25 Ф 13 вычисляется следующим образом:

25 = 11001 13 = 01101 25 ® 13 = 10100

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

Не для каждого значения к можно получить все "перемещанные" значения из 1, 2, В - 1, иногда некоторые сгенерированные числа повторяются. Поэтому для каждого значения В необходимо подобрать свое значение к, которое будет "работать".

Пример 4.8. Пусть В = 8. Если мы положим к = 3, то сгенерируем все числа от О до 7. Например, если начнем с числа di = 5, то для нахождения следующего числа сначала удваиваем число di, получаем число 10, которое больще 8. Поэтому из 10 вычитаем 8, получаем 2 и вычисляем = 2 Ф 3 = 1. Отметим, что для любого х сумму X Ф 3 можно вычислить путем инвертирования (преобразования в обратный код) последних двух двоичных разрядов числа х.

Повторяя описанную последовательность действий, получим числа di, йг, rf? в виде 3-битовых двоичных чисел. Все этапы их вычисления показаны в табл. 4.2. Отметим, что умножение двоичного числа на 2 равнозначно сдвигу влево этого числа на один разряд - это оправдывает название "метод последовательного сдвига регистра".

Таблица4.2. Вычисления по методу последовательного сдвига регисгра

(ii= 101 = 5

сдвиг

1010

удаление ведущей 1 (вычитание 8)

<i2 = 001 = 1

сдвиг

da= 010 =2

сдвиг

£(4=100=4

сдвиг

1000

удаление ведущей 1

di = Oil= 3

сдвиг

(ie= 110 = 6

сдвиг

1100

удаление ведущей 1

® 3

d7 = 111 = 7



Читатель может проверить, что полный "перемешанный" набор чисел 1, 2, 7 можно получить и для = 5, но ни при каких других значениях ft. D

Реструктуризация хеш-таблиц

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

Чтобы сохранить постоянное время выполнения операторов, которое теоретически возможно при использовании хеш-таблиц, мы предлагаем при достижении Л достаточно больших значений, например при Л > 0.9В для закрытых хеш-таблиц и N > 2В - для открытых хеш-таблиц, просто создавать новую хеш-таблицу с удвоенным числом сегментов. Перезапись текуших элементов множества в новую хеш-таблицу в среднем займет меньше времени, чем их ранее выполненная вставка в старую хеш-таблицу меньшего размера. Кроме того, затраченное время на перезапись компенсируется более быстрым выполнением операторов словарей.

4.9. Реализация АТД для отображений

Вернемся к АТД MAPPING (Отображение), введенным в главе 2, где мы определили отображение как функцию, ставяшую в соответствие элементам области определения соответствуюшие элементы из области значений. Для этого АТД мы определили такие операторы.

1. MAKENULL(A). Инициализирует отображение А, где ни одному элементу области определения не соответствует ни один элемент области значений.

2. ASSIGN(A, d, г). Задает яля A(d) значение г.

3. СОМРиТЕ(А, d, г). Возврашает значение true и устанавливает значение г для A(d), если A(d) определено, в противном случае возврашает значение false.

Отображения можно эффективно реализовать с помошью хеш-таблиц. Операторы ASSIGN и COMPUTE реализуются точно так же, как операторы INSERT и MEMBER для словарей. Сначала рассмотрим применение открытых хеш-таблиц. Предполагаем, что хеш-функция h{x) распределяет элементы области определения по сегментам хеш-таблицы. Так же, как и для словарей, в данном случае сегменты содержат связанные списки, в ячейках которых находятся поля для элементов области определения и для соответствуюших им элементов области значений. Для реализации такого подхода надо в листинге 4.8 заменить определение типа ячеек следующим объявлением:

type

celltype = record

domainelement: domaintype; range: rangetype; next: tcelltype

Здесь domaintype и rangetype - типы данных для элементов области определения и области значений соответственно. Объявление АТД MAPPING следующее:

type

MAPPING = array[0..B-1] of Tcelltype





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.0018