Мне почему-то всегда казалось, что хэши в Perl, несмотря на название, реализованы в виде бинарных деревьев, а не хэш-таблиц . Как бы дико это ни звучало. Вероятно, это связано с тем, что в STL контейнер std::map обычно реализуется в виде красно-черного дерева, и я ошибочно предположил, что в Perl сделано так же. Но недавно я обнаружил, что в книге «Programming Perl» недвусмысленно утверждается обратное.
Интересная особенность хэш-таблиц заключается в том, что для добавления, удаления и поиска элементов им требуется лишь O(1) операций. Тем временем, красно-черным и АВЛ-деревьям для этого нужно O(log(N)) операций. Кроме того, хэш-таблицы намного проще для понимания, чем бинарные деревья поиска.
К недостаткам хэш-таблиц относится невозможность быстро получить отсортированный список ключей. Также остается множество открытых вопросов касательно реализации. Например, каким конкретно образом разрешать коллизии и какую конкретно функцию хэширования выбрать? Что делать с элементами хэш-таблицы при изменении ее размера в случае, если этот самый размер не фиксирован? Не перестраивать же всю хэш-таблицу с нуля?
Чтобы получить ответы на эти вопросы (программисты бывают такими любопытными, знаете ли), я решил разобраться в том, как именно устроены хэши в Perl. В конце концов, хэши являются одним из основных типов данных в Perl и они выдержали серьезную проверку временем. Какая еще реализация хэш-таблиц может претендовать на звание наиболее универсальной, быстрой и устойчивой к коллизиям?
Примечание: Почему-то в некоторой литературе и в названиях статей на русскоязычной Вики используется слово х е ш, хотя на той же Вики уже в тексте это слово пишется через «э», х э ш. Согласно гуглу, оба написания используются примерно с одинаковой частотой. На мой взгляд, ответ на вопрос «как правильно писать?» содержится в текстах российских ГОСТов . Следует писать х э ш, х э ширование, х э ш-таблица , х э ш-функция .
Найти информацию по теме оказалось несложно. Во-первых, в Perl используется хэш-функция Дженкинса :
uint32_t _htable_hash ( const char * key , const size_t key_len ) {
uint32_t hash , i ;
for ( hash = i = 0 ; i < key_len ; ++ i ) {
hash += key [ i ] ;
hash += ( hash << 10 ) ;
hash ^= ( hash >> 6 ) ;
}
hash += ( hash << 3 ) ;
hash ^= ( hash >> 11 ) ;
hash += ( hash << 15 ) ;
return hash ;
}
Она отличается своей простотой, скоростью и устойчивостью к коллизиям. Также существует оптимизированный вариант для ключей большой длины. Подробнее о хэш-функции Дженкинса можно прочитать в статье самого Боба Дженкинса для журнала Dr Dobbs .
Во-вторых, для разрешения коллизий используются цепочки. В-третьих, хэш-таблицы в Perl имеют переменный размер. Соответствующие источники информации:
- Статья How Hashes Really Work на сайте perl.com;
- Обсуждение Implementation of perl hashes на perlmonks.org;
- Файл hv.c из исходного кода Perl 5.14.0;
Если вы попробуете почитать hv.c, то обнаружите, что он довольно сложен для восприятия. В связи с этим на данном этапе я решил покончить с теорией и перейти к практике. То есть, написать свою реализацию хэш-таблицы переменного размера и убедиться, что она работает достаточно хорошо.
Писать решил на Си, ибо я давно на нем не писал и надо бы освежить знания языка. Потом, в C++11 появился unordered_map (кстати, у пользователей Boost он есть уже давным-давно), а писать такие вещи для Python или самого Perl попахивает извращением. Интерфейс хэш-таблицы получился довольно очевидным:
htable.h
(c) Alexandr A Alexeev 2011 | http://remontka.com/
*/
#include <stdint.h>
#include <stdbool.h>
enum htable_error {
HTABLE_ERROR_NONE ,
HTABLE_ERROR_NOT_FOUND ,
HTABLE_ERROR_MALLOC_FAILED ,
} ;
/* элемент хэш-таблицы */
struct htable_item {
uint32_t hash ; /* значение хэш-функции */
char * key ; /* ключ */
size_t key_len ; /* длина ключа */
int value ; /* значение */
struct htable_item * next ; /* следующий элемент в цепочке */
} ;
/* хэш-таблица */
struct htable {
uint32_t mask ; /* маска, применяемая к хэш-функции */
size_t size ; /* текущий размер хэш-таблицы */
size_t items ; /* сколько элементов хранится в хэш-таблице */
enum htable_error last_error ; /* ошибка в последней операции */
struct htable_item ** items_table ; /* элементы */
} ;
struct htable * htable_new ( void ) ;
void htable_free ( struct htable * tbl ) ;
bool htable_get ( struct htable * tbl ,
const char * key , const size_t key_len , int * value ) ;
bool htable_set ( struct htable * tbl ,
const char * key , const size_t key_len , const int value ) ;
bool htable_del ( struct htable * tbl ,
const char * key , const size_t key_len ) ;
Что интересно, уже после написания кода я заглянул в исходники Perl 1.0 и увидел там примерно то же самое. Итак, код хэш-функции уже был приведен выше, а реализация htable_get, htable_set и htable_del вполне очевидна. Самое интересное делает функция _htable_resize (нет в заголовочном файле), вызываемая после каждого успешного добавления или удаления элемента в хэш-таблицу . Рассмотрим ее по частям:
false в случае ошибки */
bool _htable_resize ( struct htable * tbl ) {
struct htable_item ** new_items_table ;
struct htable_item * curr_item , * prev_item , * temp_item ;
size_t item_idx , new_size = tbl -> size ;
uint32_t new_mask ;
if ( tbl -> items < MIN_HTABLE_SIZE ) {
tbl -> last_error = HTABLE_ERROR_NONE ;
return true ;
}
Пока все просто. Хэш-таблица должна иметь какой-то минимальный размер, меньше которого она ни при каких обстоятельствах не становится. У меня минимальный размер хэш-таблицы равен восьми элементам.
new_size = tbl -> size * 2 ;
new_mask = new_size — 1 ;
new_items_table = malloc ( new_size * sizeof ( struct htable_item * ) ) ;
if ( new_items_table == NULL ) {
tbl -> last_error = HTABLE_ERROR_MALLOC_FAILED ;
return false ;
}
/* первую половину тупо копируем */
memcpy ( new_items_table , tbl -> items_table , tbl -> size *
sizeof ( struct htable_item * ) ) ;
/* вторую половину пока что заполняем нулями */
memset ( & new_items_table [ tbl -> size ] , 0 , tbl -> size *
sizeof ( struct htable_item * ) ) ;
for ( item_idx = 0 ; item_idx < tbl -> size ; item_idx ++ ) {
prev_item = NULL ;
curr_item = new_items_table [ item_idx ] ;
while ( curr_item != NULL ) {
if ( ( curr_item -> hash & tbl -> mask ) !=
( curr_item -> hash & new_mask ) ) {
if ( prev_item == NULL ) {
new_items_table [ item_idx ] = curr_item -> next ;
} else {
prev_item -> next = curr_item -> next ;
}
temp_item = curr_item -> next ;
curr_item -> next = new_items_table [ curr_item -> hash & new_mask ] ;
new_items_table [ curr_item -> hash & new_mask ] = curr_item ;
curr_item = temp_item ;
} else {
prev_item = curr_item ;
curr_item = curr_item -> next ;
}
} /* while */
} /* for */
}
Если число элементов превысило размер хэш-таблицы , удваиваем размер хэш-таблицы . Что интересно, в последних версиях интерпретатора Perl используется такой же критерий удвоения размера таблицы, но в Perl 1.0 использовался критерий «если хэш-таблица заполнена более, чем на 60%». Вероятно, это было связано с несовершенством хэш-функции DJBX33A , использованной изначально ( хэш-функция Дженкинса была взята на вооружение позднее).
Обратите внимание, что лишь половина элементов нуждается в перемещении. Поскольку размер хэш-таблицы всегда равен степени двойки, значение хэш-функции каждого элемента при увеличении таблицы становится длиннее на один бит. Те элементы, у которых дополнительный бит оказался нулем, уже находятся на своем месте, и лишь остальные (примерно половина) нуждаются в перемещении. Если бы мы использовали хэш-таблицы , размер которых представлял собой простое число, а такое решение иногда рекомендуют в умных книжках, перемещать пришлось бы почти все элементы.
new_size = tbl -> size / 2 ;
new_mask = new_size — 1 ;
new_items_table = malloc ( new_size * sizeof ( struct htable_item * ) ) ;
if ( new_items_table == NULL ) {
tbl -> last_error = HTABLE_ERROR_MALLOC_FAILED ;
return false ;
}
memcpy ( new_items_table , tbl -> items_table , new_size *
sizeof ( struct htable_item * ) ) ;
for ( item_idx = new_size ; item_idx < tbl -> size ; item_idx ++ ) {
if ( tbl -> items_table [ item_idx ] == NULL )
continue ;
if ( new_items_table [ item_idx — new_size ] == NULL ) {
new_items_table [ item_idx — new_size ] = tbl -> items_table [ item_idx ] ;
} else {
curr_item = new_items_table [ item_idx — new_size ] ;
while ( curr_item -> next != NULL ) {
curr_item = curr_item -> next ;
}
curr_item -> next = tbl -> items_table [ item_idx ] ;
}
}
}
Аналогичная ветка для случая уменьшения размера хэш-таблицы . Все с точностью до наоборот. Размер хэш-таблицы уменьшается в два раза. Цепочки, находящиеся в первой половине таблицы, копируются, как есть, после чего на новые места перебрасываются цепочки из второй половины хэш-таблицы . Обратите внимание, что перемещаются целые цепочки, а не отдельные элементы. Следует также отметить, что во многих задачах словари (мы же реализуем именно эту абстракцию) не опустошаются, а только пополняются. Соответственно, вам может захотеться выпилить эту ветку.
free ( tbl -> items_table ) ;
tbl -> items_table = new_items_table ;
tbl -> size = new_size ;
tbl -> mask = new_mask ;
}
tbl -> last_error = HTABLE_ERROR_NONE ;
return true ;
}
Наконец, если размер хэш-таблицы изменился в ту или иную сторону, подменяем ссылку на таблицу, после чего обновляем ее размер и значение маски. Хочу обратить внимание на одну особенность приведенного кода. Если добавить в хэш-таблицу число элементов, равное степени двойки, затем добавить еще один элемент, удалить один элемент, снова добавить, снова удалить и так далее, то при каждой операции добавления и удаления будет происходить изменение размера хэш-таблицы . Следует немного изменить логику функции _htable_resize в случае, если для вашего приложения такая ситуация имеет большую вероятность. Или если злоумышленник может попытаться таким образом атаковать приложение.
Дополнение: Если вам кажется маловероятной возможность такой атаки, обратите внимание на новость о способе DoS-атаки, затрагивающем PHP, Java, Ruby, ASP.NET и Python (но не Perl).
Полную версию исходников можно скачать здесь . В комплекте вы найдете демонстрационную программу и Perl-скрипт , предназначенный для ее тестирования . Содержание скрипта следующее:
use strict ;
my $i = 0 ;
for ( «a» .. «zzzz» ) {
++ $i ;
print «set $_ $i n » ;
}
for my $cmd ( qw/get del/ ) {
print «$cmd $_ n » for ( «a» .. «zzzz» ) ;
}
print «aaaa n » ;
print «quit» ;
Как собрать и протестировать код:
perl test.pl > . / input.txt
time cat input.txt | . / htable_test > . / test_result.txt
Как минимум, программа должна успешно завершиться. Если не лень, можно поискать в test_result.txt какие-нибудь косяки. Если лень, можно выполнить:
В ответ ничего не должно выводиться. Кому совсем не лень, может протестировать программу вручную. На моем ноутбуке Asus X51L под управлением FreeBSD 8.2 на выполнение всех 1 425 764 операций с хэш-таблицей (учитывая также парсинг команд и работу с вводом-выводом) программе понадобилось почти ровно три секунды. Это 475 254 операций в секунду или 0.000002 секунды на одну операцию. По-моему, совсем неплохо.
Собственно, это все, о чем я хотел написать. Как обычно, я буду рад любым комментариям и постараюсь ответить на возникшие у вас вопросы.
Дополнение: Исходники к этой заметке теперь также доступны и на GitHub . Приведенная в этой заметке реализация устарела. Более совершенная реализация, разработанная в рамках работы над Не унылом постом о списках и деревьях поиска в языке C , доступна в этом репозитории на GitHub .
