Министерство Образования РФ Воронежский государственный университет Факультет Компьютерных наук Кафедра программирования и информационных технологий Курсовая работа по курсу "Технологии программирования" по теме "Хеширование" Выполнил: студент 3его курса Шадчнев Евгений Проверил: доцент каф. ПиИТ Хлебостроев Виктор Григорьевич Воронеж 2003 Содержание Введение 3 Хеш-функции 4 Метод деления 4 Метод умножения (мультипликативный) 5 Динамическое хеширование 5 Расширяемое хеширование (extendible hashing) 7 Функции, сохраняющие порядок ключей (Order preserving hash functions) 8 Минимальное идеальное хеширование 8 Разрешение коллизий 10 Метод цепочек 10 Открытая адресация 10 Линейная адресация 11 Квадратичная и произвольная адресация 11 Адресация с двойным хешированием 11 Удаление элементов хеш-таблицы 12 Применение хеширования 13 Хеширование паролей 13 Заключение 15 Приложение (демонстрационная программа) 15 Список литературы: 16 Введение С хешированием мы сталкиваемся едва ли не на каждом шагу: при работе с браузером (список Web-ссылок), текстовым редактором и переводчиком (словарь), языками скриптов (Perl, Python, PHP и др.), компилятором (таблица символов). По словам Брайана Кернигана, это "одно из величайших изобретений информатики". Заглядывая в адресную книгу, энциклопедию, алфавитный указатель, мы даже не задумываемся, что упорядочение по алфавиту является не чем иным, как хешированием. Хеширование есть разбиение множества ключей (однозначно характеризующих элементы хранения и представленных, как правило, в виде текстовых строк или чисел) на непересекающиеся подмножества (наборы элементов), обладающие определенным свойством. Это свойство описывается функцией хеширования, или хеш-функцией, и называется хеш-адресом. Решение обратной задачи возложено на хеш-структуры (хеш-таблицы): по хеш-адресу они обеспечивают быстрый доступ к нужному элементу. В идеале для задач поиска хеш-адрес должен быть уникальным, чтобы за одно обращение получить доступ к элементу, характеризуемому заданным ключом (идеальная хеш-функция). Однако, на практике идеал приходится заменять компромиссом и исходить из того, что получающиеся наборы с одинаковым хеш-адресом содержат более одного элемента. Термин "хеширование" (hashing) в печатных работах по программированию появился сравнительно недавно (1967 г., [1]), хотя сам механизм был известен и ранее. Глагол "hash" в английском языке означает "рубить, крошить". Для русского языка академиком А.П. Ершовым [2] был предложен достаточно удачный эквивалент - "расстановка", созвучный с родственными понятиями комбинаторики, такими как "подстановка" и "перестановка". Однако он не прижился. Как отмечает Дональд Кнут [3], идея хеширования впервые была высказана Г.П. Ланом при создании внутреннего меморандума IBM в январе 1953 г. с предложением использовать для разрешения коллизий хеш-адресов метод цепочек. Примерно в это же время другой сотрудник IBM - Жини Амдал - высказала идею использования открытую линейную адресацию. В открытой печати хеширование впервые было описано Арнольдом Думи (1956), указавшим, что в качестве хеш-адреса удобно использовать остаток от деления на простое число. А. Думи описывал метод цепочек для разрешения коллизий, но не говорил об открытой адресации. Подход к хешированию, отличный от метода цепочек, был предложен А.П. Ершовым (1957, [2]), который разработал и описал метод линейной открытой адресации. ............