Повторное использование 5-независимых хеш-функций для линейного зондирования

14

В хеш-таблицах, которые разрешают коллизии линейным зондированием, для обеспечения ожидаемой производительности необходимо и достаточно, чтобы хеш-функция была из 5-независимого семейства. (Достаточность: «Линейное зондирование с постоянной независимостью», Паг и др. , Необходимость: «О k-независимости, необходимой для линейного зондирования и минимальной независимости», Pătraşcu и Thorup )О(1)

Насколько я понимаю, наиболее быстро известные 5 независимых семей используют табуляцию. Выбор функции из такого семейства может быть дорогостоящим, поэтому я хотел бы свести к минимуму количество повторений, при этом предотвращая атаки на алгоритмическую сложность, как описано в «Отказе в обслуживании через атаки алгоритмической сложности» Кросби и Уоллаха . Меня меньше беспокоит время атаки (то есть противники с секундомерами). Каковы последствия повторного использования одной и той же функции:

  1. При выращивании слишком большой таблицы хешей?
  2. При сжатии хеш-таблицы, что недостаточно полно?
  3. При восстановлении хеш-таблицы, в которой установлено слишком много «удаленных» битов?
  4. В различных хеш-таблиц, которые могут содержать некоторые общие ключи?К
  5. В различных хеш-таблиц, которые не содержат общих ключей?К
ds.data-structures hash-function randomized-algorithms security jbapple
источник
Если речь идет о практике ... правдоподобный прагматический подход заключается в использовании криптографической хеш-функции со случайным секретом, включенным во входные данные, вместо использования схемы, основанной на табулировании. Тогда есть меньшее давление, чтобы повторно использовать ту же самую хэш-функцию; Вы можете использовать разные секреты для каждой хеш-таблицы (и изменять секрет и перефразировать все, когда уменьшаете / увеличиваете / перестраиваете хеш-таблицу).
DW
Я думаю, что даже быстрые криптографические хеш-функции на коротких входах, таких как SipHash-2-4, довольно медленны по сравнению даже с 5-независимыми семействами, использующими полиномы.
Jbapple

Ответы:

1

Одна потенциальная проблема заключается в том, что при чтении из хеш-таблицы элементы не должны читаться в порядке слотов, если все хеш-таблицы используют одну и ту же хеш-функцию. Это связано с тем, что эти элементы в указанном порядке могут привести к тому, что процедура вставки в меньшую хеш-таблицу с той же хеш-функцией станет квадратичной, предполагая, что максимальный коэффициент заполнения превышает . Видеть:1/2

jbapple
источник