2. Хеширование. Хеш-функции. Коллизии и методы их устранения. Сферы применения хеширования, достоинства метода.

Хеширование является самым быстродействующим из известных методов программного поиска. Термин хеширование произошел от английского глагола «to hash» (крошить, нарезать, делать месиво). Для методов хеширования встречаются следующие термины: рассеянная память, адресация вразброс, адресация с перемешиванием, ключевые преобразования, расстановка. Данный метод не требует никакого упорядочивания или сортировки ключевых слов. Высокая скорость выполнения операции хеширование обусловлена тем, что элементы данных запоминаются и впоследствии выбираются из ячеек памяти, адреса которых являются простыми арифметическими функциями содержимого соответствующих ключевых слов. Адреса, получаемые из ключевых слов методом хеширования, называются хеш адресами. Таким образом, идея хеширования состоит в том, чтобы взять некоторые характеристики ключа с помощью, так называемой хеш-функции и взять это значение в качестве адреса начала поиска, то есть k храниться по адреса F(k). С хеш-функцией связана так называемая хеш-таблица, ячейки которой пронумерованы и хранят сами данные или ссылки на данные. Однако функции, дающие неповторяющиеся значения редки даже в случае большой таблицы. Возможно, что найдутся различные ключи k_i=!k_j, для которых F(k_i)=F(k_j). Таким образом, часто отображение, осуществляемое хеш-функцией, является отображение многие к одному и приводит к коллизии. При возникновении коллизии два или более ключа ассоциируются с одной и той же ячейкой хеш-таблицы. Поскольку два ключа не могут занимать одну и ту же ячейку в таблице, необходимо выбрать стратегию разрешения коллизий, то есть метод, указывающий альтернативное местоположение элемента. Следовательно, чтобы использовать хеш-таблицу, программист должен выбрать хеш-функцию и метод разрешения коллизий.

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

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

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

В линейном пробинге к хеш адресу прибавляется или вычитается по единице, пока не обнаружится незанятая ячейка. а_i =(a0+i)mod t. а_i – номер пробы, а t - размер хеш таблицы. T >= 1,5*n. При квадратичной пробе расчет ведется по той же формуле, но при i^2. N - Общее количество ключей. Небольшой недостаток квадратичных проб заключается в том, что при поиске пробуются не все строки таблицы, т.е. при включении элемента может не найтись свободного места, хотя на самом деле оно есть. Если размер T – простое число, то при квадратичных пробах рассматривается, по крайней мере, половина таблицы.

2 метод устранения – метод цепочек.

При этом подходе к хешированию, таблица рассматривается как массив связанных списков. Каждая такая цепочка называется блоком и содержит записи отображаемой хеш функции в один и тот же табличный адрес. Чтобы обнаружить элемент данных, нужно применить хеш функцию для определения нужного связного списка и выполнить там последовательный поиск. Пример таких цепочек размер таблицы T, рекомендуется брать от 1/3n от количества элементов до 1/2n. В общем случае, метод цепочек быстрее открытой адресации, т.к. просматривает только те ключи, которые попадают в один и тот же табличный адрес. Кроме того, открытая адресация предполагает наличие таблицы фиксированного размера, в то время как в методе цепочек элементы таблицы создаются динамически.

• Наибольшее применение метода хеширования получило системное программирование. В настоящее время все символьные таблицы строятся по методу хеширования.

• Управление базами данных.

• Применяется для организации таблиц, используемых в языках искусственного интеллекта.

• Защита информации, криптографии, кодировании.