Перемешивание кукушки в C

Question

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

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

Answer 1

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

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

Answer 2

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

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

-Adam

Answer 3

http://www.mpi -inf.mpg.de / ~ Сандерс / программы / Кукушка /

НТН

Answer 4

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

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

Answer 5

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

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

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

Answer 6

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

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

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

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

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

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

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

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

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

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

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

и т.д.

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

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

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

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

Answer 7

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

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

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

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

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

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

В хеш-таблице у меня будет:

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

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

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

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

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

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

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

Answer 8

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