Bloomfilter实现
使用Bloomfilter，我们将获得空间优化。 cassandra框架还具有Bloom Filter的实现。 但详细地说，这个空间优化是如何实现的？
布隆filter不是“框架”。 它更像是一种算法。 实施不是很长。
这是Java中的一个我尝试过（ .jar ，源代码和JavaDoc都可用）：
“独立的Java实现的Cuckoo Hashing和Bloom Filters” （如果以下链接不再起作用，您可能需要谷歌这样做）：
您可以使用此示例了解它如何节省空间：让我说我在谷歌工作，在Chrome团队工作，我想在浏览器中添加一项function，通知用户他输入的url是否是恶意url。 所以我有一个大约100万个恶意URL的数据集，这个文件的大小约为25MB。 由于大小非常大（与浏览器本身的大小相比较大），我将这些数据存储在远程服务器上。
情况1：我使用带哈希表的哈希函数。 我决定使用有效的散列函数，并通过散列函数运行所有100万个url以获取散列键。 然后我创建一个哈希表（一个数组），其中哈希键将给我一个放置该URL的索引。 所以现在，一旦我散列并填充了散列表，我就检查它的大小。 我已经在哈希表中存储了所有100万个URL以及它们的密钥。 所以大小至少为25 MB。 此哈希表由于其大小将存储在远程服务器上。 当用户出现并在地址栏中输入url时，我需要检查它是否是恶意的。 因此，我通过哈希函数运行url（浏览器本身可以这样做），我得到该URL的哈希键。 我现在必须使用该哈希密钥向我的远程服务器发出请求，以检查具有该特定密钥的哈希表中的特定URL是否与用户输入的内容相同。 如果是，那么它是恶意的，如果不是，则它不是恶意的。 因此，每次用户输入URL时，都必须向远程服务器发出请求以检查它是否是恶意URL。 这将花费大量时间，从而使我的浏览器变慢。
案例2：我使用布隆filter。 使用多个散列函数通过布隆filter运行100万个URL的整个列表，并且在大的0数组中将相应的位置标记为1。 假设我们想要1％的误报率，使用布隆filter计算器（ http://hur.st/bloomfilter?n=1000000&p=0.01 ），我们得到的布隆filter大小仅为1.13 MB。 这个小尺寸是预期的，即使数组的大小很大，我们只存储1或0而不是散列表中的URL。这个数组可以被视为位数组。 也就是说，由于我们只有两个值1和0，我们可以设置单个位而不是字节。 这将减少8倍的空间。 这个1.13 MB的布隆filter由于体积小，可以存储在网页浏览器中！ 因此，当用户出现并输入URL时，我们只需应用所需的散列函数（在浏览器中），并检查bloomfilter中的所有位置（存储在浏览器中）。 任何位置的值为0都告诉我们此URL绝对不在恶意URL列表中，用户可以自由进行。 因此，我们没有调用服务器，因此节省了时间。 值为1告诉我们，url可能位于恶意URL列表中。 在这些情况下，我们调用远程服务器，在那里我们可以使用一些其他散列函数和一些散列表，如第一种情况一样，检索并检查url是否实际存在。 由于大多数时候，url不太可能是恶意url，因此浏览器中的小布隆filter会将其显示出来，从而避免调用远程服务器，从而节省时间。 只有在某些情况下，如果布隆filter告诉我们url可能是恶意的，只有在那些情况下我们才会调用服务器。 那’可能’是99％的权利。
因此，通过在浏览器中使用小型bloomfilter，我们节省了大量时间，因为我们不需要为输入的每个URL进行服务器调用。
所以我之前看过这个问题，并且我使用了上面的建议，结果certificate这对我来说是缓慢的。 所以我写了自己的。 这不是完全一般的，但我相信如果有人像我一样渴望表现，他们会让自己变得更加一般:)
我使用了Murmur哈希实现，你可以在这里下载： http ： //d3s.mff.cuni.cz/~holub/sw/javamurmurhash/
代码：package uk.ac.cam.cl.ss958.SpringBoardSimulation;
import ie.ucd.murmur.MurmurHash; import java.util.BitSet; import java.util.Random; public class FastBloomFilter { private final BitSet bs; final int [] hashSeeds; final int capacity; public FastBloomFilter(int slots, int hashFunctions) { bs = new BitSet(slots); Random r = new Random(System.currentTimeMillis()); hashSeeds = new int[hashFunctions]; for (int i=0; i>> 24), (byte)(value >>> 16), (byte)(value >>> 8), (byte)value}; for (int i=0; i>> 24), (byte)(value >>> 16), (byte)(value >>> 8), (byte)value}; for (int i=0; i 您可以使用基于Redis服务器和Redisson lib的Bloomfilter。 基于128位HighwayHash 。 这是一个例子：
RBloomFilter bloomFilter = redisson.getBloomFilter("sample"); // initialize bloom filter once with // expectedInsertions = 55000000 // falseProbability = 0.03 bloomFilter.tryInit(55000000L, 0.03); bloomFilter.add(new SomeObject(someStateHere1)); bloomFilter.add(new SomeObject(someStateHere2)); // does it contain object? bloomFilter.contains(new SomeObject(someStateHere3));
我写了一篇关于使用Java 8function实现bloomfilter的简短post ，我希望这与节省空间的问题有关。 我进一步讨论了如何对一组Bloomfilter进行位切片，当一些信息检索系统会这样做时，这与你有很多布隆filter时的效率有关。