Алгоритмы хеширования занимают особое место в сердцах программистов. Они изучаются в началах информатики, поэтому это наиболее доступные алгоритмы и конечно их приятно ваять. Кроме того, как бесконечный поиск Святого Грааля, поиск совершенной хэш-функции для заданного набора данных, все еще имеет значительную паству в каждом годовом наборе журналов по информатике. Для тех разработчиков, которые программируют для заработка, однако, неясные усовершенствования к необычным хеш-функциям, имеют небольшое применение. Вообще, когда Вы нуждаетесь в хэш-таблице, Вы хотите, конечно же, быструю и удобную хеш-функцию. И если Вы знаете, где взять ее, то Вы почти точно станете жертвой той ошибки, что Вы якобы можете написать и оптимизировать ее быстро для вашего заданного приложения.
В этой статье, я буду обсуждать хороший, универсальный алгоритм хеширования, а затем проведу анализ, как хеширование может быть сделано более эффективным. В заключение, я буду исследовать удивительный эффект аппаратных усовершенствований хеширования - в частности разницу между производительностью ЦПУ и латентностью памяти.
Основы
Хэш-таблицы похожи на большинство таблиц (старомодное слово для "массивов"). Таблица становится хэш-таблицей, когда к заданному элементу осуществляется непоследовательный доступ с помощью хэш-функции. В хэш-функцию, в общем, передается элемент данных, который она преобразовывается в целое число, которое используется как индекс в таблице. Например, если Вы имеете хэш-таблицу, в которую Вы хотели бы сохранить даты, Вы могли бы брать Юлианскую дату (положительное целое число прошедших дней с 1 января 4713 г. до нашей эры) и делить эту дату на размер хэш-таблицы. Остаток, названый "хэш-ключ", и будет ваш индекс в хэш-таблице.
В закрытой хэш-таблице, хэш-ключ - индекс элемента, в котором Вы сохраняете дату и данные, связанные с этой датой. Если слот в таблице занят другой датой (это называется "коллизия"), Вы можете или генерировать другой хэш-ключ (называется "нелинейное перехеширование") или найти в таблице доступный слот (линейное перехеширование).
В открытой хэш-таблице (более общий случай), каждый элемент в таблице - голова связанного списка элементов данных. В этой модели, коллизия обрабатывается, при помощи добавления элемента коллизии к списку, который начинает в слоте таблицы, куда ссылаются оба ключа. Этот подход имеет преимущество, что таблица не ограничивает числом элементов, которые таблица может содержать, в то время как закрытая таблица не может содержать большее количество элементов данных, чем элементов в таблице.
Хэш-Функции
Хеширование полезно там, где необходимо большой диапазон возможных значений сохранить в небольшом объеме памяти, и отыскать простым, почти произвольным доступом. Также, хэш-таблицы часто используются в базах данных и, особенно в языковых процессорах типа компиляторов и ассемблеров, где они обслуживают таблицы идентификаторов. В таких приложениях, хэш-таблица - принципиальная структура данных. Так как всякий доступ к таблице должен быть выполнен через хэш-функцию, то она должна удовлетворять двум требованиям: она должна работать быстро, и выдавать хорошие ключи распределения по таблице. Последнее требование минимизирует коллизии и предотвращает хеширование элементов с одинаковыми значениями ключей только в одной части таблицы.
/*--- HashPJW --------------------------------------------------- *
Адаптация обобщенного алгоритма хеширования Питера Вейнбергер (PJW) *
Основанного на версии Аллена Холуба. Принимает указатель на *
элемент данных datum, и возвращает хэш как целое без знака *
----------------------------------------------------------------------*/
#include <limits.h>
#define BITS_IN_int ( sizeof(int) * CHAR_BIT )
#define THREE_QUARTERS ((int) ((BITS_IN_int * 3) / 4))
#define ONE_EIGHTH ((int) (BITS_IN_int / 8))
#define HIGH_BITS ( ~((unsigned int)(~0) >> ONE_EIGHTH ))
unsigned int HashPJW
( const char * datum )
{
unsigned int hash_value, i;
for ( hash_value = 0; *datum; ++datum )
{
hash_value = ( hash_value << ONE_EIGHTH ) + *datum;
if (( i = hash_value & HIGH_BITS ) != 0 )
hash_value = ( hash_value ^ ( i >> THREE_QUARTERS )) & ~HIGH_BITS;
}
return ( hash_value );
}
Пример 1: HashPJW (). Адаптация обобщенного алгоритма хеширования Питера Вейнбергера.
В большинстве программ, время работы хэш-функции незначительное. Фактически, трудно написать реальную программу, в которой хэш-функция отнимает один процент от времени выполнения всей программы. Если ваш профилировщик сообщает Вам иначе, Вы должны заменить эту хэш-функцию. Я представляю здесь две превосходных, универсальных хэш-функции. Функция HashPJW () (пример 1) основана на работе Питера Вейнбергера из AT&T Bell Labs, и широко известна. Функция ElfHash () (пример 2) - вариант HashPJW (), который используется в объектных файлах UNIX формата ELF. Функции принимают указатель на строку и возвращают целое число. Конечный хэш-ключ получается как остаток от деления этого ключа на размер таблицы. Переносимая версия алгоритма Вейнбергера в примере 1 относится к Аллену Холубу. К сожалению, версия Холуба содержит ошибку, которая была выявлена в более поздних работах (включая первое издание «Practical Algorithms for Programmers» Джона Рекса и меня). Ошибка не препятствует работе, она просто дает неоптимальный хэш. Версия в примере 1 правильная. Пример 2 взят из спецификации "System V Application Binary Interface". Этот алгоритм иногда содержит опечатки (смотри “Programming in Standard C” для UnixWare, например) в форме, которая дает очень плохие результаты. Версия I представленная здесь правильная.
/*--- ElfHash --------------------------------------------------- *
Опубликованный алгоритм хэша использованный в формате ELF для
Объектных файлов UNIX. Принимает указатель на строку текста,
Хэширует ее и возвращает unsigned long.
-----------------------------------------------------------------*/
unsigned long ElfHash
( const unsigned char *name )
{
unsigned long h = 0, g;
while ( *name )
{
h = ( h << 4 ) + *name++;
if ( g = h & 0xF0000000 ) h ^= g >> 24;
h &= ~g;
}
return h;
}
Пример 2. Elfhash(). Опубликованный алгоритм хэша использованный в формате ELF для объектных файлов UNIX.
Обе функции быстродействующие, так как выполняют только поразрядные операции. Не выполняется никаких арифметических действий, и входные данные должны быть по-байтно.
Так как программа тратит мало времени на хеширование, Вы не должны шаманить алгоритм, чтобы еще оптимизировать производительность. Вы должны сосредоточиться на качестве генерируемых хэш-ключей. Чтобы сделать это нам понадобится маленькая программа, которая будет хэшировать набор данных и печатать статистику о качестве хэша. Исходные коды программы wordlist.exe можно смотри в конце статьи. Она проверит наши функции. Файл также содержит тестовые данные. Программа читает текстовый файл и сохраняет каждое уникальное слово и счетчик повторений в хэш-таблицу. Несколько параметров командной строки (все документированы) позволяют Вам определить размер хэш-таблицы, печатать таблицу статистики, и даже печатать все уникальные слова и их счетчики.
Эта тестовая программа показывает, что два алгоритма превосходно распределяют хэш-значения в таблице. В 16-разрядных средах, HashPJW () незначительно лучше при хешировании текста, в то время как ElfHash () значительно лучше в хешировании чисел. В 32-разрядных средах, алгоритмы идентичны.
Производительность
Так как скорость алгоритма очень хорошая, то надо обратить внимание на качество генерирования хэш-ключей. Однако нужно учесть ряд обстоятельств. Даже программы, в которых интенсивно используется хэш (компиляторы не фигурируют в этой группе) не станут быстрее больше, чем на 4 или 5 процентов с созданием более совершенного хэш-алгоритма. А так как, если в самом лучшем случае улучшение составит всего 5 процентов, то, конечно же, настройка хэш-функции будет одной из последних возможных оптимизации, которые Вы выполняете. При этом надо учесть, что настройка хэша требует значительного эмпирического тестирования: Вы не хотите улучшить производительность с одним набором данных, при этом значительно ухудшить ее на другом.
Поэтому, если у Вас не исключительный набор данных, используйте одну из вышеупомянутых функций. Отдельные аспекты вашей хэш-таблицы могут быть легко настроены, чтобы улучшить производительность.
Во-первых, в вашей таблице должно быть простое число слотов. Как упоминалось выше, заключительный хэш-индекс равен остатку от деления хэш-значения на размер таблицы. Максимальное рассеивание по таблице будет тогда, когда хэш-значение и размер таблицы простые числа (нет общих делителей), при этом проще гарантировать, что размер таблицы - простое число. Например, хеширование Библии, которая состоит из 42,829 уникальных слов, в открытую хэш-таблицу с 30,241 элементами (простое число) показывает, что 76.6 процентов от слотов использовался, и что средняя цепочка была 1.85 слова длиной на один слот (с максимумом 6). При хешировании того же самого файла с хэш-таблицей в 30,240 элементов (число, которое делиться на целые числа от 2 до 9) заполняется только 60.7 процентов от слотов, и средняя цепочка - 2.33 слова длиной (максимум: 10). Это довольно значимое улучшение просто сделав размер таблице простым числом.
Во-вторых, простое улучшение - это увеличение размера хэш-таблицы. Эта классическая оптимизация будет эффективна, только тогда, когда набор данных имеет большее количество элементов, чем ваша хэш-таблица. (Я все еще рассуждаю об открытых хэш-таблицах, закрытые хэш-таблицы будут обсуждены ниже.) Возвращаясь к примеру с Библией, когда она была прохэширована (с HashPJW) в таблицу из 7561 элементов, 99.7 процентов от слотов было занято, и средняя цепочка была 5.68 слов длиной; в 15,121 элементах, размещение было 93.9 процента, и средняя цепочка была 3.01 слова. Значения для таблицы из 30,241 элементов уже приводились. Исходя из этого примера, можно сделать вывод что, увеличивая в четыре раза размер таблицы, почти на два делим длину цепочки. Конечно, хэш-операции играют небольшую роль в скорости программы, поэтому улучшение будет только на 1.7 процента. Однако, если выполняются и другие оптимизации, это различие может быть значимо.
В заключение, будьте внимательными с конструкцией связанных списков, исходящих от таблицы. Значительное уменьшение дефрагментизации памяти может быть достигнуто, не распределяя память, каждый раз под элемент данных при добавлении его в таблицу, а используя объединение узлов, распределенных как один блок. Аналогично, списки нужно упорядочивать, или по возрастанию значения или по частоте доступа. Таблицы идентификаторов компилятора, например, часто помещают узел, к которому было последнее обращение в начало списка, по теории, обращения к какой-то переменной имеет тенденцию группироваться вместе. Этот особенно заметно в языках типа C и Паскаль, которые имеют локальные переменные.
Таблица 1. Результаты хэширования Библии с 42,829 уникальными словами:
|
Размер таблицы |
Процент использованных слотов |
Средняя цепочка |
Максимальная цепочка |
|
30,240 |
60.7 |
2.33 |
10 |
|
30,241 |
76.6 |
1.85 |
6 |
|
7561 |
99.7 |
5.68 |
- |
|
15,121 |
93.9 |
3.01 |
- |
Закрытые хэш-таблицы
Как упомянуто выше, есть два основных метода разрешения коллизий при хешировании в закрытых таблицах - линейное перехеширование или нелинейное перехеширование. Идея нелинейного перехеширования в том, чтобы рассредоточить коллизии по таблице.
Закрытые хэш-таблицы особенно эффективны, когда максимальный размер входящего набора данных известен, и можно создать таблицу с намного большим количеством элементов. Доказано, что, если только закрытая таблица становится полной более, чем 50 процентов, то производительность ее резко падает (смотри “Data Structures and Program Design in C”, Роберт Крус, Брюс Леунг, и Кловис Тондо, Prentice Hall, 1991). Закрытые таблицы обычно используются для быстрого создания прототипов (их просто закодировать) и где важен быстрый доступ (нет связанного списка), и есть достаточно памяти.
Из традиционной информатики известно, что при заданной равной загрузке (отношение занятых слотов к размеру таблицы), хэш-таблицы лучше работают при использовании нелинейного перехеширования чем, при проходе через таблицу. Эта точка зрения вообще была принята без больших дебатов, потому что математически это неоспоримо.
Однако, аппаратные усовершенствования (всех вещей!) начинают изменяться математику пользу линейного перехеширования. Особенно, по причине латентности памяти и наличию кэша ЦПУ.
Латентность памяти
Новейшие ЦПУ сегодня обычно функционируют на частотах более 250 MHz. На таких частотах, каждый цикл команды занимает менее 4 наносекунд. По сравнению, самая быстрая оперативная память имеет частоту выборки в 60 наносекунд. В действительности, это означает, что один цикл выборки из памяти - приблизительно в 15 раз медленнее, чем выполнение команды на ЦПУ. Исходя из этой разницы, Вы можете понять, что ваши программы должны избегать выборок из памяти в максимально возможной степени.
Большинство ЦПУ сегодня имеет встроенную кэш-память, и большинство программ во время выполнения чаще всего использует эту память, чем общую динамическую память. От кэш-памяти есть польза только тогда, когда данные, к которым Вы должны обратиться уже в кэше (когда это происходит, Вы имеете ”попадание” в кэш). Во время кэширования есть тенденция сохранять блоки данных, задействованных в предыдущих операциях, и эти блоки имеют тенденцию включать данные больше байта или байтов, которые используются для одной команды. В результате, удачные попадания в кэш увеличатся, если Вы обращаетесь к смежным байтам в последующих командах. Следовательно, Вы будете иметь гораздо большее количество удачных попаданий в кэш, если Вы используете линейное перехеширование и просто сделаете запрос смежного элемента таблицы чем, если Вы используете нелинейное перехеширование.
Насколько значительна эта разница? Программа memtime.c показывает Вам эффекты с латентностью памяти (латентность – это задержка или время отклика). Она распределяет заданный блок и читает каждый байт. На первом проходе, она читает хаотично; на втором она читает последовательно. В таблице 2 представлены результаты для 10 миллионов чтений из таблицы размером 10 Мб.
Таблица 2. Результаты для 10 миллионов чтений из 10 Мб таблицы.
|
Процессор/Память |
Последовательное |
Случайное |
|
100-MHz Pentium/60-ns память |
1 секунд |
7 секунд |
|
66-MHz Cyrix 486/70-ns память |
2 секунд |
9 секунд |
Очевидно, соотношение становится еще более неблагоприятным, когда программа выполняется на операционных системах со страничной организацией памяти, типа UNIX. Когда предыдущая программа была выполнена на 486/66-MHz PC с 70-ns памятью, в среде UnixWare, последовательное чтение заняло 3 секунды, а случайное чтение, заняло 35 секунд.
Замечание для ясности: Обращения к памяти, которые происходят вместе, должны быть расположены вместе.
Вы могли бы возразить, что экономия горсточки секунд при 10 миллионов доступах к памяти едва стоит усилий. Во многих случаях это будет истинно. Тем не менее, кодирование этой оптимизации это простой вопрос выбора между равными усилиями (как в случае разных подходов к перехешированию). Кроме того, есть признаки того, что быстродействие ЦПУ продолжает увеличиваться, в то время как скорости выборки из памяти остались неизменными в течение нескольких лет. Со временем, выгода от учета латентности памяти увеличится.
В случае перехеширования, линейный подход имеет дополнительный плюс: новый хэш-ключ не должен быть вычислен. Поэтому для закрытых хэш-таблиц, которые бывают редко заполненными и используют линейное перехеширование.
Латентность память может быть значимой и в других областях программирования. Помните об этом, когда кодируете.
Благодарности
Я благодарю Маршала К. МакКусик и Джона Маша за их идеи, Джона Рекса и Ральфа Баркера за помощь в улучшении статьи.
© Андрей Бинсток - шеф редактор “UNIX Review” и
соавтор книги Practical Algorithms for Programmers (Addison-Wesley, 1995).
Его электронный адрес: abinstock@mfi.com.