黄忠的技术博客

永不停息的战争

你应该知道的布隆过滤器(BloomFilter)

  • 标签:
  • tec

之所以谈论这个问题,是因为面试中偶尔会提到这个问题, 重要的是我是一个爬虫工作者(多么美妙的名字,不是吗),没有理由不知道。 另外它的价值不仅仅在于处理爬虫url排重等问题, 比如检测一个可疑的电子邮件地址是否在黑名单中; 又比如,查询一个字符串中,包含哪些字符等问题; 大家可以查询wiki布隆过滤器了解更多的知识。

```
package com.chris.review;

import java.util.BitSet;

/**   
 * User: zhong.huang   
 * Date: 13-8-18   
 *   
 * 一些方法   
 *   
 * public void set(int pos): 位置pos的字位设置为true。   
 * public void set(int bitIndex, boolean value) 将指定索引处的位设置为指定的值。   
 * public void clear(int pos): 位置pos的字位设置为false。   
 * public void clear() : 将此 BitSet 中的所有位设置为 false。   
 * public int cardinality() 返回此 BitSet 中设置为 true 的位数。   
 * public boolean get(int pos): 返回位置是pos的字位值。   
 * public void and(BitSet other): other同该字位集进行与操作,结果作为该字位集的新值。   
 * public void or(BitSet other): other同该字位集进行或操作,结果作为该字位集的新值。   
 * public void xor(BitSet other): other同该字位集进行异或操作,结果作为该字位集的新值。   
 * public void andNot(BitSet set) 清除此 BitSet 中所有的位,set - 用来屏蔽此 BitSet 的 BitSet   
 * public int size(): 返回此 BitSet 表示位值时实际使用空间的位数。   
 * public int length() 返回此 BitSet 的“逻辑大小”:BitSet 中最高设置位的索引加 1。   
 * public int hashCode(): 返回该集合Hash 码, 这个码同集合中的字位值有关。   
 * public boolean equals(Object other): 如果other中的字位同集合中的字位相同,返回true。   
 * public Object clone() 克隆此 BitSet,生成一个与之相等的新 BitSet。   
 * public String toString() 返回此位 set 的字符串表示形式。   
 */    public class BloomFilter {
private int DEFAULT_SIZE = 2 << 24;
private int[] seeds = {3, 7, 11, 13, 31, 37, 61};
private BitSet bitSet;

public BloomFilter() {
    bitSet = new BitSet(DEFAULT_SIZE);
}

//计算Hash值
private int hash(String str, int n) {
    int result = 0;
    for (int i = 0; i < str.length(); i++) {
        result = seeds[n] * result + str.charAt(i);
        if (result > 2 << 24) {
            result %= 2 << 24;
        }
    }
    return result;
}

//判断是否在布隆过滤器中
private boolean exists(String str) {
    int hash = 0;
    for (int i = 0; i < seeds.length; i++) {
        hash = hash(str, i);
        if (bitSet.get(hash) == false)
            return false;
    }
    return true;
}

//添加元素到布隆过滤器
private void add(String str) {
    int hash;
    for (int i = 0; i < seeds.length; i++) {
        hash = hash(str, i);
        bitSet.set(hash);
    }
}

//初始化布隆过滤器
private void init(int num) {
    for (int i = 0; i < num; i++) {
        add("http://www.dajie.com" + i);
    }
}

public static void main(String[] args) {
    BloomFilter bf = new BloomFilter();
    bf.init(10000000);
    long start = System.currentTimeMillis();
    System.out.println(bf.exists("http://www.dajie.com"));
    long end = System.currentTimeMillis();
    System.out.println(end - start);
    start = end;
    System.out.println(bf.exists("http://www.dajie.com1"));
    end = System.currentTimeMillis();
    System.out.println(end - start);
}

} ```

分享到: 返回主页