布隆过滤器的实现

Question

使用Bloom filter，我们将获得空间优化。cassandra框架还实现了Bloom Filter。但是详细地说，这种空间优化是如何实现的呢？

Answer 1

bloom filter不是一个“框架”。它实际上更像是一个简单的算法。实现的时间不是很长。

这里有一个我尝试过的Java语言(.jar、源代码和JavaDoc都是可用的)：

“Cuckoo哈希和Bloom过滤器的独立Java实现”(你可能想在谷歌上搜索这个链接，以防下面的链接不再起作用)：

http://lmonson.com/blog/?page_id=99

Answer 2

你可以通过这个例子来理解它是如何节省空间的:假设我在Chrome团队中为Google工作，我想在浏览器中添加一个功能，如果用户输入的URL是恶意url，该功能会通知用户。所以我有一个大约一百万个恶意URL的数据集，这个文件的大小大约是25MB。由于大小相当大(与浏览器本身的大小相比很大)，因此我将此数据存储在远程服务器上。

案例1:我将哈希函数与哈希表一起使用。我决定了一个有效的散列函数，并通过散列函数运行所有100万个urls来获得散列键。然后，我创建了一个哈希表(一个数组)，其中的哈希键将为我提供放置该URL的索引。所以，一旦我散列并填充了哈希表，我就会检查它的大小。我已经在哈希表中存储了所有100万个URL以及它们的键。因此，大小至少为25MB。由于哈希表的大小，它将存储在远程服务器上。当用户出现并在地址栏中输入url时，我需要检查它是否是恶意的。因此，我通过散列函数运行URL (浏览器本身可以做到这一点)，并获得该url的散列键。我现在必须用这个散列键向我的远程服务器发出一个请求，以检查我的散列表中具有该特定键的特定URL是否与用户输入的URL相同。如果是，那么它是恶意的，如果不是，那么它不是恶意的。因此，每次用户输入URL时，都必须向远程服务器发出请求，以检查它是否是恶意URL。这会花费很多时间，因此会让我的浏览器变慢。

案例2:我使用bloom filter。使用多个散列函数通过bloom filter运行100万个URL的整个列表，并将各自的位置标记为1，这是一个巨大的0数组。假设我们想要1%的误报率，使用布隆过滤器计算器(http://hur.st/bloomfilter?n=1000000&p=0.01)，我们得到所需的布隆过滤器大小仅为1.13MB。尽管数组的大小很大，但我们只存储1或0，而不是table.This，因为在散列URL数组可以被视为位数组的情况下，这种小尺寸是预期的。也就是说，因为我们只有两个值1和0，所以我们可以设置单独的位而不是字节。这将减少8倍的空间占用。这个1.13MB的布隆过滤器，由于它的小尺寸，可以存储在web浏览器本身中!！因此，当用户出现并输入URL时，我们只需应用所需的散列函数(在浏览器本身中)，并检查bloom filter (存储在浏览器中)中的所有位置。任何位置的值为0都表示此URL绝对不在恶意URL列表中，用户可以自由操作。因此，我们没有调用服务器，从而节省了时间。值1告诉我们该url可能在恶意url列表中。在这些情况下，我们调用远程服务器，在那里我们可以使用一些其他的哈希函数和一些哈希表，就像第一种情况一样，检索和检查url是否确实存在。由于大多数情况下，url不太可能是恶意的，浏览器中的小布隆过滤器会找出这一点，因此通过避免调用远程服务器来节省时间。只有在某些情况下，如果bloom过滤器告诉我们url可能是恶意的，我们才会调用服务器。这个“可能”是99%正确的。

因此，通过在浏览器中使用一个小的bloom过滤器，我们节省了大量的时间，因为我们不需要为输入的每个url都进行服务器调用。

Answer 3

所以我以前见过这个问题，我使用了上面的建议，结果对我来说是一种很慢的方式。所以我写了我自己的。它不是完全通用的，但我相信，如果有人像我一样渴望性能，他们会自己把它变得更通用:)

我使用了Murmur散列实现，您可以从这里下载：http://d3s.mff.cuni.cz/~holub/sw/javamurmurhash/

代码:uk.ac.cam.cl.ss958.包；

    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));


        }
    }