Несколько вопросов о кукушке

Question

Мне нужно создать таблицу быстрого поиска с 8-байтовыми целочисленными ключами. Построение таблицы выполняется во время инициализации, и после этого данные не обновляются. Количество элементов данных не превышает 100 КБ, поэтому я могу позволить себе использовать дополнительное пространство для разреженности хеш-таблицы. Однако поиск данных должен быть максимально эффективным. Насколько я понимаю, Cuckoo Hashing кажется подходящим для такого сценария. Тем не менее, я не очень ясно о нескольких вещах:

1. Какое семейство хеш-функций следует использовать в этом случае? В некоторых работах предполагается, что стандартное семейство функций «((a * x + b) mod p) mod m» не является хорошим выбором. Более того, p должно быть простым> UInt64.MaxValue, что затрудняет вычисление функции. Многосменное семейство "(a * x) >> (w - log (m))" также не считается хорошим выбором. Я не мог найти точного ответа о том, какую функцию использовать.

2. Операция «вставки» может вызвать перефразировку. Таким образом, теоретически время вставки неограничено в худшем случае (вы просто продолжаете выбирать «плохую» функцию, которая приводит к перефразировке). Я понимаю, что вероятность этого близка к нулю, но мне трудно просто игнорировать эту проблему в производстве.

3. Существуют ли более подходящие структуры данных для описанной проблемы? оригинальная бумага Cuckoo Hash предполагает, что простой хэш с линейным зондированием может быть более эффективным, если у вас достаточно свободного места (в два-три раза больше элементов). Кроме того, на этапе построения я могу проверить, не сталкиваются ли более двух ключей, и выбрать другую функцию хеширования (я могу позволить себе сделать это несколько раз и выбрать лучшую).

Большое спасибо за ваши ответы.

Answer 1

1. Подойдет практически любая хеш-функция, поскольку у вас есть только 100К-ключи, просто убедитесь, что она как минимум независима от двух сторон (см. http://www.eecs.harvard.edu/~michaelm/postscripts/soda2008b.pdf) или просто используйте что-нибудь быстрое.

2. Процедура вставки будет работать в амортизированном / ожидаемом времени O (1), если вы выполните исчерпывающий поиск, так как вы делаете это в начале, у вас все будет хорошо. Если вы используете менее 50% (т. Е. Количество слотов> 2x количество ключей), вероятность того, что вставка вызовет перефразирование, мала. Вы можете сделать это еще меньше, используя тайник (http://www.eecs.harvard.edu/~michaelm/postscripts/esa2008full.pdf), и поиск по-прежнему мал. В любом случае просто повторите попытку, пока все не будет работать, поскольку вы делаете это только при инициализации.

3. Отрезать дважды, измерить один раз.