Особенности процесса хеширования

скачать (2902.1 kb.)

  1   2   3   4
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ

АНГАРСКАЯ ГОСУДАРСТВЕННАЯ ТЕХНИЧЕСКАЯ АКАДАМИЯ

КИБЕРНЕТИЧЕСКИЙ ФАКУЛЬТЕТ

КАФЕДРА ВЫЧИСЛИТЕЛЬНЫЕ МАШИНЫ И КОМПЛЕКСЫ
РЕФЕРАТ

По дисциплине "Структуры и алгоритмы”

Тема: Особенности процесса хеширования


Выполнил:

студент гр. ИВТз-11-1

Лужбин В.Г.

Проверил:

доцент Кулакова И.М.


г. Ангарск, 2013г.
Содержание
Введение

Хеширование

Хеш-функции

Хеш-таблицы

Метод цепочек

Метод открытой адресации

Контрольная сумма

Список используемой литературы


Введение
С хешированием сталкиваются едва ли не на каждом шагу: при работе с браузером (список Web-ссылок), текстовым редактором и переводчиком (словарь), языками скриптов (Perl, Python, PHP и др.), компилятором (таблица символов). По словам Брайана Кернигана, это "одно из величайших изобретений информатики". Заглядывая в адресную книгу, энциклопедию, алфавитный указатель, мы даже не задумываемся, что упорядочение по алфавиту является не чем иным, как хешированием.

Хеширование применяется для быстрого поиска в структурах данных и в криптографии, а также для проверки на наличия ошибок.

Хеширование это процесс получения уникального (чаще цифрового) идентификатора для объекта.


Хеширование

Хеширование (hash - смешивание, перемешивание, размешивание) - преобразование входного массива данных в короткое число фиксированной длины (которое называется хешем или хеш-кодом) таким образом, чтобы с одной стороны, это число было значительно короче исходных данных, а с другой стороны, с большой вероятностью однозначно им соответствовало.

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

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

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

Примечание

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

  1   2   3   4



Рефераты Практические задания Лекции
Учебный контент

© ref.rushkolnik.ru
При копировании укажите ссылку.
обратиться к администрации