Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АрхитектураБиологияГеографияДругоеИностранные языки
ИнформатикаИсторияКультураЛитератураМатематика
МедицинаМеханикаОбразованиеОхрана трудаПедагогика
ПолитикаПравоПрограммированиеПсихологияРелигия
СоциологияСпортСтроительствоФизикаФилософия
ФинансыХимияЭкологияЭкономикаЭлектроника

Функции хеширования

Алгоритмы внутренней сортировки | Задание к лабораторной работе | Методические указания к выполнению задания | Структуры списков | Задание к лабораторной работе | Методические указания к выполнению задания | Структуры BST - деревьев | Задание к лабораторной работе | Структуры сбалансированных деревьев | Задание к лабораторной работе |


Читайте также:
  1. AЧX и ФЧХ передаточной функции цепи.
  2. II. Функции школьной формы
  3. Self и его функции.
  4. В то же время, старение тела - это прогрессирую­щий ожог химическими веществами, который приводит к повреждению желез и нарушению их функций, вплоть до их полой дисфункции.
  5. Верховный тайный совет, его функции и деятельность
  6. Виды аптечных учреждений. Задачи и функции аптечных организаций.
  7. Виды и функции переговоров

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

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

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

Хеш-функция, основанная на выборе цифр, формирует хеш-значение, как комбинацию отдельных цифр ключа. Например,для хеш-таблицы с размером m = 1000 из 12-значного ключа можно выбрать первую, шестую и двенадцатую цифры. Запись этих цифр в позиционной десятичной системе и будет представлять хеш-значение, лежащее в диапазоне от 0 до 999. Но такой способ хеширования оправдывает себя, если ключи элементов, вставляемых в таблицу, равномерно распределены на всём диапазоне значений.

Метод свёртки группирует цифры ключа и складывает группы цифр по модулю m. Например, для m = 1000 ключ 123342954451 можно преобразовать по схеме:

123 + 342 + 954 + 451 = 870.

 

Можно применять свёртку, комбинированную с выбором цифр. Например, сначала выполняется простое суммирование групп цифр ключа, а из полученной суммы выбирается нужное количество цифр.

Метод деления с остатком (модульное хеширование) даёт простые и эффективные хеш-функции. Ключу k ставится в соответствие остаток от деления k на m. Хеш-функция вычисляется, как уравнение h(k) = k mod m.

Mетод хорошо работает, если в качестве m выбирать простые числа, далеко отстоящие от степени двойки. Ниже приведены рекомендуемые размеры хеш-таблиц (числа Мерсенне) для модульного хеширования [8]:

Таблица 2

2n d 2n - d
     
     
    1 021
    2 039
    4 093
    8 191
    16 381
    32 749
    65 521
    131 071
    262 139
    524 287
    1 048 573
    2 097 143
    4 194 301
    8 388 593
    16 777 213
    33 554 393

Метод умножения (мультипликативный) вычисляет хеш- функцию по формуле

h(k) = ë m (k A mod1 ) û

, где A - некоторая константа, удовлетворяющая условию 0 < A < 1, k A mod1 дробная часть произведения k A.

Достоинство метода умножения заключается в том, что качество хеш-функции мало зависит от выбора m. Но обычно в качестве m выбирают степень двойки, так как в большинстве компьютеров умножение на степень двойки реализуется быстро, как сдвиг слова. Метод умножения работает при любом выборе константы А, но некоторые значения А могут быть лучше других. Удачным значением является число – «золотое сечение» [4]:

А = ( - 1)/2» 0,6180339887

Если ключ является строкой символов произвольной длины, то можно применить преобразование строки к натуральному числу и затем применить к этому числу один из описанных выше методов. Но такой способ хеширования не всегда себя оправдывает. Существуют специальные методы хеширования строк. Например, если строки включают только заглавные буквы латинского алфавита, то каждой букве от A до Z можно поставить в соответствие числа от 1 до 26. Строка символов заменяется конкатенацией битовых образов этих чисел, соответствующих символам строки. К десятичному значению получившейся битовой последовательности можно применить любой из описанных выше методов хеширования [3].

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

c 2 = m/P (f i –P/m) 2

, где P – количество ключей, использованных для получения распределения, m - размер хеш - таблицы, f i - количество ключей с хеш-значением, равным i [8].

Если использованные ключи являются случайными на всём пространстве значений ключей U, значение функции c 2 должно быть равно m ± с вероятностью 1 - 1 /c, где c=U/m.


Дата добавления: 2015-11-04; просмотров: 822 | Нарушение авторских прав


<== предыдущая страница | следующая страница ==>
Методические указания к выполнению задания| Разрешение коллизий и структуры хеш-таблиц

mybiblioteka.su - 2015-2024 год. (0.007 сек.)