Какие функции хеша использовать в цветном фильтре

У меня возникает вопрос о выборе хеш-функций для фильтров Bloom:

  • Какие функции использовать?

В почти каждом документе/документе вы можете прочитать, что хеш-функции, используемые в цветном фильтре, должны быть независимыми и равномерно распределены.

Я знаю, что подразумевается под этим (независимым и равномерно распределенным), но мне трудно найти аргументацию или дискуссию, которые хеш-функции выполняют эти требования и поэтому подходят. Во многих сообщениях я читал о предложениях по использованию FNV или хеш-функции Murmur, но не почему (или, по крайней мере, без доказательства) они подходят.

Спасибо заранее!

Ответы

Ответ 1

Hash Functions должен предоставить вам графическое доказательство того, почему FNV будет плохим выбором, и почему Murmur2 или один из Хэши Боба Дженкинса были бы хорошим выбором.

Ответ 2

Я задал себе тот же вопрос при создании библиотеки фильтров Java Bloom. См. Github readme для подробного рассмотрения моего анализа хеш-функций для фильтров Bloom.

Я рассмотрел проблему с двух сторон:

  • Как быстро вычисляется?
  • Насколько однородным является распределение выходных данных?

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

Результат:

  • Используйте Murmur3 для лучшего компромисса между скоростью и единообразием. Не используйте Murmur2, поскольку он не является однородным для входов, которые изменяются небольшими приращениями.
  • Используйте криптографическую хэш-функцию, например SHA-256, для лучшей однородности.
  • Примените Kirsch-Mitzenmacher-Optimization только для вычисления 2 вместо х хэш-функций (hash_i = hash1 + ix hash2).

Если ваша реализация использует Java, я бы рекомендовал использовать нашу библиотеку хеша фильтра Bloom. Он хорошо документирован и тщательно протестирован. Для получения подробной информации, включая результаты тестов для разных хеш-функций и их несоответствие в соответствии с критерием Чи-Квадрата, см. Github readme of repo.

Ответ 3

Я думаю, что разумным вариантом было бы несколько CRC-хэшей. Я предполагаю, что если вам нужны несколько n-бит хэш-значений, то для многочленов с булевыми коэффициентами поля существуют несколько простых многочленов степени n + 1. Но я не знаю процесса нахождения этих многочленов.

Другая возможность - использовать несколько модульных хэшей. Размер битового массива Bloom Filter должен быть максимальным значением по модулю. Но я думаю, что для того, чтобы он работал хорошо, значения модуля должны были бы быть продуктом простых чисел, превышающих 10, и относительно просто друг к другу. И диапазон от минимального до максимального значения модуля должен быть как можно меньше. Я не знаю, как найти такие ценности. Я написал код с открытым кодом С++ для быстрого вычисления остатков: https://github.com/wkaras/C-plus-plus-intrusive-container-templates/blob/master/modulus_hash.h