КАТЕГОРИИ: Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748) |
Оценка качества хеш-функции
Begin Var Begin Var i: Integer; Hash: LongInt; Hash:=0; for i:=1 to Length(aKey) do Hash:=((Hash*17)+ord(aKey[i])) mod aTableSize; Result:=Hash; if Result < 0 then Inc(Result, aTableSize); end;
Функция принимает в качестве параметров значение строкового ключа и размер таблицы. Алгоритм поддерживает постоянно изменяющееся хеш-значение, изначально установленное равным нулю. Это значение изменяется для каждого символа в строке путем его умножения на небольшое простое число, добавления кода следующего символа и деления по модулю на размер таблицы. Если конечное значение окажется отрицательным (особенность операции деления по модулю в Delphi), к результату добавится значение размера таблицы. Другая известная функция, именуемая ELF-хешем (формат исполняемых и компонуемых модуле, Executable and Linking Foramt), была предложена П.Дж.Вайнбергером. Отличие алгоритма от приведенного выше заключается в применении эффекта рандомизации, когда операция XOR вновь загружает старший полубайт действующей рабочей переменной хеша (полубайт, который должен исчезнуть в результате переполнения при выполнении следующей операции умножения), если он не равен нулю, в младшую часть переменной. Затем старший полубайт устанавливается в ноль, в результате чего хеш-значение никогда не будет неотрицательным.
function SimpleHash(aKey: string; aTableSize: Integer): Integer; i: Integer; G,Hash: LongInt; Hash:=0; for i:=1 to Length(aKey) do Hash:=(Hash shl 4)+ord(aKey[i]); G:=Hash and LongInt($F0000000); if G <> 0 then Hash:=(Hash xor (G shr 24)) xor G; Result:=Hash mod aTableSize; end;
Функция превосходит предыдущую реализацию благодаря эффекту рандомизации и выполнении для каждого символа только операций поразрядного сдвига и логических операций. В общем случае ее можно считать наилучшей. Правильный выбор хеш-функции важен. При ее удачном построении таблица заполняется более равномерно, уменьшается число коллизий и уменьшается время выполнения операций поиска, вставки и удаления. Для оценки качества хеш-функции проводят имитационное моделирование. Формируется целочисленный массив, длина которого совпадает с размером хеш-таблицы. Случайно генерируется достаточно большое число ключей, для каждого ключа вычисляется хеш-функция. В элементах массива просчитывается число генераций данного адреса. По результатам моделирования можно построить график распределения значений хеш-функции (рис. 8.2). Для получения корректных оценок число генерируемых ключей должно в несколько раз превышать длину таблицы.
Рис. 8.2. Распределение коллизий в адресном пространстве таблицы.
Если число элементов таблицы достаточно велико, то график строится не для отдельных адресов, а для групп адресов. Например, все адресное пространство разбивается на 100 фрагментов и подсчитывается число попаданий адреса для каждого фрагмента. Большие неравномерности свидетельствуют о высокой вероятности коллизий в отдельных местах таблицы. Такая оценка является приближенной, но позволяет предварительно оценить качество хеш-функции и избежать грубых ошибок при ее построении. Оценка будет более точной, если генерируемые ключи будут более близки к реальным ключам, используемым при заполнении хеш-таблицы. Для символьных ключей важно добиться соответствия генерируемых кодов символов тем кодам символов, которые имеются в реальном ключе. Для этого стоит проанализировать, какие символы могут быть использованы в ключе. Например, если ключ представляет фамилию на русском языке, то будут использованы русские буквы. Причем первый символ может быть прописным, а остальные – строчными. Если ключ представляет номерной знак автомобиля, то также несложно определить допустимые коды символов в определенных позициях ключа. Приведем пример генерации ключа из десяти латинских букв, первая из которых является прописной, а остальные строчными:
Дата добавления: 2014-01-07; Просмотров: 1271; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |