Хеширование Cuckoo в C
https://stackoverflow.com/questions/231438
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Есть ли у кого-нибудь реализация Хеширование с кукушкой в С?Если бы существовала версия с открытым исходным кодом, не под лицензией GPL, это было бы идеально!
Поскольку Адам упомянул об этом в своем комментарии, кто-нибудь знает, почему он мало используется?Это просто вопрос реализации или хорошие теоретические свойства не реализуются на практике?
Другие советы
Как указывали другие ответы, верно, что самый простой хеш-стол кукушки требует, чтобы таблица была наполовину пустой. Однако концепция была обобщена на d -ное хеширование кукушки, в котором каждый ключ имеет d возможные места для вложения, в отличие от 2 мест в простой версии.
Приемлемый коэффициент загрузки быстро увеличивается при увеличении d . Только для d = 3 вы уже можете использовать около 75% заполненной таблицы. Недостатком является то, что вам нужны d независимые хеш-функции. Я фанат хеш-функций Боба Дженкинса для этой цели (см. http://burtleburtle.net /bob/c/lookup3.c ), что может оказаться полезным в реализации хеширования кукушки.
Хеширование Cuckoo относительно не используется за пределами академических кругов (за исключением аппаратных кешей, которые иногда заимствуют идеи, но на самом деле не реализуют их полностью).Чтобы хорошо провести время при вставках, требуется очень разреженная хеш-таблица — для хорошей производительности действительно нужно, чтобы 51% вашей таблицы было пустым.Таким образом, он либо быстрый и занимает много места, либо медленный и использует пространство эффективно, но не то и другое одновременно.Другие алгоритмы эффективны как по времени, так и по пространству, хотя они хуже, чем «кукушка», когда учитываются только время или пространство.
Вот генератор кода для хеш-таблиц cuckoo.Проверьте лицензию генератора, чтобы убедиться, что выходные данные не соответствуют лицензии GPL.Так и должно быть, но все равно проверьте.
-Адам
Даже если это старый вопрос, кому-то это может быть интересно :)
В этом документе описывается реализация параллельного хеша d-ary cuckoo на графических процессорах (CUDA / OpenCL). Это описано очень хорошо, и реализовать его на основе описания довольно легко. Вообще стоит почитать, если вам интересна эта тема. (Вам потребуется логин ACM.)
Язык ввода-вывода имеет один, в PHash.c. Вы можете найти код для ввода-вывода на Github. IO имеет лицензию BSD.
Я вижу смысл в использовании, но это было моим аргументом в пользу использования именно этой схемы хеширования. Пожалуйста, дайте мне знать, если я что-то пропустил.
Насколько мне известно, возможными альтернативами хеш-таблицам для создания динамического словаря являются (сбалансированные) двоичные деревья и скиплисты. Просто для обсуждения давайте абстрагируемся от ключей и типов значений и будем предполагать, что мы будем обращаться к значениям через 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 s байта для хранения. Если коэффициент загрузки составляет 50%, для хранения элементов n мне потребуются те же 4 байта s , что и для деревьев.
Для меня это не так уж и плохо: хеш-таблица cuckoo будет занимать более или менее тот же объем памяти, что и двоичное дерево, но даст мне время доступа O (1), а не O (log n).
Не считая сложности поддержания сбалансированного дерева и дополнительной информации, которая может потребоваться для хранения балансировочной информации в узле.
Другие схемы хеширования могут обеспечить лучший коэффициент загрузки (скажем, 75% или 80%) без гарантии на худшее время доступа (которое может быть даже O (n)).
Кстати, хэши с кукушкой и " хеширование кукушки с помощью тайника " похоже, что он может увеличить коэффициент загрузки при сохранении постоянного времени доступа.
Хеширование кукушки кажется мне ценной техникой, и я подумал, что она уже исследована; это причина моего вопроса.
Я не могу говорить о программном обеспечении, но хеширование кукушки, безусловно, используется в оборудовании и становится очень популярным. Крупные поставщики сетевого оборудования изучают хеширование кукушки, а некоторые уже используют его. Влечение к хешированию кукушки, конечно же, связано с постоянным временем поиска, а также с почти постоянным временем вставки.
Хотя вставка теоретически может быть неограниченной, на практике она может быть ограничена до O (log n) числа строк в таблице (таблицах), и при измерении время вставки составляет в среднем около 1,1 * d обращений к памяти. Это всего на 10% больше, чем абсолютный минимум! Доступ к памяти часто является ограничивающим фактором в сетевом оборудовании.
Независимые хеш-функции обязательны, и правильно их выбрать сложно. Удачи.
После комментария «onebyone» я реализовал и протестировал пару версий хеширования Cuckoo, чтобы определить реальные требования к памяти.
После некоторого эксперимента утверждение о том, что вам не нужно пересчитывать данные до тех пор, пока таблица не заполнится почти на 50 %, кажется верным, особенно если "тайник"Хитрость реализована.
Проблема в том, что вы увеличиваете таблицу.Обычный подход заключается в удвоении ее размера, но это приводит к тому, что новая таблица используется только на 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%.
Конечно, ценой за меньшее потребление памяти является увеличение количества reash, которое в конечном итоге понадобится.Увы, ничего не бывает бесплатно.
Я собираюсь продолжить расследование, если кому-то интересно.
