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

6 декабря 2011

Мне почему-то всегда казалось, что хэши в 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 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;
  }

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

  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.

Метки: , .


Вы можете прислать свой комментарий мне на почту, или воспользоваться комментариями в Telegram-группе.