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

Question

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

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

Answer 1

http://www.mpi-inf.mpg.de/~sanders/programs/cuckoo/

НТН

Answer 2

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

Адрес code generator for cuckoo hash tables. Проверьте лицензию генератора, чтобы убедиться, что выход не является GPL. Должно быть, но все равно проверьте.

-Adam

Answer 3

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

Answer 4

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

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

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

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

Так, предполагающие указатели имеют одинаковый размер ы, для хранения п пунктов мне потребуется 4 сек байт.

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

В Hashtable я бы:

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

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

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

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

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

Кстати, d-ary cuckoo hashing и «cuckoo hashing with a stash», по-видимому, способны увеличить коэффициент нагрузки, сохраняя при этом постоянное время доступа.

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

Answer 5

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

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

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

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

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

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

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

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

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

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

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

т.д.

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

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

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

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

Answer 6

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

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

Answer 7

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

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

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

Answer 8

Несмотря на то, что это старый вопрос, кто-то еще может быть заинтересованы :)

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