Сумасшедшее хеширование в C

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

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

Язык IO имеет один в PHash.c. Можно найти эти код для IO на GitHub. IO является лицензируемым BSD.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

-Adam

После комментария от "onebyone" я реализовал и протестировал несколько версий Сумасшедшего хеширования для определения требования реальной памяти.

После некоторого эксперимента, заявление, что Вы не имеете к reash до таблицы, почти на 50% полно, кажется, верен, особенно если" притон " прием является implmented.

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

На самом деле, предположите, что хеш-таблица имеет 16 слотов, когда я вставлю 8-е число элемента, я выбегу из хороших слотов и буду иметь к reash. Я удвою его, и теперь таблица является 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-й) после reash (т.е. худший случай).

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

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

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

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

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

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

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

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