АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Оценка качества хеш-функции

Читайте также:
  1. ERP-стандарты и Стандарты Качества как инструменты реализации принципа «Непрерывного улучшения»
  2. II РЕСЕНТИМЕНТ И МОРАЛЬНАЯ ОЦЕНКА
  3. XVII. Эпидемиологический анализ и оценка эффективности противоэпидемических мероприятий
  4. А) Оценка уровня подготовленности нового работника.
  5. Анализ активов организации и оценка эффективности их использования.
  6. Анализ безубыточности и оценка запаса финансовой прочности
  7. Анализ безубыточности и оценка запаса финансовой прочности
  8. Анализ и оценка влияния на объем продаж использования производственных ресурсов.
  9. Анализ и оценка денежных потоков по видам деятельности
  10. Анализ и оценка денежных потоков предприятия
  11. Анализ и оценка дивидендного дохода на одну акцию.
  12. Анализ и оценка поведения фирмы совершенного конкурента в двух временных периодах

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

Рис. 3.6. Распределение коллизий в адресном пространстве таблицы

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

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

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

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

Пример

: ключ √ 10 символов, 1-й большая латинская буква

2-10 малые латинские буквы

var i:integer; s:string[10];

begin

s[1]:=chr(random(90-65)+65);

for i:=2 to 10 do s[i]:=chr(random(122-97)+97);

end

В данном фрагменте используется тот факт, что допустимые коды символов располагаются последовательными непрерывными участками в кодовой таблице. Рассмотрим более общий случай. Допустим, необходимо сгенерировать ключ из m символов с кодами в диапазоне от n1 до n2.

Генерация ключа из m символов c кодами в диапазоне от n1 до n2

(диапазон непрерывный)

for i:=1 to m do str[i]:=chr(random(n2-n1)+n1);

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

Генерация ключа из m символов c кодами

в диапазоне от n1 до n4 (диапазон имеет разрыв от n2 до n3)

for i:=1 to m do

begin

x:=random((n4 - n3) + (n2 √ n1));

if x<=(n2 - n1) then str[i]:=chr(x + n1)

else str[i]:=chr(x + n1 + n3 √ n2)

end;

Рассмотрим еще один конкретный пример. Допустим известно, что ключ состоит из 7 символов. Из них три первые символа √ большие латинские буквы, далее идут две цифры, остальные √ малые латинские.

Пример: длина ключа 7 символов

1. 3 большие латинские (коды 65-90)

2. 2 цифры (коды 48-57)

3. 2 малые латинские (коды 97-122)

var

key: string[7];

begin

for i:=1 to 3 do key[i]:=chr(random(90-65)+65);

for i:=4 to 5 do key[i]:=chr(random(57-48)+57);

for i:=6 to 7 do key[i]:=chr(random(122-97)+97);

end;

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


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 |

Поиск по сайту:



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.004 сек.)