Могу ли я использовать 1 вместо k хеш-функций для реализации фильтра Блума?

Здесь есть аналогичный вопрос: Почему фильтру Блума нужно несколько Хеш-функции?, но у него есть выбранный ответ, который довольно расплывчатый и не полностью отвечает на мой вопрос:

Вместо использования k хеш-функций (или даже всего 2, как указано в этой статье: http://www.eecs.harvard.edu/~kirsch/pubs/bbbf/rsa.pdf ), могу ли я применить одно из следующих решений для реализации фильтра Блума?

  1. Введите хэш один раз, разбейте хэш на k разделов и используйте модуль m каждого из этих разделов в качестве значений моего индекса.
  2. Хэш-ввод один раз, затем модуль на k простых чисел, чтобы получить k значений индекса.

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


algorithm hash bloom-filter hash-function
person jasonbcox    schedule 10.05.2016    source источник
comment
Первый из них — это фактически k независимых хеш-функций. Второй нет; хэш-функции коррелированы.   -  person Raymond Chen    schedule 10.05.2016
comment
@RaymondChen: Из любопытства, как соотносятся h%p1 и h%p2, если предположить, что h равномерно распределено в [0, m), а p1 и p2 — различные простые числа между m^(1/3) и m^(1) /2)? .... хотя кажется, что сегментация на битовые диапазоны - более дешевое вычисление...   -  person rici    schedule 10.05.2016
comment
h%p1 и h%p2 не являются независимыми. Знание (h+1)%p1 многое говорит вам о (h+1)%p2.   -  person Raymond Chen    schedule 10.05.2016
comment
Моя интуиция была в том же духе, что и Ричи, полагая, что, хотя они не являются по-настоящему зависимыми, результаты будут достаточно разнообразными, чтобы их можно было использовать на практике.   -  person jasonbcox    schedule 10.05.2016
comment
Спасибо за ответ, Рэймонд Чен, я, вероятно, выберу № 1, если не будет явно лучшего и более простого способа реализовать это.   -  person jasonbcox    schedule 10.05.2016