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

Хеширование строк переменной длины

Читайте также:
  1. I.2. Определение расчетной длины и расчетной нагрузки на колонну
  2. В) Прием подмены независимой переменной
  3. Введите строку ( до 49 символов )
  4. Ввод и вывод символьных строк
  5. Визначте, чи можна вважати поведінку Антонечка ухиленням від слідства? Чи зупинявся в цьому випадку перебіг давності? Як обчислюються строки давності?
  6. Вопрос Загальна характеристика апеляційного оскарження, строк подання. Вимоги до форми та змісту апеляційної скарги (подання).
  7. вопрос Загальна характеристика касаційного оскарження, строк подання. Вимоги до форми та змісту касаційної скарги (подання).
  8. Вопрос Поняття строку вирішення спору та порядок ведення засідання.
  9. Вопрос Поняття та види процесуальних строків.
  10. Вопрос. Символьные и строковые типы.
  11. ВСТАНОВЛЕННЯ СТРОКІВ ВИКОНАННЯ РОБІТ
  12. Гарантійний строк експлуатації обчислюється від дня

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

Хеширование Пирсона — алгоритм, предложенный Питером Пирсоном для процессоров с 8-битными регистрами, задачей которого является быстрое вычисление хеш-кода для строки произвольной длины. На вход функция получает слово , состоящее из символов, каждый размером 1 байт, и возвращает значение в диапазоне от 0 до 255. При этом значение хеш-кода зависит от каждого символа входного слова.

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

h:= 0for each c in W loop index:= h xor c h:= T[index]end loopreturn h

Среди преимуществ алгоритма следует отметить:

· простоту вычисления;

· не существует таких входных данных, для которых вероятность коллизии наибольшая;

· возможность модификации в идеальную хеш-функцию.

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

Идеальное хеширование

Идеальной хеш-функцией (англ. Perfect hash function) называется такая функция, которая отображает каждый ключ из набора в множество целых чисел без коллизий. В математических терминах это инъективное отображение.

Описание

Функция называется идеальной хеш-функцией для , если она инъективна на ;

1. Функция называется минимальной идеальной хеш-функцией для , если она является ИХФ и ;

2. Для целого , функция называется -идеальной хеш-функцией (k-PHF) для если для каждого имеем .

Идеальное хеширование применяется в тех случаях, когда мы хотим присвоить уникальный идентификатор ключу, без сохранения какой-либо информации о ключе. Одним из наиболее очевидных примеров использования идеального (или скорее -идеального) хеширования является ситуация, когда мы располагаем небольшой быстрой памятью, где размещаем значения хешей, связанных с данными хранящимися в большой, но медленной памяти. Причем размер блока можно выбрать таким, что необходимые нам данные, хранящиеся в медленной памяти, будут получены за один запрос. Подобный подход используется, например, в аппаратных маршрутизаторах. Также идеальное хеширование используется для ускорения работы алгоритмов на графах, в тех случаях, когда представление графа не умещается в основной памяти.


1 | 2 | 3 | 4 | 5 |

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

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