On Friday 23 May 2008 15:20, j16sdiz at freenetproject.org wrote:
> Author: j16sdiz
> Date: 2008-05-23 14:20:09 +0000 (Fri, 23 May 2008)
> New Revision: 20059
>
> Added:
> branches/saltedhashstore/freenet/src/freenet/support/BloomFilter.java
> Log:
> bloom filter
>
>
> Added: branches/saltedhashstore/freenet/src/freenet/support/BloomFilter.java
> ===================================================================
> --- branches/saltedhashstore/freenet/src/freenet/support/BloomFilter.java
>
(rev 0)
> +++ branches/saltedhashstore/freenet/src/freenet/support/BloomFilter.java
2008-05-23 14:20:09 UTC (rev 20059)
> +
> + private int[] getHashes(byte[] key) {
> + int[] hashes = new int[k];
> +
> + MessageDigest md = SHA256.getMessageDigest();
> + try {
> + for (int i = 0; i < k; i++) {
> + md.update(key);
> + md.update((byte) i);
> + hashes[i] = (int)
> ((Fields.bytesToLong(md.digest()) & Long.MAX_VALUE) %
length);
Unnecessary. Just extract them all from a single SHA256 invocation at
different points along the output. Otherwise, a nice simple implementation.
Although it will need to be regenerated periodically because it's
non-counting so doesn't support deletions. If it was counting, it could
efficiently support deletions, and therefore need regenerating only after an
unclean shutdown (or maybe several unclean shutdowns)... or when there was an
overflow, which as long as the same key isn't added twice (unclean shutdowns
again!), should be relatively rare... Some implementations apparently use an
exception table, but I don't see any efficient way to do this on-disk (unless
it's really small, would it be?).
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: not available
URL:
<https://emu.freenetproject.org/pipermail/devl/attachments/20080524/949e5953/attachment.pgp>
