Решение задач на тему: Хеш-функции. Метод деления. Метод умножения мультипликативный

Введение

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

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

Термин "хеширование" (hashing) в печатных работах по программированию появился сравнительно недавно (1967 г., [1]), хотя сам механизм был известен и ранее. Глагол "hash" в английском языке означает "рубить, крошить". Для русского языка академиком А.П. Ершовым [2] был предложен достаточно удачный эквивалент - "расстановка", созвучный с родственными понятиями комбинаторики, такими как "подстановка" и "перестановка". Однако он не прижился.

Как отмечает Дональд Кнут [3], идея хеширования впервые была высказана Г.П. Ланом при создании внутреннего меморандума IBM в январе 1953 г. с предложением использовать для разрешения коллизий хеш-адресов метод цепочек. Примерно в это же время другой сотрудник IBM - Жини Амдал - высказала идею использования открытую линейную адресацию. В открытой печати хеширование впервые было описано Арнольдом Думи (1956), указавшим, что в качестве хеш-адреса удобно использовать остаток от деления на простое число. А. Думи описывал метод цепочек для разрешения коллизий, но не говорил об открытой адресации. Подход к хешированию, отличный от метода цепочек, был предложен А.П. Ершовым (1957, [2]), который разработал и описал метод линейной открытой адресации. Среди других исследований можно отметить работу Петерсона (1957, [4]). В ней реализовывался класс методов с открытой адресацией при работе с большими файлами. Петерсон определил открытую адресацию в общем случае, проанализировал характеристики равномерного хеширования, глубоко изучил статистику использования линейной адресации на различных задачах. В 1963 г. Вернер Букхольц [6] опубликовал наиболее основательное исследование хеш-функций.

К концу шестидесятых годов прошлого века линейная адресация была единственным типом схемы открытой адресации, описанной в литературе, хотя несколькими исследователями независимо была разработана другая схема, основанная на неоднократном случайном применении независимых хеш-функции ([3], стр. 585). В течение нескольких последующих лет хеширование стало широко использоваться, хотя не было опубликовано никаких новых работ. Затем Роберт Моррис [5] обширный обзор по хешированию и ввел термин "рассеянная память" (scatter storage). Эта работа привела к созданию открытой адресации с двойным хешированием.

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

Оглавление

- Введение 3

- Хеш-функции

- Метод деления

- Метод умножения мультипликативный

- Динамическое хеширование

- Расширяемое хеширование extendible hashing

- Функции, сохраняющие порядок ключей Order preserving hash functions

- Минимальное идеальное хеширование

- Разрешение коллизий

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

- Открытая адресация

- Линейная адресация

- Квадратичная и произвольная адресация

- Адресация с двойным хешированием

- Удаление элементов хеш-таблицы

- Применение хеширования

- Хеширование паролей

- Заключение 15

- Приложение демонстрационная программа

- Список литературы 16

Заключение

Хеширование, которое родилось еще в середине прошлого века, активно используется в наши дни везде, где требуется произвести быструю выборку данных. Появились новые методы хеширования, новые модификации алгоритмов, написанных ранее. По мнению Дональда Кнута ([3], стр. 586), наиболее важным открытием в области хеширования со времен 70 годов, вероятно, является линейное хеширование Витольда Литвина [18]. Линейное хеширование, которое не имеет ничего общего с классической технологией линейной адресации, позволяет многим хеш-адресам расти и/или выступать в поли вставляемых и удаляемых элементов. Линейное хеширование может также использоваться для огромных баз данных, распределенных между разными узлами в сети.

Разумеется, методы и сферы применения хеширования не ограничиваются тем, что представлено в этой работе. Не вдаваясь в строгий анализ эффективности, были рассмотрены только базовые, наиболее известные методы. Помимо них можно отметить полиномиальное хеширование (М. Ханан и др., 1963), упорядоченное хеширование (О. Амбль, 1973), линейное хеширование (В. Литвин, 1980). Подробнее о методах хеширования см. [3, 6, 7, 19-22].

Список литературы

- Неllеrmаn Н., Digitаl Соmрutеr Systеm Рrinсiрlеs. МсGrаw-Нill.

- Ершов А.П., Избранные труды., Новосибирск: "Наука".

- Кнут Д., Искусство программирования, т.3. М.: Вильямс.

- Реtеrsоn W.W., Аddrеssing fоr Rаndоm-Ассеss Stоrаgе // IВМ Jоurnаl оf Rеsеаrсh аnd Dеvеlорmеnt, 1957. V.1, N2. Р.

- Моrris R., Sсаttеr Stоrаgе Тесhniquеs // Соmmuniсаtiоns оf thе АСМ, 1968. V.11, N1. Р.

- Вuсhhоlz W., IВМ Systеms J., 2 (1963).

- Fundаmеntа Маth. 46 (1958).

- R. Сiсhеlli, Мinimаl Реrfесt Наshing Маdе Simрlе, Соmm. АСМ Vоl. 23 Nо. 1, Jаn.

- Т. Gunji, Е. Gоtо, J. Infоrmаtiоn Рrос., 3 (1980).

- Чмора А., Современная прикладная криптография., М.: Гелиос АРВ.

- Litwin W., Рrос. 6th Intеrnаtiоnаl Соnf. оn Vеry Lаrgе Dаtаbаsеs (1980).

- Кормен Т., Лейзерсон Ч., Ривест Р., Алгоритмы: построение и анализ, М.: МЦНМО.

- Вирт Н., Алгоритмы структуры данных программы, М.: Мир.

- Керниган Б., Пайк Р., Практика программирования, СПб.: Невский диалект.

- Шень А, Программирование: теоремы и задачи. М.: МЦНМО.