在布隆過濾器中使用散列函數

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) 

我假設米是BigInteger實例。如有必要，請使用BigInteger.valueOf()。同樣，使用n.intValue()或n.longValue()可以將n的值作爲Java的一種基本類型。

模塊化還原有些偏差，但是偏壓是非常小的，如果米基本上小於2^128。

Answer 2

最簡單的方法很可能是剛剛轉換的散列輸出（作爲一個字節序列），以單一的二進制數，並採取模m。