← На главную

Реализация хэш-таблиц, почти как в Perl

Мне почему-то всегда казалось, что хэши в Perl, несмотря на название, реализованы в виде бинарных деревьев, а не хэш-таблиц. Как бы дико это ни звучало. Вероятно, это связано с тем, что в STL контейнер std::map обычно реализуется в виде красно-черного дерева, и я ошибочно предположил, что в Perl сделано так же. Но недавно я обнаружил, что в книге «Programming Perl» недвусмысленно утверждается обратное.

Интересная особенность хэш-таблиц заключается в том, что для добавления, удаления и поиска элементов им требуется лишь O(1) операций. Тем временем, красно-черным и АВЛ-деревьям для этого нужно O(log(N)) операций. Кроме того, хэш-таблицы намного проще для понимания, чем бинарные деревья поиска.

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

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

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

Найти информацию по теме оказалось несложно. Во-первых, в Perl используется хэш-функция Дженкинса:

/* http://en.wikipedia.org/wiki/Jenkins_hash_function */ 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 имеют переменный размер. Соответствующие источники информации:

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

Писать решил на Си, ибо я давно на нем не писал и надо бы освежить знания языка. Потом, в C++11 появился unordered_map (кстати, у пользователей Boost он есть уже давным-давно), а писать такие вещи для Python или самого Perl попахивает извращением. Интерфейс хэш-таблицы получился довольно очевидным:

/* htable.h (c) Alexandr Alexeev 2011 | http://eax.me/ */ #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; }

Пока все просто. Хэш-таблица должна иметь какой-то минимальный размер, меньше которого она ни при каких обстоятельствах не становится. У меня минимальный размер хэш-таблицы равен восьми элементам.

if(tbl->items > tbl->size) { 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, использованной изначально (хэш-функция Дженкинса была взята на вооружение позднее).

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

if(tbl->items <= (tbl->size / 2)) { 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]; } } }

Аналогичная ветка для случая уменьшения размера хэш-таблицы. Все с точностью до наоборот. Размер хэш-таблицы уменьшается в два раза. Цепочки, находящиеся в первой половине таблицы, копируются, как есть, после чего на новые места перебрасываются цепочки из второй половины хэш-таблицы. Обратите внимание, что перемещаются целые цепочки, а не отдельные элементы. Следует также отметить, что во многих задачах словари (мы же реализуем именно эту абстракцию) не опустошаются, а только пополняются. Соответственно, вам может захотеться выпилить эту ветку.

if(new_size != tbl->size) { 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-скрипт, предназначенный для ее тестирования. Содержание скрипта следующее:

#!/usr/bin/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";

Как собрать и протестировать код:

make perl test.pl > ./input.txt time cat input.txt | ./htable_test > ./test_result.txt

Как минимум, программа должна успешно завершиться. Если не лень, можно поискать в test_result.txt какие-нибудь косяки. Если лень, можно выполнить:

cat test_result.txt | grep 'last_error = 1'

В ответ ничего не должно выводиться. Кому совсем не лень, может протестировать программу вручную. На моем ноутбуке Asus X51L под управлением FreeBSD 8.2 на выполнение всех 1 425 764 операций с хэш-таблицей (учитывая также парсинг команд и работу с вводом-выводом) программе понадобилось три секунды. Это 475 254 операций в секунду или 0.000002 секунды на одну операцию. По-моему, совсем неплохо.

Дополнение: Исходники к этой заметке теперь также доступны и на GitHub. Приведенная в этой заметке реализация устарела. Более совершенная реализация, разработанная в рамках работы над Не унылом постом о списках и деревьях поиска в языке C, доступна в этом репозитории на GitHub.