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

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

Спасибо


hash bloom-filter
person dangerstat    schedule 02.05.2010    source источник
comment
Обычно вы реализуете фильтр Блума или хеш-таблицу для скорости. MD5 нацелен на устойчивость к коллизиям и криптографическую безопасность и, следовательно, очень медленный по сравнению с другими функциями. Вам следует искать другие функции для использования (но ответы ниже применимы независимо от вашей функции хеширования)   -  person Slartibartfast    schedule 05.08.2010

Ответы (2)


arrow_upward
4
arrow_downward

Сначала вы должны преобразовать хеш-вывод в беззнаковое целое число, а затем уменьшить его по модулю 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.

person Thomas Pornin    schedule 03.05.2010

arrow_upward
0
arrow_downward

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

person Amber    schedule 02.05.2010
comment
Привет, Дэв, приветствую ответ, не могли бы вы конкретизировать пример простого преобразования хеш-вывода (в виде последовательности байтов) в одно двоичное число, спасибо: D - person dangerstat; 02.05.2010