使用Bloom过滤器，我们将获得空间优化。 cassandra框架还具有Bloom Filter的实现。但详细地说，这个空间优化是如何实现的？
布隆过滤器不是“框架”。它更像是一种算法。实施不是很长。
这是Java中的一个我尝试过（.jar，源代码和JavaDoc都可用）：
“独立的Java实现的Cuckoo Hashing和Bloom过滤器”（如果以下链接不再起作用，您可能需要谷歌这样做）：
您可以使用此示例了解它如何节省空间：让我说我在谷歌工作，在Chrome团队工作，我想在浏览器中添加一项功能，通知用户他输入的网址是否是恶意网址。所以我有一个大约100万个恶意URL的数据集，这个文件的大小约为25MB。由于大小很大（与浏览器本身的大小相比较大），我将这些数据存储在远程服务器上。
情况1：我使用带哈希表的哈希函数。我决定使用有效的散列函数，并通过散列函数运行所有100万个url以获取散列键。然后我创建一个哈希表（一个数组），其中哈希键将为我提供放置该URL的索引。所以现在一旦我散列并填充了散列表，我就检查它的大小。我已经在哈希表中存储了所有100万个URL以及它们的密钥。所以大小至少为25 MB。此哈希表由于其大小将存储在远程服务器上。当用户出现并在地址栏中输入网址时，我需要检查它是否是恶意的。因此，我通过哈希函数运行url（浏览器本身可以这样做），我得到该URL的哈希键。我现在必须使用该哈希密钥向我的远程服务器发出请求，以检查具有该特定密钥的哈希表中的特定URL是否与用户输入的内容相同。如果是，那么它是恶意的，如果不是，则它不是恶意的。因此，每次用户输入URL时，都必须向远程服务器发出请求以检查它是否是恶意URL。这将花费大量时间，从而使我的浏览器变慢。
案例2：我使用布隆过滤器。使用多个散列函数通过布隆过滤器运行100万个URL的整个列表，并且在大的0数组中将相应的位置标记为1。假设我们想要1％的误报率，使用布隆过滤器计算器（http://hur.st/bloomfilter?n=1000000&p=0.01），我们得到布隆过滤器所需的大小仅为1.13 MB。这个小的大小是预期的，即使数组的大小很大，我们只存储1或0而不是散列表中的URL。这个数组可以被视为位数组。也就是说，由于我们只有两个值1和0，我们可以设置单个位而不是字节。这将减少8倍的空间。这个1.13 MB的布隆过滤器由于体积小，可以存储在网页浏览器中！因此，当用户出现并输入URL时，我们只需应用所需的哈希函数（在浏览器本身中），并检查bloom过滤器中的所有位置（存储在浏览器中）。任何位置的值为0都告诉我们此URL绝对不在恶意URL列表中，用户可以自由进行。因此，我们没有调用服务器，因此节省了时间。值为1告诉我们，网址可能位于恶意URL列表中。在这些情况下，我们调用远程服务器，在那里我们可以使用一些其他散列函数和一些散列表，如第一种情况一样，检索并检查url是否实际存在。由于大多数时候，网址不太可能是恶意网址，因此浏览器中的小布隆过滤器会将其显示出来，从而避免调用远程服务器，从而节省时间。只有在某些情况下，如果布隆过滤器告诉我们网址可能是恶意的，只有在那些情况下我们才会调用服务器。 '可能'是99％的权利。
因此，通过在浏览器中使用小型bloom过滤器，我们节省了大量时间，因为我们不需要为输入的每个URL进行服务器调用。
所以我之前看过这个问题，并且我使用了上面的建议，结果证明这对我来说是缓慢的。所以我写了自己的。它并不完全通用，但我确信如果有人像我一样渴望表现，他们会让自己变得更加通用:)
我使用了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<hashFunctions; ++i) {
hashSeeds[i] = r.nextInt();
}
capacity = slots;
}
public void add(int value) {
byte [] b = new byte[] {
(byte)(value >>> 24),
(byte)(value >>> 16),
(byte)(value >>> 8),
(byte)value};
for (int i=0; i<hashSeeds.length; ++i) {
int h = MurmurHash.hash32(b, 4, hashSeeds[i]);
bs.set(Math.abs(h)%capacity, true);
}
}
public void clear() {
bs.clear();
}
public boolean mightContain(int value) {
byte [] b = new byte[] {
(byte)(value >>> 24),
(byte)(value >>> 16),
(byte)(value >>> 8),
(byte)value};
for (int i=0; i<hashSeeds.length; ++i) {
int h = MurmurHash.hash32(b, 4, hashSeeds[i]);
if(!bs.get(Math.abs(h)%capacity)) {
return false;
}
return true;
}
public static void main(String [] args) {
FastBloomFilter bf = new FastBloomFilter(1000, 10);
System.out.println("Query for 2000: " + bf.mightContain(2000));
System.out.println("Adding 2000");
bf.add(2000);
System.out.println("Query for 2000: " + bf.mightContain(2000));
}
}
您可以使用基于Redis服务器的Bloom过滤器和Redisson lib。基于128位HighwayHash。这是一个例子：
RBloomFilter<SomeObject> 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 8功能实现bloom过滤器的short post，我希望这与节省空间的问题有关。我去了一个bit further讨论如何对一组Bloom过滤器进行比特切片，当一些信息检索系统会这样做时，这与你有很多布隆过滤器时的效率有关。