Using hash functions with Bloom filters
Bloom filter uses a hash function (or many) to generate a value between 0 and m given the input string X. My question is how to use a hash function to generate a value in this way, for example MD5 hash is usually represented as a 32-line long string hex
. how would I use the MD5 hashing algorithm to generate a value between 0 and m, where can I specify m? I'm using Java at the moment, so an example for this with the suggested MessageDigest function would be great, although just a general description of how to do this would be fine too.
thanks
a source to share
You must first convert the hash output to an unsigned integer and then decrement it modulo m. It looks like this:
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)
I assumed m is an instance BigInteger
. Use if necessary BigInteger.valueOf()
. Similarly, use n.intValue()
or n.longValue()
to get the value n as one of the Java primitive types.
Modular reduction is somewhat biased, but the bias is very small if m is significantly less than 2 ^ 128.
a source to share