Реализация хэш-таблиц, почти как в Perl
Мне почему-то всегда казалось, что хэши в 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://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;
}
Пока все просто. Хэш-таблица должна иметь какой-то минимальный размер, меньше которого она ни при каких обстоятельствах не становится. У меня минимальный размер хэш-таблицы равен восьми элементам.
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 секунды на одну операцию. По-моему, совсем неплохо.
Собственно, это все, о чем я хотел написать. Как обычно, я буду рад любым комментариям и постараюсь ответить на возникшие у вас вопросы./span