将哈希函数与布隆过滤器结合使用

Question

布隆过滤器使用散列函数(或多个)在给定输入字符串X的情况下生成介于0和m之间的值。我的问题是如何使用散列函数以这种方式生成值，例如，MD5散列通常由32个长度的hex字符串表示，我如何使用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为模。