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

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

---

Нашим авторам под силу любые дипломы на заказ . Доверяйте Work5.

---

Предметом исследования являются методы хеширования. Цель работы изучить метод хеширования, хеш-функции, хеш-таблицу, поиск, добавление данных, разрешение коллизий. Для решения поставленных целей в работе решается ряд задач:  дать определение хэш-функции;  изучить методы хеш-функций;  рассмотреть хеш-таблицы;  изучить применение хеширования;  рассмотреть причины возникновения хэш-коллизии;  изучить методы «Отдельная цепочка», «Отдельное сцепление со связанными списками», «Отдельное сцепление со списком заголовочных ячеек», «Отдельное сцепление с другими структурами», «Открытая адресация», «Объединенное хэширование», «Кукушечное хэширование», «Hopscotch хэширование», «Хэширования Робина Гуда», «Двухвариантного хэширования». Структурно работа состоит из введения, заключения, двух глав и списка использованных источников.  

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

1. Андреев Н.Н. О некоторых направлениях исследований в области защиты информации.// Международная конференция “Безопасность информации”. Сборник материалов, М., 2017, c. 94-97 2. Баpичев С.С., Гончаров В.В., Серов Р.Е. Основы современной кpиптогpафии. М.: Мир, 2017. 176 с. 3. Болски М.И. Язык программирования Си. М.: Радио и связь, 2018. 96 с. 4. Грушо А.А. Тимонина Е.Е. Теоретические основы защиты информации М.: Яхтсмен, 2021. 31 с. 5. Домашев А. В., Попов В.О., Правиков Д.И., Прокофьев И.В., Щербаков А.Ю. Программирование алгоритмов защиты информации. М.: Нолидж, 2020. 288 с. 6. Варфоломеев А.А., Жуков А.Е., Мельников А.Б., Устюжанин Д.Д. Блочные криптосистемы. Основные свойства и методы анализа стойкости. М.: МИФИ, 2020. 200с. 7. Молдовян А.А., Молдовян Н.А., Советов Б.Я. Криптография. СПб.: Лань, 2020. 224 с. 8. Семьянов П.В. Почему криптосистемы ненадежны? Тезисы доклада на конф. «Методы и технические средства обеспечения безопасности информации», . СПб.: ГТУ, 2019. 18 с. 9. Спесивцев А. В. Защита информации в персональных ЭВМ. М.: Мир, 2012. 278 с. 10. Ростовцев А.Г., Матвеев В.А. Защита информации в компьютерных системах. Элементы криптологии. Под редакцией П.Д. Зегжды. СПб.: ГТУ, 2021. 365 с.