- •Отчет №4
- •1.Хеширование
- •Хеш-функции, основанные на делении
- •Мультипликативная схема хеширования
- •Хеширование строк переменной длины
- •Идеальное хеширование
- •Описание Функция называется идеальной хеш-функцией для , если она инъективна на ;
- •Универсальное хеширование
- •Описание
- •В хеш-таблицах
- •Криптографическая соль
- •Криптографические хеш-функции
- •Геометрическое хеширование
- •Ускорение поиска данных
- •2.Пирамиды
- •Замечательное свойство кучи.
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
федеральное государственное бюджетное образовательное учреждение
высшего профессионального образования
«Забайкальский государственный университет»
(ФГБОУ ВПО «ЗабГУ»)
Энергетический факультет
Кафедра информатики и вычислительной техники
Отчет №4
по дисциплине: «Алгоритмы обработки данных»
Выполнил ст. гр. ИВТ-13-2(ВМК)
(группа)
Забелин В.О.
(фамилия, инициалы)
Чита
2015
1.Хеширование
Хеширование – преобразование по определённому алгоритму входного массива данных произвольной длины в выходную битовую строку фиксированной длины. Такие преобразования также называются хеш-функциями или функциями свёртки, а их результаты называют хешем, хеш-кодом, хеш-суммой или сводкой сообщения.
Хеширование применяется для построения ассоциативных массивов, поиска дубликатов в сериях наборов данных, построения достаточно уникальных идентификаторов для наборов данных, контрольного суммирования с целью обнаружения случайных или намеренных ошибок при хранении или передаче, для хранения паролей в системах защиты (в этом случае доступ к области памяти, где находятся пароли, не позволяет восстановить сам пароль), при выработке электронной подписи (на практике часто подписывается не само сообщение, а его хеш-образ).
В общем случае однозначного соответствия между исходными данными и хеш-кодом нет в силу того, что количество значений хеш-функций меньше, чем число вариантов значений входного массива; существует множество массивов с разным содержимым, но дающих одинаковые хеш-коды — так называемые коллизии. Вероятность возникновения коллизий играет немаловажную роль в оценке качества хеш-функций.
Существует множество алгоритмов хеширования с различными свойствами(разрядность, вычислительная сложность, криптостойкость и т. п.). Выбор той или иной хеш-функции определяется спецификой решаемой задачи. Простейшими примерами хеш-функций могут служить контрольная сумма или CRC.
Виды хеш-функций
Хорошая хеш-функция должна удовлетворять двум свойствам:
быстро вычисляться;
минимизировать количество коллизий
Предположим, для определённости, что — количество ключей, а хеш-функция имеет не более различных значений:
В качестве примера «плохой» хеш-функции можно привести функцию с , которая десятизначному натуральном числу сопоставляет три цифры выбранные из середины двадцатизначного квадрата числа . Казалось бы, значения хеш-кодов должны равномерно распределиться между «000» и «999», но для реальных данных такой метод подходит лишь в том случае, если ключи не имеют большого количества нулей слева или справа.
Однако существует несколько более простых и надежных методов, на которых базируются многие хеш-функции.
Хеш-функции, основанные на делении
Первый метод заключается в том, что мы используем в качестве хеша остаток от деления на , где — это количество всех возможных хешей:
При этом очевидно, что при чётном значение функции будет чётным, при чётном , и нечётным — при нечётном, что может привести к значительному смещению данных в файлах. Также не следует использовать в качестве степень основания счисления компьютера, так как хеш-код будет зависеть только от нескольких цифр числа , расположенных справа, что приведет к большому количеству коллизий. На практике обычно выбирают простое — в большинстве случаев этот выбор вполне удовлетворителен.
Ещё следует сказать о методе хеширования, основанном на делении на полином по модулю два. В данном методе также должна являться степенью двойки, а бинарные ключи () представляются в виде полиномов. В этом случае в качестве хеш-кода берутся значения коэффициентов полинома, полученного как остаток от деления на заранее выбранный полином степени :
При правильном выборе такой способ гарантирует отсутствие коллизий между почти одинаковыми ключами.