Фильтр Блума: Как найти k хеш-функций?

Question

Фильтру Блума требуется k хеш-функций, которые возвращают значение от 0 до m (m - длина массива битов). Мне нужно реализовать такой фильтр Блума, и я уже читал некоторые теоретические статьи об этом фильтре (как они работают, сколько хеш-функций вам нужно, как ведет себя ошибка и т. Д.)

Теперь у меня есть два вопроса о хэш-функциях:

• Как мне найти k хеш-функций - какие хеш-функции мне следует использовать?
• Как мне найти хеш-функции, которые возвращают значение от 0 до m? В качестве альтернативы, как я могу отобразить вывод хэш-функции в диапазон 0-м?

Answer 1

Вы можете использовать это - http://en.wikipedia.org/wiki/Universal_hashing

Answer 2

Вы можете использовать оптимизацию Кирша-Митценмахера :

hash_i = hash1 + i * hash2

Где хэш-1 32-битный, хеш-2 32-битный.В виде вы можете использовать:

hash1 = upper 32 bit of a 64 bit hash
hash2 = lower 32 bit of a 64 bit hash
hash = hash1
for(int i=0; i<k; i++) {
    hash += hash2
}

Answer 3

U может использовать любые хеш-функции .... в сети доступно много простых хеш-функций. См. http://en.wikipedia.org/wiki/List_of_hash_functions

Используйте любую хеш-функцию для получения хеш-значения, а для того, чтобы получить его в диапазоне 0-м, используйте оператор модуля (%). т.е. битовое размещение = хэш% m;

это может быть неэффективно, но работает ...

Answer 4

• Характеристики k хеш-функций, которые следует использовать:
  приведены на странице википедии: Фильтр Блума и перейдите в
  описание алгоритма , где сказано: требование разработки k различных независимых хеш-функций ...

• Для хороших уроков по универсальному хешированию: Хорошая лекция MIT

Answer 5

Вы можете получить кучу хеш-значений одновременно с помощью криптографической хеш-функции, такой как MD5 или SHA.Разделите криптографическое значение хеша на N m-битных кусочков и обработайте их так же, как если бы вы выводили N обычных хеш-функций.