Использование хэш-функций с фильтрами Блума

Question

Фильтр Блума использует хеш-функцию (или многие) для генерации значения между 0 и m при заданной входной строке X. Мой вопрос заключается в том, как использовать хеш-функцию для генерации значения таким образом, например, MD5. хеш, как правило, представлен строкой длиной hex 32, как бы я использовал алгоритм хеширования MD5 для генерации значения между 0 и m, где я могу указать m? Сейчас я использую Java, так что пример того, как сделать это с помощью функциональности MessageDigest, которую он предлагает, был бы великолепен, хотя просто общее описание того, как это сделать, тоже подойдет.

Спасибо

Answer 1

Сначала следует преобразовать выходные данные хеш-функции в целое число без знака, а затем уменьшить его по модулю m . Это выглядит так:

MessageDigest md = MessageDigest.getInstance("MD5");
// hash data...
byte[] hashValue = md.digest();
BigInteger n = new BigInteger(1, hashValue);
n = n.mod(m);
// at that point, n has a value between 0 and m-1 (inclusive)

Я предположил, что m - это BigInteger экземпляр. При необходимости используйте BigInteger.valueOf(). Аналогично, используйте n.intValue() или n.longValue(), чтобы получить значение n в качестве одного из примитивных типов Java.

Модульное сокращение несколько смещено, но смещение очень мало, если m существенно меньше, чем 2 ^ 128 .

Answer 2

Простейшим способом, вероятно, было бы просто преобразовать вывод хеша (в виде последовательности байтов) в одно двоичное число и взять его по модулю m.