bloom filter 备忘(1)

这是 url 队列一环的要害之一。

爬虫必然要考虑的问题之一就是url的去重问题，很容易想到的方法是 hashmap/hashtable(md5(url))：程序退出时序列化并写入持久介质，启动时重新读入，反序列化载入内存。或者考虑如Berkeley DB等key-value结构的持久存储方案，可以屏蔽了很多如持久化、高并发、随机/顺序存储等操作。忽略md5的重复几率，在数据量不是太大的情况下不失为一个办法，md5之后Hash映射碰撞几率很小，或者足以容忍，而且实现简单，也比较准确。但hashtable的内存利用率常常只有50%(googleblog)，当需要消重的数据量数以亿计的时候这个问题就异常突出了，幸好早在1970年巴顿.布隆就给我们准备好了解决方案：布隆过滤器(Bloom Filter)。

布隆过滤器(Bloom Filter)实际上是一个很长的二进制向量和一系列随机映射函数，可以用于检索一个元素是否在一个集合中。由一组hash函数和一个给定长度的位向量组成，位向量的长度、hash函数的数量依赖于数据量和我们能容忍的假命中率高低；其优点是空间效率和查询时间都远远超过一般的算法，缺点是有一定的误识别率和删除困难。使用高质量的hash函数相当重要，它保证输出等分在所有可能值上，hash函数里的“热点”会大幅增加假命中率。

package isabella;

import java.util.BitSet;

public class BloomFilter {
    private int setLen = 2 << 32 - 1;
    private BitSet bits;

    public BloomFilter() {
        bits = new BitSet(setLen);
    }

    /**
     * @param url
     * @return contains or not
     */
    public boolean contains(String url) {
        if (url == null) {
            return true;
        }

        int pos0 = hash1(url);
        int pos1 = hash1(url);
        int pos2 = hash2(url);
        int pos3 = hash3(url);
        if (bits.get(pos0) && bits.get(pos1) && bits.get(pos2) && bits.get(pos3)) {
            return true;
        }
        return false;
    }

    public void put(String url) {
        if (url == null) {
            return;
        }
        int pos0 = hash0(url);
        int pos1 = hash1(url);
        int pos2 = hash2(url);
        int pos3 = hash3(url);

        bits.set(pos0);
        bits.set(pos1);
        bits.set(pos2);
        bits.set(pos3);
    }

    /**
     * K Hash
     * @param line
     * @return
     */
    private int hash3(String line) {
        int h = 0;
        for (int i = 0; i < line.length(); i++) {
            h = 37 * h + line.charAt(i);
        }
        return check(h);
    }

    private int hash2(String line) {
        int h = 0;
        for (int i = 0; i < line.length(); i++) {
            h = 33 * h + line.charAt(i);
        }
        return check(h);
    }

    private int hash1(String line) {
        int h = 0;
        for (int i = 0; i < line.length(); i++) {
            h = 31 * h + line.charAt(i);
        }
        return check(h);
    }

    private int hash0(String line) {
        int h = 0;
        for (int i = 0; i < line.length(); i++) {
            h = 30 * h + line.charAt(i);
        }
        return check(h);
    }

    private int check(int h) {
        return setLen & h;
    }
}

参考文档：
Bloom Filter概念和原理
数学之美系列 － 布隆过滤器