ИСАУ: Хешированная таблица

Для ускорения поиска требуемой строки существует и иной способ организации данных в таблице. Он основывается на указанной выше возможности двояко идентифицировать строку в таблице, а именно: по значению ключа и по индексу строки. Этот подход лежит в основе группы алгоритмов организации данных в таблицах называемой хешированием. При разработке этого способа организации данных ставилась цель сохранить быстроту поиска, присущую упорядоченной таблицы, и преодолеть отмеченный выше недостаток, связанный с большим временем выполнения операций удаления и добавления строк в таблицу. В основе хеширования лежит размещение строк в таблице не последовательно, а некоторым случайным образом. Хитрость состоит в том, что каждая новая строка размещается в таблице таким образом, что ее присутствие или отсутствие может быть позднее установлено без поиска по всей таблице. Метод хеширования состоит в вычислении значения индекса строки таблицы(адреса) с помощью некоторой функции от ключевого значения строки. Эта функция носит название функцией расстановки (адресной функцией), или хеш-функцией. Существует целый ряд алгоритмов хеширования. Рассмотрим основные их них. Рассмотрение каждого алгоритма будет складываться из этапа заполнения (создания) хешированной таблицы и этапа поиска данных по заданному ключу в созданной таблице. На этапе заполнения у нас есть изначально пустая таблица с n входами. Каждый вход в таблицу идентифицируется индексом в диапазоне значений от 0 до (n-1). В таблицу последовательно заносятся строки в соответствии со значением ключевого поля. Функция хеширования получает на вход значение ключевого поля очередной строки и результатом работы функции является некоторое значение индекса таблицы. Т.е. функция хеширования возвращает в качестве результата целое число в диапазоне от 0 до (n-1). Этапы создания таблицы. Для добавляемой строки по ее ключу вычисляется значение хеш-функции. Это значение трактуется как индекс таблицы. Проверяется, свободна ли в таблице строка с данным индексом. Если да, то новая строка заносится в таблицу по данным индексом. Ограничимся пока предположением, что во всех случаях требуемая нам строка свобода. Рассмотрим этот процесс на примере. Пусть имеется таблица с десятью входами. Небольшой размер таблицы обусловлен стремлением демонстрации алгоритма на простом примере. Пусть у нас поступают следующие входные строки, содержащие описание исторических событий нашей Родины: В качестве ключевого поля строки выберем поле «Дата». Определим хеш-функцию как содержимое поля «Дата» взятое по модулю 10. В соответствии с этим для первой входной строки значение хеш-функции равно 8. Помещаем первую входную строку в строку с индексом 8 создаваемой таблицы. Для второй входной строки значение хеш-функции равно 2. Помещаем вторую входную строку в строку таблицы с индексом 2. И так далее для всех входных строк. В итоге наша таблица будет иметь следующий вид: На этом создание нашей таблицы пока завершилось. Чего же существенного мы достигли? Как сейчас убедимся, достигли мы очень многого. Этап поиска записи по значению ключа. Теперь перед нами стоит задача — по заданному значению ключа (в нашем случае по дате) найти соответствующую запись в таблице. Например, требуется найти запись о событии 1242 года. Для ее поиска значение ключевого поля (1242) обрабатывается той же хеш-функцией, которая использовалась при построении таблицы. Значение результата хеш-функции в этом случае — 2. А это есть значение индекса строки таблицы, где располагается искомая нами строка. Все!!! Результат достигнут и без всякого перебора элементов! Подведем итог. Нам удалось построить данные в таблице таким образом, что время поиска элемента минимальное — мы сразу находим искомый элемент. Обсудим полученный результат. За счет чего удалось добиться столь внушительного успеха? Если присмотреться внимательнее на первый взгляд мы просто реализовали прямой доступ к нашим данным. Возникает естественный вопрос: а почему бы нам сразу не организовать было наши данные в таблицу с прямым доступом, где дата служила бы индексом. Ведь результат по скорости поиска был бы аналогичным достигнутыми нами с помощью хеширования. Но в этом случае наша таблица бы выглядела следующим образом: Как видно, в этом случает размер таблицы катастрофически возрастает. При этом таблица практически осталась пустая. Коэффициент заполнения таблицы составляет ~0.0025 (5/2000). Даже если бы мы начали таблицу не с нулевого индекса, а с 988 (т.е. фактически отбросили начальную пустую часть таблицы) ситуация бы не улучшилась качественно, т.к. коэффициент заполнения таблицы увеличился бы только в два раза и стал бы равным ~0.005. Таким образом использование значения даты как непосредственного индекса приводит к очень не эффективному использованию памяти. Этого пример, в частности, иллюстрирует один из аспектов использования хеширования. По сути хеш-функция преобразует широкий диапазон входных значений ключа (в нашем примере от 0 до 2003) в существенно меньший диапазон значений (в нашем случае от 0 до 9). Этот прием используется практически во всех хеш-функциях. И именно за счет такого преобразования удалось, с одной стороны, организовать хранение данных, достаточно компактно (без множества пустых строк в таблице), а, с другой стороны, обеспечить реализацию метода прямого доступа к этим данным (справедливости ради отметим, что прямой доступ удалось организовать до поры до времени). Но, конечно, внимательный читатель в данный момент негодует: «Зачем мне это все так подробно разжевывают. Ведь вся эта «замечательная» система рухнет, как только встретится строка типа:

