Хеширование кукушки в C

Есть ли у кого-нибудь реализация хэширование кукушки в C? Если бы была версия с открытым исходным кодом, а не с GPL, она была бы идеальной!

Поскольку Адам упомянул об этом в своем комментарии, кто-нибудь знает, почему он мало используется? Это просто вопрос реализации или хорошие теоретические свойства на практике не реализуются?

Ответы

Ответ 2

Как указывали другие ответы, верно, что простейшая хеш-таблица cuckoo требует, чтобы таблица была наполовину пустой. Однако концепция была обобщена на хеширование кукушки d-ary, в которой каждый ключ имеет d возможных мест для гнездования, в отличие от двух мест в простой версии.

Допустимый коэффициент загрузки быстро увеличивается с увеличением d. Только для d = 3 вы уже можете использовать около 75% полной таблицы. Недостатком является то, что вам нужны независимые хеш-функции. Я поклонник хэш-функций Боба Дженкинса для этой цели (см. http://burtleburtle.net/bob/c/lookup3.c), которые могут оказаться полезными в реализации хэширования кукушки.

Ответ 3

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

Вот генератор кода для хеш-таблиц кукушки. Проверьте лицензию генератора, чтобы убедиться, что выход не является GPL. Это должно быть, но все равно проверьте.

-Adam

Ответ 4

Даже если это старый вопрос, кому-то все равно может быть интересно:)

В этой статье описывается реализация параллельного d-ary хэша кукушки на графических процессорах (CUDA/OpenCL). Это описано очень хорошо, и его реализация на основе описания довольно проста. В общем, стоит прочитать, если вас интересует эта тема. (Вам потребуется логин ACM, хотя.)

Ответ 5

Язык ввода-вывода имеет один, в PHash.c. Вы можете найти код для ввода-вывода в Github. IO лицензируется BSD.

Ответ 6

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

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

Для двоичного дерева я бы:

struct node {
  void *key;
  void *value;
  struct node *left;
  struct node *right;
}

Итак, если указатели имеют одинаковый размер s, чтобы сохранить n элементов, мне понадобятся 4 байта.

Скописты почти такие же, как среднее число указателей в node равно 2.

В хэш-таблице я бы:

struct slot {
  void *key;
  void *value;
}

Таким образом, каждый элемент будет содержать только 2 байта, которые будут сохранены. Если коэффициент загрузки равен 50%, для хранения n элементов мне понадобятся те же байты размером 4 байта, что и деревья.

Мне не кажется слишком плохо: хеш-таблица cuckoo будет занимать более или менее тот же объем памяти, что и двоичное дерево, но даст мне O (1) время доступа, а не O (log n).

Не считая сложность сохранения сбалансированного дерева и дополнительной информации, которая может потребоваться для хранения балансировочной информации в node.

Другие схемы хэширования могут обеспечить лучший коэффициент загрузки (например, 75% или 80%) без гарантии на время доступа наихудшего случая (что может быть даже O (n)).

Кстати, d-ary cushoo hashing и " хэширование кукушки с кошельком ", похоже, способно увеличить коэффициент загрузки, сохраняя при этом постоянное время доступа.

Хеширование кукушки кажется мне ценной техникой, и я думал, что это уже изучено; что причина моего вопроса.

Ответ 7

После комментария от "onebyone", я внедрил и протестировал пару версий хэширования кукушки, чтобы определить реальную потребность в памяти.

После некоторого эксперимента претензии, которые вам не нужно развернуть до тех пор, пока таблица не будет заполнена почти на 50%, кажется правдой, особенно если " stash" трюк".

Проблема заключается в том, что вы увеличиваете таблицу. Обычный подход заключается в удвоении его размера, но это приводит к тому, что новая таблица используется только на 25%!

Фактически, предположим, что хэш-таблица имеет 16 слотов, когда я вставляю восьмой номер элемента, у меня заканчиваются хорошие слоты и вам придется разворачиваться. Я удвою его, и теперь на столе будет 32 слота, из которых только 8 из них заняты, что составляет 75% отходов!

Это цена, которую нужно заплатить за "постоянное" время поиска (в терминах верхней границы для количества доступа/сравнения).

Я разработал другую схему: начиная с мощности 2 больше, чем 1, если таблица имеет n слотов, а n - мощность в два, добавьте n/2 слота otherwhise, добавив n/3 слота:

+--+--+
|  |  |                             2 slots
+--+--+

+--+--+--+
|  |  |  |                          3 slots
+--+--+--+ 

+--+--+--+--+
|  |  |  |  |                       4 slots
+--+--+--+--+

+--+--+--+--+--+--+
|  |  |  |  |  |  |                 6 slots
+--+--+--+--+--+--+

+--+--+--+--+--+--+--+--+
|  |  |  |  |  |  |  |  |           8 slots
+--+--+--+--+--+--+--+--+

и др.

Вместе с предположением, что перезагрузка произойдет только тогда, когда таблица заполнена на 50%, это приводит к тому, что таблица будет только на 66% пустой (1/3), а не на 75% пустой (1/4) после (т.е. наихудший случай).

Я также выяснил (но мне все еще нужно проверить математику), каждый раз увеличивая значение sqrt (n), потерянное пространство асимптотически приближается к 50%.

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

Я буду исследовать дальше, если кто-то заинтересован.

Ответ 8

Я не могу говорить о программном обеспечении, но хеширование кукушки, безусловно, используется в аппаратных средствах и становится очень популярным. Крупные поставщики сетевого оборудования изучали хеширование кукушки, а некоторые уже используют его. Притяжение к хэшированию кукушки происходит, конечно, из постоянного времени поиска, но также и с близким постоянным временем вставки.

Хотя теоретическая вставка теоретически может быть неограниченной, на практике она может быть ограничена значением O (log n) числа строк в таблице (таблицах), а при измерении время вставки составляет около 1,1 * d доступа к памяти в среднем. Это всего на 10% больше абсолютного минимума! Доступ к памяти часто является ограничивающим фактором в сетевом оборудовании.

Независимые хеш-функции являются обязательными и правильно их выбраны. Удачи.