Хэш-функции и хэш-адресация

      Комментарии к записи Хэш-функции и хэш-адресация отключены

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

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

Хэш-функцией Fназывается некоторое отображение множества входных элементов R на множество целых неотрицательных чисел Z: F(r)=n, rR, nZ. Сам термин “хэш-функция” происходит от английского термина “hash function” (hash – “мешать”, “смешивать”, “путать”). Вместо термина “хэширование” иногда используются термины “рандомизация”, “переупорядочивание”.

Множество допустимых входных элементов R называется областью определения хэш-функций. Множеством значений хэш-функций F называется подмножество М из множества целых неотрицательных чисел Z: MНZ, содержащее все возможные значения, возвращаемые функцией F: “rR: F(r)M. Процесс отображения области определения хэш-функций на множество значений называется “хэшированием”.

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

Областью определения хэш-функции будет множество всех возможных имен идентификаторов.

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

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

На рис. 3 проиллюстрирован метод организации таблиц идентификаторов с использованием хэш-адресации. Трем различным идентификаторам A1, А2, А3соответствуют на рисунке три значения хэш-функции n1, n2, n3. В ячейки, адресуемые n1, n2, n3, помещается информация об идентификаторах A1, А2, А3. При поиске идентификатора А3вычисляется значение адреса n3и выбираются данные из соответствующей ячейки таблицы.

Рис. 3. Организация таблицы идентификаторов с использованием хэш-адресации

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

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

Построение таблиц идентификаторов на основе хэш-функции.Существуют различные варианты хэш-функции. Получение результата хэш-функции – “хэширование” – обычно достигается за счет выполнения над цепочкой символов некоторых простых арифметических и логических операций. Самой простой хэш-функцией для символа является код внутреннего представления в ЭВМ литеры символа. Эту хэш-функцию можно использовать и для цепочки символов, выбирая первый символ в цепочке. Так, если двоичное ASCII представление символа А есть 00100001, то результатом хэширования идентификатора АТаble будет код 00100001.

Хэш-функция, предложенная выше, очевидно не удовлетворительна: при использовании такой хэш-функции возникнет новая проблема – двум различным идентификаторам, начинающимся с одной и той же буквы, будет соответствовать одно и то же значение хэш-функции. Тогда при хэш-адресации в одну ячейку таблицы идентификаторов по одному и тому же адресу должны быть помещены два различных идентификатора, что явно невозможно. Такая ситуация, когда двум или более идентификаторам соответствует одно и то же значение функции, называется коллизией. Возникновение коллизии проиллюстрировано на рис. 4 – двум различным идентификаторам А1и А2соответствуют два совпадающих значения хэш-функции n1=n2.

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

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

Практически существует ограничение, делающее создание взаимно однозначной хэш-функции для идентификаторов невозможным. Дело в том, что в реальности область значений любой хэш-функции ограничена размером доступного адресного пространства в данной архитектуре компьютера. При организации хэш-адресации значение, используемое в качестве адреса таблицы идентификаторов, не может выходить за пределы, заданные адресной сеткой компьютера. Множество адресов любого компьютера с традиционной архитектурой может быть велико, но всегда конечно, т. е. ограничено. Организовать взаимно однозначное отображение бесконечного множества на конечное даже теоретически невозможно. Можно учесть, что длина принимаемой во внимание строки идентификатора в реальных компиляторах также практически ограничена – обычно она лежит в пределах от 32 до 128 символов (т. е. и область определения хэш-функции конечна). Но и тогда количество элементов в конечном множестве, составляющем область определения функции, будет превышать их количество в конечном множестве области значений функции (количество всех возможных идентификаторов все равно больше количества допустимых адресов в современных компьютерах). Таким образом, создать взаимно однозначную хэш-функцию практически ни в каком варианте невозможно. Следовательно, невозможно избежать возникновения коллизий.

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

Для решения проблемы коллизии можно использовать много способов. Одним из них является метод “рехэширования” (или “расстановки”). Согласно этому методу, если для элемента А адрес h(A), вычисленный с помощью хэш-функции, указывает на уже занятую ячейку, то необходимо вычислить значение функции n1=h1(A) и проверить занятость ячейки по адресу n1. Если и она занята, то вычисляется значение h2(А), и так до тех пор, пока либо не будет найдена свободная ячейка, либо очередное значение hi(A) совпадет с h(A). В последнем случае считается, что таблица идентификаторов заполнена и места в ней больше нет – выдается информация об ошибке размещения идентификатора в таблице. Особенностью метода является то, что первоначально таблица идентификаторов должна быть заполнена информацией, которая позволила бы говорить о том, что все ее ячейки являются пустыми (не содержат данных). Например, если используются указатели для хранения имен идентификаторов, то таблицу надо предварительно заполнить пустыми указателями.

Такую таблицу идентификаторов можно организовать по следующему алгоритму размещения элемента.

Шаг 1. Вычислить значение хэш-функции n = h(A) для нового элемента А.

Шаг 2. Если ячейка по адресу n пустая, то поместить в нее элемент А и завершить алгоритм, иначе i:=1 и перейти к шагу 3.

Шаг 3. Вычислить ni= hi(A). Если ячейка по адресу niпустая, то поместить в нее элемент А и завершить алгоритм, иначе – перейти к шагу 4.

Шаг 4. Если n=ni, то сообщить об ошибке и завершить алгоритм, иначе – i:=i+l и вернуться к шагу 3.

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

