使用Java的BitSet实现BloomFilter

使用Java的BitSet实现BloomFilter

Java 中 BitSet就是“位图”数据结构 (可以简单看做redis的bitmaps数据结构)，根据“位图”的语义，数据的存在性可以使用 bit 位上的1或0来表示；一个 bit 具有2个值：0和1，正好可以用来表示 false 和 true。

可以使用BitSet实现一个简单的布隆过滤器，判断“数据是否存在”。

代码展示

package com.wuxiaolong.algorithm.bloomfilter;

import org.apache.commons.lang3.StringUtils;

import java.util.BitSet;

//布隆过滤器
public class BloomFilter {

    /* BitSet初始分配2^24个bit */
    private static final int DEFAULT_SIZE = 2 << 24;

    /** 不同哈希函数的种子，一般应取质数
    * 质数又叫素数，指的是在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。反之，则被称为合数。
    * 1和0既非素数，也非合数。
    * 质数有无穷个，主要有2、3、5、7、11、13、17、19、23、29、31、37、41、43、47、53、59、61、67、71等。
    * 质数的性质：
    * 1、质数p的约数只有两个，分别是1和p。
    * 2、初等数学基本定理：任一大于1的自然数，要么本身是质数，要么可以分解为几个质数之积，且这种分解是唯一的。
    * 3、质数的个数是无限的。
    * 4、质数的个数公式π(n)是不减函数。
    * */
    private static final int[] seeds = new int[] { 5, 7, 11, 13, 31, 37 };

    /**
     * JAVA中BitSet就是“位图”数据结构，根据“位图”的语义，
     * 数据的存在性可以使用bit位上的1或0来表示；一个bit具有2个值：0和1，正好可以用来表示false和true
     */
    private BitSet bits = new BitSet(DEFAULT_SIZE);

    /* 哈希函数对象 */
    private SimpleHash[] func = new SimpleHash[seeds.length];

    public BloomFilter() {
        for (int i = 0; i < seeds.length; i++) {
            func[i] = new SimpleHash(DEFAULT_SIZE, seeds[i]);
        }
    }

    // 将url标记到bits中
    public void add(String str) {
        for (SimpleHash f : func) {
            bits.set(f.hash(str), true);
        }
    }

    // 判断是否已经被bits标记
    public boolean contains(String str) {
        if (StringUtils.isBlank(str)) {
            return false;
        }

        boolean ret = true;
        for (SimpleHash f : func) {
            ret = ret && bits.get(f.hash(str));
        }

        return ret;
    }

    /* 哈希函数类 */
    public static class SimpleHash {
        private int cap;
        private int seed;

        public SimpleHash(int cap, int seed) {
            this.cap = cap;
            this.seed = seed;
        }

        // hash函数，采用简单的加权和hash
        public int hash(String value) {
            int result = 0;
            int len = value.length();
            for (int i = 0; i < len; i++) {
                result = seed * result + value.charAt(i);
            }

            // 计算取模结果： result %  cap
            // 当取模运算 取模的数字cap是2的n方时  可以转换成二进制的按位与 ： result & (cap-1)
            return result & (cap - 1);
        }
    }
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86