Хеширование с цепочками

МИНИСТЕРСТВО  ОБРАЗОВАНИЯ И НАУКИ

РОССИЙСКОЙ  ФЕДЕРАЦИИ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ

ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

ТЮМЕНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

Институт  математики, естественных наук

И информационных технологий

Кафедра программного обеспечения 

КУРСОВАЯ  РАБОТА

По предмету Структуры и алгоритмы компьютерной обработки данных

На тему:

Хеширование с цепочками. 

                                          Выполнила:

                                          Студентка 304-1 группы

                                          Киселева Елена  Александровна

                                          Проверила:

                                          ст.преподаватель  кафедры

                                          программного обеспечения

                                          Киприна Елена Александровна 
 
 

Тюмень-2012

 

Аннотация

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

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

      

Содержание

Теоретическая часть.

1.1  Введение…………………………………………………………………………………….4

1.2 Хеш-функции………………………………………………………………………………...6

1.2.1 Метод  деления……………………………………………………………………………..6

1.2.2 Метод  умножения………………………………………………………………………….7

1.3 Разрешение  коллизий. Хеширование с цепочками………………………………………..9

1.3.1 Реализация  основных процедур и функций  для работы с хеш-таблицами (Паскаль)...9

1.3.2 Оценка  времени работы операций для  хеширования с цепочками…………………...13

Практическая  часть. Демонстрационная программа.

2.1  Описание……………………………………………………………………………………14

2.2 Техническое описание программы………………………………………………………..14

2.3 Скриншот  демонстрационной программы………………………………………………..14

2.4 Обработчики событий……………………………………………………………………..15

2.5 Основные процедуры и функции…………………………………………………………15

Заключение…………………………………………………………………………………………………19

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

Теоретическая часть

1.1  Введение

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

      С хешированием мы сталкиваемся едва ли не на каждом шагу: при работе с браузером (список 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). Эта работа привела к созданию открытой адресации с двойным хешированием.

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

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

      Хеш-функция  – это некоторая функция h(K), которая берет некий ключ K и возвращает адрес, по которому производится поиск в хеш-таблице, чтобы получить информацию, связанную с K. Например, K – это номер телефона абонента, а искомая информация – его имя. Функция в данном случае нам точно скажет, по какому адресу найти искомое.

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

1.2.1 Метод деления.

      Метод деления весьма прост – используется остаток от деления на M:

      h(K) = K mod M

      Надо  тщательно выбирать эту константу. Если взять ее равной 100, а ключом будет случить год рождения, то распределение будет очень неравномерным  для ряда задач (идентификация игроков  юношеской бейсбольной лиги, например). Более того, при четной константе значение функции будет четным при четном K и нечетным - при нечетном, что приведет к нежелательному результату. Еще хуже обстоят дела, если M – это степень счисления компьютера, поскольку при этом результат будет зависеть только от нескольких цифр ключа справа. Точно также можно показать, что M не должно быть кратно трем, поскольку при буквенных ключах два из них, отличающиеся только перестановкой букв, могут давать числовые значения с разностью, кратной трем (см. [3], стр. 552). Приведенные рассуждения приводят к мысли, что лучше использовать простое число. В большинстве случаев подобный выбор вполне удовлетворителен.

      

      Таб1. Значение хеш-функции деления

      В таблице 1 представлены результаты вычисления h(x) для целых 16-разрядных случайных ключей при M=16, 100 и 97. Легко заметить случаи коллизии: например, для М=16 пять различных ключей имеют хеш-адрес, равный 2, для М=100 два ключа имеют хеш-адрес, равный 90, для М=97 два ключа имеют хеш-адрес, равный 82.

      На  практике, метод деления – самый распространенный.

1.2.2 Метод умножения.

      Пусть ключ является w-битовым целым числом. Положим,

      h(К)=Ц.ч.(М*Д.ч.(К*q)),

      где q- константа от 0 до 1, Ц.ч. –целая часть чила, Д.ч. – дробная часть числа.

      Достоинство метода умножения в том, что значаения  хеш-функции мало зависят от выбора М. Обычно в качестве М используют степень двойки – 2^n, тогда умножение на М реализуется как сдвиг на  n битов влево.

      Последовательность  вычисления хеш-функции следующая:

• Ключ К, представленный в виде w-битового числа, умножается на w-битовое число q2^w.
• Получается 2w-битовое число, у которого берут младшие w бит.
• Из выделенных битов выделяют n старших.

      Таким образом, хеш-функция состоит из n старших битов правой половины произведения Кq2^w. Выбор q не принципиален. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

1.3 Разрешение коллизий. Хеширование с цепочками.

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

В данном походе к хешированию таблица рассматривается как массив связанных списков или деревьев. Каждый такой список называется блоком (bucket) и содержит записи, отображаемые хеш-функцией в один и тот же табличный адрес. Эта стратегия разрешения коллизий называется методом цепочек (chaining with separate lists).

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