Шаг 1. Вычислить значение хэш-функции n=h(A) для нового элемента А.

Шаг 2. Если ячейка по адресу n пустая, то элемент не найден, алгоритм завершен, иначе – сравнить имя элемента в ячейке n с именем искомого элемента А. Если они совпадают, то элемент найден и алгоритм завершен, иначе – i:=1 и перейти к шагу 3.

Шаг 3. Вычислить ni= hi(A). Если ячейка по адресу niпустая или n=ni, то элемент не найден и алгоритм завершен, иначе – сравнить имя элемента в ячейке niс именем искомого элемента А. Если они совпадают, то элемент найден и алгоритм завершен, иначе – i:=i+l и повторить шаг 3.

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

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

Самым простым методом вычисления функции hi(A) является ее организация в виде hi(A)=(h(A)+рi) mod Nm, где рi– некоторое вычисляемое целое число, a Nm– максимальное число элементов в таблице идентификаторов. В свою очередь, самым простым подходом здесь будет положить рi=i. Тогда получаем формулу hi(A)=(h(A)+i) mod Nm. В этом случае при совпадении значений хэш-функции для каких-либо элементов поиск свободной ячейки в таблице начинается последовательно от текущей позиции, заданной хэш-функцией h(A).

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

Рассмотрим в качестве примера ряд последовательных ячеек таблицы n1, n2, n3, n4, n5и ряд идентификаторов, которые надо разместить в ней: А1, А2, А3, А4, А5, при условии, что h(A1)=h(A2)=h(A5)=n1; h(A3)=h(A4)=n4. Последовательность размещения идентификаторов в таблице при использовании простейшего метода рехэширования показана на рис. 5. В итоге после размещения в таблице для поиска идентификатора A1потребуется 1 сравнение, для A2– 2 сравнения, для A3– 2 сравнения, для A4– 1 сравнение и для A5– 5 сравнений.

Даже такой примитивный метод рехэширования является достаточно эффективным средством организации таблиц идентификаторов при неполном заполнении таблицы. Имея, например, даже заполненную на 90 % таблицу для 1024 идентификаторов, в среднем необходимо выполнить 5,5 сравнений для поиска одного идентификатора, в то время как даже логарифмический поиск дает в среднем от 9 до 10 сравнений. Сравнительная эффективность метода будет еще выше при росте числа идентификаторов и снижении заполненности таблицы.

Среднее время на помещение одного элемента в таблицу и на поиск элемента в таблице можно снизить, если применить более совершенный метод рехэширования. Одним из таких методов является использование в качестве рiдля функции hi(A)=(h(A)+pi) mod Nmпоследовательности псевдослучайных целых чисел p1, p2, …, pk. При хорошем выборе генератора псевдослучайных чисел длина последовательности k будет k=Nm.

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

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

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

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

Метод цепочек работает по следующему алгоритму.

Шаг 1. Во все ячейки хэш-таблицы поместить пустое значение, таблица идентификаторов не должна содержать ни одной ячейки, переменная FreePtr (указатель первой свободной ячейки) указывает на начало таблицы идентификаторов; i:=l.

Шаг 2. Вычислить значение хэш-функции niдля нового элемента Аi. Если ячейка хэш-таблицы по адресу niпустая, то поместить в нее значение переменной FreePtr и перейти к шагу 5; иначе – перейти к шагу 3.

Шаг 3. Положить j:=1, выбрать из хэш-таблицы адрес ячейки таблицы идентификаторов mjи перейти к шагу 4.

Шаг 4. Для ячейки таблицы идентификаторов по адресу mj, проверить значение поля ссылки. Если оно пустое, то записать в него адрес из переменной FreePtr и перейти к шагу 5; иначе – j:=j+l, выбрать из поля ссылки адрес mjи повторить шаг 4.

Шаг 5. Добавить в таблицу идентификаторов новую ячейку, записать в нее информацию для элемента Аi(поле ссылки должно быть пустым), в переменную FreePtr поместить адрес за концом добавленной ячейки. Если больше нет идентификаторов, которые надо разместить в таблице, то выполнение алгоритма закончено, иначе – i:=i+1 и перейти к шагу 2.

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

Шаг 1. Вычислить значение хэш-функции n для искомого элемента А. Если ячейка хэш-таблицы по адресу n пустая, то элемент не найден и алгоритм завершен, иначе положить j:=1, выбрать из хэш-таблицы адрес ячейки таблицы идентификаторов mj=n.

Шаг 2. Сравнить имя элемента в ячейке таблицы идентификаторов по адресу mjс именем искомого элемента А. Если они совпадают, то искомый элемент найден и алгоритм завершен, иначе – перейти к шагу 3.

Шаг 3. Проверить значение поля ссылки в ячейке таблицы идентификаторов по адресу mj. Если оно пустое, то искомый элемент не найден и алгоритм завершен; иначе – j:=j+l, выбрать из поля ссылки адрес mjи перейти к шагу 2.

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

На рис. 6 проиллюстрировано заполнение хэш-таблицы и таблицы идентификаторов для примера, который ранее был рассмотрен на рис. 5 для метода простейшего рехэширования. После размещения в таблице для поиска идентификатора A1потребуется 1 сравнение, для A2– 2 сравнения, для A3– 1 сравнение, для А4– 1 сравнение и для А5—3 сравнения.

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

Статьи к прочтению:

Excel Magic Trick 1133: Aging Accounts Receivable Reports: PivotTable & Unique Identifier


Похожие статьи: