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

таблице, то каждый сегмент в среднем будет иметь N/B элементов и мы ожидаем, что операторы INSERT, DELETE и MEMBER будут выполняться в среднем за время 0(1 + -W/B). Здесь константа 1 соответствует поиску сегмента, а N/B- поиску элемента в сегменте. Если В примерно равно N, то время выполнения операторов становится константой, независящей от N.

Предположим, что есть программа, написанная на языке программирования, подобном Pascal, и мы хотим все имеющиеся в этой программе идентификаторы занести в хещ-таблицу. После обнарркения объявления нового идентификатора он вставляется в хещ-таблицу, конечно же, после проверки, что его еще нет в хещ-таблице. На этапе проверки естественно предполокить, что идентификатор с равной вероятностью может быть в любом сегменте. Таким образом, на процесс заполнения хещ-таблицы с jV элементами потребуется время порядка 0(N(1 + Л/В)). Если положить, что В равно N, то получим время 0(N).

На следующем этапе анализа программы просматриваются идентификаторы в теле программы. После наховдения идентификатора в теле программы, чтобы получить информацию о нем, его же необходимо найти в хещ-таблице. Какое время потребуется для нахождения идентификатора в хещ-таблице? Если время поиска для всех элементов примерно одинаково, то оно соответствует среднему времени вставки элемента в хещ-таблицу. Чтобы увидеть это, достаточно заметить, что время поиска любого элемента равно времени вставки элемента в конец списка соответствующего сегмента. Таким образом, время поиска элемента в хещ-таблице составляет 0(1 + N/B).

В приведенном выще анализе предполагалось, что хещ-функция распределяет элементы по сегментам равномерно. Но существуют ли такие функции? Рассмотрим функцию, код которой приведен в листинге 4.7, как типичную хещ-функцию. (Напомним, что эта функция преобразует символы в целочисленный код, суммирует коды всех символов и в качестве результата берет остаток от деления этой суммы на число В.) Следующий пример оценивает работу этой функции.

Пример 4.5. Предположим, что функция из листинга 4.7 применяется для занесения в таблицу со 100 сегментами 100 символьных строк АО, А1, .... А99. Принимая во внимание, что ord(O), ord(l) ord(9) образуют арифметическую прогрессию (это справедливо для всех таблиц кодировок, где цифры О, 9 стоят подряд, например для кодировки ASCII), легко проверить, что эти элементы займут не более 29 сегментов из ста, наибольщий сегмент (сегмент с номером 2) будет содержать элементы А18, А27, А36, А90, т.е. девять элементов из ста. Используя тот факт, что для вставки i-vo элемента требуется i + 1 щагов, легко подсчитать, что в данном случае среднее число щагов, необходимое для вставки всех 100 элементов, равно 395. Для сравнения заметим, что оценка N{1 + Л/В)предполагает только 200 щагов. □

В приведенном примере хещ-функция распределяет элементы исходного множества по множеству сегментов не равномерно. Но возможны "более равномерные" хещ-функции. Для построения такой функции можно воспользоваться хорощо известным методом возведения числа в квадрат и извлечения из полученного квадрата нескольких средних цифр. Например, если есть число л, состоящее из 5 цифр, то после возведения его в квадрат получим число, состоящее из 9 или 10 цифр. "Средние цифры" - это цифры, стоящие, допустим, на позициях от 4 до 7 (отсчитывая справа). Йх значения, естественно, зависят от числа и. Если В = 100, то для формирования номера сегмента достаточно взять две средние цифры, стоящие, например, на позициях 5 и 6 в квадрате числа.

Отметим, что строки А2 и А20 не обязательно должны находиться в одном сегменте, но А23 и А41, например, будут располагаться в одном сегменте.

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



Этот метод можно обобщить на случай, когда В не является степенью числа 10. Предположим, что элементы исходного множества являются целыми числами из интервала О, 1, К. Введем такое целое число С, что ВС примерно равно Я, тогда функция

h(n) = [п/С] mod В,

где [х] обозначает целую часть числа х, эффективно извлекает из середины числа цифры, составляющие число, не превышающее В.

Пример 4.6. Если К = 1000 и 5 = , то можно выбрать С = 354. Тогда

А(456) =

207936

mods = 587 mods = 3. □

Для применения к символьной строке описанной хеш-функции надо сначала в строке сгруппировать символы справа налево в блоки с фиксированным количеством символов, например по 4 символа, добавляя при необходимости слева пробелы. Каждый блок трактуется как простое целое число, из которого путем конкатенации (сцепления) формируется двоичный код символов, составляющих блок. Например, основная таблица ASCII кодировки символов использует 7-битовый код, поэтому символы можно рассматривать как "цифры" по основанию 2" или 128*. Таким образом, символьную строку abed можно считать целым числом (128)*а + (128)& + (128)с + d. После преобразования всех блоков в целые числа они суммируются, а затем выполняется вышеописанный процесс возведения в квадрат и извлечения средних цифр.

Анализ закрытого хеширования

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

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

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

Конечно, если вы работаете не только с латиницей, но и с кириллицей, то необходимо использовать полную таблицу ASCII. В этом случае основанием для "цифр"-символов будет не 2, а 2, но суть метода от этого не меняется. - Прим. ред.

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



которые методики повторного хеширования, даюшие "случайное" (равномерное) распределение элементов по сегментам.

Вероятность коллизии равна N/B. Предполагая осушествление коллизии, на первом этапе повторного хеширования "работаем" с В - \ сегментом, где находится Л - 1 элемент. Тогда вероятность возникновения двух подряд коллизий равна N(N - 1)/(В(В - 1)). Аналогично, вероятность по крайней мере / коллизий равна

-l)...(N-i + 1) В{И- l)...(B~i + l)

Если значения В к N большие, то эта вероятность примерно равна (iV/B).Среднее Число проб равно единице плюс сумма по всем i > 1 вероятностей событий, что, по крайней мере, осуществится / коллизий, т.е. среднее число проб примерно равно (не

превышает) 1 + {N/В) =-} Можно показать, что точное значение этой сум-

(=1 В- N

мы при подстановке в нее выражения (4.3) вместо (. Bjpaвнo-В + \-

В+ 1 -Л

наша приближенная формула достаточно точна, за исключением случая, когда Л близко к В.

Отметим, что величина--растет очень медленно при возрастании Л от О

ДО в - 1, т.е. до максимального значения N, когда еше возможна вставка нового элемента. Например, если Л равняется половине В, то в среднем требуются две пробы для вставки нового элемента. Среднее число проб на один сегмент при заполнении

М сегментов равно g + х-сумму можно аппроксимировать ин-тегралом --ах , который равен -1г-г. Таким образом, для пол-

jv/J° в-х м ув-м + 1 j

ного заполнения таблицы (М = В) требуется в среднем 1пВ проб на сегмент, или всего В\т\В проб. Но для заполнения таблицы на 90% (М = 0.9В) требуется всего В((10/9)1п10), или примерно 2.56В проб.

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

Здесь использована следующая формула вычисления среднего (математического ожидания). Пусть X - положительная целочисленная случайная величина, принимающая положительное целое значение i с вероятностью р,-. Тогда математическое ожидание случайной величины X можно вычислить по формуле M[xJ = ~1р,= + ХГ.г Si.,А =

= 1 + Х.г"!- Отсюда легко получается приведенная в тексте оценка. - Прим. ред.





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