№ п.п.	Дата	Событие
7	1147	Первое упоминание Москвы в летописи

В этом случае хеш-функция выдаст значение 7, мы пойдем в таблицу, а там строка 7 уже занята — в ней содержится «1917 Октябрьская революция». Совершенно справедливо все кроме утверждения, что «вся эта «замечательная» система рухнет». Рассмотрим, как же необходимо действовать в этой ситуации. Ситуация, при которой очередная входная строка должна быть записана в уже занятую строку хеш-таблицы, носит название коллизия. Существуют различные алгоритмы разрешения коллизий. Наиболее часто используемые алгоритмы рассмотрены ниже. Линейное хеширование Алгоритм линейного хеширования до возникновения коллизии работает согласно описанной выше схеме. При обнаружении коллизии встает вопрос о том куда записать очередную входную строку в хеш-таблицу. Согласно алгоритму линейного хеширования, если выбранная строка в хеш-таблице занята, то в качестве строки-кандидата на запись в нее данных выбирается следующая строка таблицы. И процесс зацикливается. При достижении последней строки таблицы, в качестве следующей выбирается первая (т.е. таблица рассматривается как циклический буфер). Если пройдена вся таблица и не найдена свободная строка, то это свидетельствует о том, что таблица полностью заполнена и нет возможности занести в нее еще одну строку. Обычно это свидетельствует об ошибке допущенной на стадии проектирования. Простое добавление свободных строк к заполненной хеш-таблице резко снижает скорость поиска данных. Таки образом в рассмотренном нами выше примере в случае использования линейного хеширования таблица примет следующий вид: Естественно возникает вопрос о поиске данных в этом случае. Алгоритм поиска элемента достаточно очевиден и прост. По заданному значению ключа вычисляется значение хеш-функции и выбирается элемент таблицы с индексом равным значению хеш-функции. Сравниваются значения ключей заданного и в выбранном элементе. Если значения совпадают, то поиск завершен успешно. Если нет, то в качестве тестируемого выбирается как из циклического буфера следующий элемент таблицы. Если он пустой, то завершение работы алгоритма с результатом «искомый элемент отсутствует». Алгоритм возвращается к точке сравнения значения ключей. Сформулируем теперь алгоритм линейного хеширования более строгим языком. Пусть для некоторого значения ключа значение хеш-функции равно i. Проверяем i-ю позицию в таблице и, если она свободна, помещаем в нее эту строку. В противном случае (т. е. если в i-ю позицию уже была помещена некоторая строка) выполняем следующие действия. Значение i изменяется по формуле i = mod_n(i+1), где mod_n — число по модулю n, n—длина таблицы. Получаемое значение индекса используется для просмотра соответствующей позиции в таблице. Если найденная позиция свободна, она заполняется этой строкой и т. д. Алгоритм продолжает работу до тех пор, пока не встретится свободная позиция, либо при получении исходного значения iвырабатывается сигнал о переполнении таблицы. Возникает естественный вопрос о времени поиска строки по заданному значению ключа при использовании алгоритма линейного хеширования. В предположении, что при заполнении таблицы значения ключей появляются случайным образом, среднее число шагов поиска строки в методе линейного хеширования описывается следующей формулой:где k—коэффициент заполнения, равный отношению п — числа заполненных элементов таблицы к N — максимальному числу элементов таблицы: Хеширование сложением Алгоритм хеширования сложением является модификацией алгоритма линейного хеширования. Различие их состоит в том, что при вычисление номера следующей строки используется формула i = mod_n(i+m)где в качестве m выбирается некоторое значение, большее единицы. При выборе m следует учитывать, что его значение не должно быть кратно N. Иначе это может привести к ситуации, при которой таблица еще не заполнена, а добавление очередного элемента вызовет вырабатывание сигнала о переполнении таблицы. Действительно, если в приведенном выше примере выбрать m равным 5, то при добавлении записи со значением ключа 1147 возникнет отмеченная ситуация, хотя коэффициент заполнения таблицы= 0.5. Обычно размер таблицы выбирается кратным 2^t. В этом случает в качестве m может быть выбрано, например, любое целое кратное 3, т.к. множество этих чисел никогда не кратно множеству чисел 2^t. Хеширование сложением целесообразно применять в случаях, когда намечается группирование элементов с разными ключами в одной области таблицы. Квадратичное хеширование В алгоритмах квадратичного хеширования при разрешении коллизии вычисляется некая псевдослучайная величина, которая добавляется к значению индекса i. Для вычисления псевдослучайной величины могут быть использованы различные способы. Например, если размер таблицы равен N = 2^t то очередное значение псевдослучайной величины P_j может быть вычислено следующим образом. Предыдущее значение P_j-1 умножается на 5, выделяются t+2 младших двоичных разряда результата и сдвигаются на 2 разряда влево. Полученный результат принимается в качестве P_j. При этом P₁ = 1. Хеширование алгоритмом сцепленных списков При использовании данного алгоритма на этапе создания хеш-таблицы при возникновении коллизии новая входная строка объединяется с существующей в хеш-таблице таким образом, чтобы образовать сцепленный список. Окончательная хеш-таблица в общем случае представляет из себя объединение N сцепленных списков. При этом все элементы каждого отдельного списка имеют одинаковое уникальное значение хеш-функции. Выше разобранный пример построения хеш- таблицы в случае использования алгоритма сцепленных списков будет выглядеть следующим образом: Алгоритм поиска по заданному значению ключа в этом случае очевиден. Вычисляется значение хеш-функции, которое определяет позицию в таблице. Далее, начиная с этой позиции, осуществляется поиск элемента согласно разобранному выше алгоритму поиска элемента в сцепленном списке. Остается не уточненным вопрос о месте размещения строк, добавляемых после обнаружения коллизии. Встречается несколько подходов решения этого вопроса. Один из них — создание элементов в области динамической памяти, как это и принято при реализации сцепленных списков. Второй состоит в использовании дополнительной  таблицы для переполняющих строк. Последняя может быть организована в виде неупорядоченной таблицы или в таком виде, когда элементы, относящиеся к одной позиции хеш-таблицы, связываются в один список. Обычно в хеш-таблице остается достаточно места для хранения переполняющих строк. В связи с этим обе таблицы могут быть совмещены посредством размещения строк, вызывающих коллизию, в первые незанятые позиции хеш- таблицы и объединения в списки тех из них, которые относятся к одной позиции хеш- таблицы. Такой метод организации хеш- таблицы называется методом внутренних цепочек и реализуется в два приема. Сначала создается хеш-таблица с таблицей переполняющих строк. На втором этапе строки из таблицы переполняющих строк переносятся в пустые позиции хеш- таблицы и формируются указатели, связывающие строки, относящиеся к одной позиции хеш-таблицы. Среднее число шагов поиска по таблице хешированной с помощью метода внутренних цепочек описывается формулой: где n — число заполненных строк в хеш-таблице, N — размер хеш-таблицы. При использовании области динамической памяти для создания элементов при разрешении коллизии хеш-таблица представляет собой, по сути, первые элементы N отдельных сцепленных списков. В соответствии с этим в предположении равномерного распределения значений хеш-функции среднее количество шагов поиска описывается как:Данная формула по сути является описанием закономерности поиска элемента в неупорядоченном списке из n/N элементов. Требования к хеш-функции Правильный выбор функции хеширования является ключевым моментом при организации данных в виде хешированной таблицы. Необходимо отметить сразу, что выбор хеш-функции является не ремеслом, а искусством. Нет, к сожалению, строго формализованного алгоритма создания хеш-функции. Есть, конечно, требования к ней и рекомендации по ее созданию, но в каждом случае необходим творческий подход при ее реализации. Рассмотрим некоторые аспекты и требования, которые предъявляются к хеш-функции. Общее требование состоит в том, что хеш-функция должна быть выбраны так, чтобы таблица получилась как можно более эффективной с точки зрения продуктивности последующего поиска. В идеальном случае функция должна вычислять уникальный адрес для каждого из фактически имеющихся ключей. При использовании таблиц фиксированных размеров можно найти подходящую функцию, затратив некоторые усилия. Но если размер таблицы не фиксирован и все возможные ключи выбираются из некоторого достаточно большого множества потенциально возможных ключей, то идеальной функции перемешивания не существует. Требуется лишь функция, хорошая в среднем, когда принимаются во внимание все возможные, появляющиеся на практике ключи, распределение этих ключей и связи между ними. Нам нужно, чтобы перемешанные адреса были равномерно распределены по таблице. Отклонение от этого требования, когда много ключей занимают одну и ту же (или соседние) позицию в таблице, называется первичным скоплением. Естественно, в качестве функции расстановки следует выбирать простые функции, вычисление которых не вызовет заметного замедления выполнения алгоритмов. В сравнении с методами последовательного поиска в таблицах методы хеширования, как правило, дают существенный выигрыш во времени. Однако выбор функции расстановки, обеспечивающей однозначное соответствие с незначительным рассеиванием, не всегда возможен. Следует так же помнить, что выбор функции перемешивания тесно связан с выбором точного размера таблицы. Методы построения хеш-функции Метод деления В методе деления в качестве значения хеш-функции используется остаток от деления ключа на некоторое целое число M: h(k)=K mod M. Очевидно, что эффективность рассеивания зависит ключей по таблице во многом зависит от значения M. Так, совсем плохо, если M является степенью основания системы счисления. В этом случае значением хеш-функции будут просто младшие разряды ключа. Сказанное справедливо и для буквенных ключей. При M = 2⁸например, значением хеш-функции будет последняя буква ключа. Чтобы предотвратить группирование ключей вокруг отдельных адресов таблицы, лучше, если M будет простым числом. Часто множества ключей представляют собой нечто вроде арифметических прогрессий вида XXA, XXB, или FT01, FT02, … .Метод деления преобразует такие прогрессии в последовательные адреса. Такую ситуацию можно считать вполне удовлетворительной. Метод умножения Представим k в виде двоичного числа и примем M = 2⁸. Умножим дробь на k и возьмем дробную часть числа, которую обозначим как {kβ}. В качестве значения хеш-функции используем m младших разрядов. Иными словами h(k)=[M* {kβ}], где [x] — целая часть числа. Рекомендуется в качестве значения β использовать иррациональное число. Например, если взять в качестве так называемое золотое сечение , то отрезок [0,1] очень хорошо делится на {β}, {2 β}, … . Т.е. как бы мелко ни делили отрезок, длины отрезков, получающихся при разбиении, будут выражаться не более чем тремя различными значениямиПри последующих разбиениях отрезок длиныделится на отрезки длинойЭто свойство при использовании метода умножения позволяет достигать хороших результатов. Требование, чтобы при вычислении функциине является обязательным. Но при β =1/M метод эквивалентен методу деления. Очень близким к методу умножения является метод «середины квадрата», в котором в качестве значения h(k) используется m битов средней части квадрата ключа k2. Это еще один из методов хеширования, но по многим параметрам он уступает методу умножения. Метод преобразования системы счисления В основе Метода вычисления значения хеш-адреса лежит преобразование значений ключа k, выраженного в одной системе счисления с основанием p какв другую систему счисления с основанием q при ограничении s на порядок результата:Для вычисления значений функции h(k) необходимо s операций умножения или деления. Следовательно, трудоемкость (число операций) этого метода оказывается больше, чем методов деления и умножения. Метод деления многочленов Пусть k, выраженное в двоичной системе счисления, записывается каки пусть M является степенью двойкиПредставим двоичный ключ k в виде многочлена видасохранив те же коэффициенты. Теперь определим остаток от деления этого многочлена на постоянный многочлен видаэтот остаток, опять же рассматриваемый в двоичной системе счисления, и используем в качестве значения хеш-функции h(k). Для вычисления остатка от деления многочленов используют полиномиальную арифметику по модулю 2. Если в качестве c(t) выбрать простой неприводимый многочлен, то при условии близких, но не равных ключейобязательно будет выполняться условиеЭта функция обладает более сильным свойством скученности в области K. Метод слияния Все рассмотренные выше методы базировались на предположении, что ключ имеет числовое значение. И в большинстве практических задач это предположение справедливо. Но значение ключа может представлять собой и другие типы данных. Наиболее часто из других типов встречаются строковые значения. Рассмотрим возможные пути построения функции хеширования в этом случае. Наиболее часто используемая методика — преобразование строки в числовое значение с помощью некоторого алгоритма. После этого задача сводится к использованию одного из ранее рассмотренных методов или их комбинации. Пусть имеется в качестве значения ключевого поля строковая переменная неопределенной длины. Дефрагментируем эту строку на несколько подстрок постоянной длины, а затем арифметически (логически и т.п.) сложим значения этих частей, трактуя их как целые значения. Часто в качестве подстроки принимается один символ. В этом случае складываются коды, представляющие символы строки. Основной недостаток этого метода состоит в том, что он недостаточно «чувствителен» к порядку букв в строке. Циклический сдвиг ключа позволяет избавиться от этого недостатка. В качестве разновидности этого метода известен подход, в котором слиянию предшествует преобразование каждой буквы ключа в двоичное число, а затем уже разделение числовой последовательности на отрезки и их суммировании. Недостаток метода — необходимость преобразования в данных, что может в ряде случаев требовать определенных временных затрат. Метод вычисления функции хеширования и методы вычисления последовательности псевдослучайных чисел имеет много общего: в основе их лежат одни и те же закономерности, а при их вычислении используются практически одни и те же простые операции. Получение очередного псевдослучайного числа последовательности не что иное, как вычисление значения хеш-функции от последнего полученного члена последовательности. При выборе метода вычисления хеш-функции на практике обычно отдают предпочтение делению или умножению из-за простоты этих методов, позволяющих производить вычисление с высокой скоростью и допускающих простую реализацию на языке высокого уровня. Однако для аппаратной или микропрограммной реализации хеш-функции очень хорошо подходит также метод деления многочленов. Для множества ключей неопределенной длины найти хеш-функцию с идеальными свойствами практически невозможно. Даже если представить, что такую функцию h(k) представить удалось, то она будет взаимно однозначной не более чем для конечного числа первых символов ключа. Однако и в этом случае, можно с успехом использовать рассмотренные выше методы, если отбросить идею однозначности и предпринять специальные меры для разрешения коллизий.