数据结构与算法-bitMap和bloomFilter

Posted on | Edited on | In ,

考虑如下需求:

  • 爬虫对于大量的URL进行排重
  • 统计网站的UV;
  • 对1到1亿的数据进行排序

位图的使用场景

如果我们要存储1到1亿个数字，支持排重该如何做呢，可以采用位图。见下面的代码，用位图会极大的节省查找、插入的效率.一次位运算即可，同时也极大的节省了内存空间，现在只许愿1亿个2进制，即12MB左右。如果用散列表至少需要40MB。

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
public class BitMap {
    private int[] bytes;
    private int total;

    //int类型的位图下标是4个字节即32bit
    public BitMap(int total) {
        this.bytes = new int[total / 32 + 1];
        this.total = total;
    }

    public void set(int value) {
        //找到数组下标
        int index = value / 32;
        //通过摩运算找到偏移量
        int bit = value % 32;
        //通过位运算|找到值
        bytes[index] |= 1 << bit;
    }

    public boolean exists(int value) {
        if (value > total) {
            return false;
        }

        int index = value / 32;
        int bit = value % 32;
        return (bytes[index] & 1 << bit) != 0;
    }
}

bloomfilter

接上面的问题，如果数字的值不多，但是范围很大，比如1亿个数字但是范围是1到10亿，这时候我们的存储空间变成了120MB，不降反升，我们该如何存储呢？这时候就要借用bloomfilter了。

boolmfilter底层还是bitMap，大小还可以设置为1亿。在介绍hash散列时候我们遇到hash冲突采用链表来解决hash冲突。在这里我们采用多个hash函数。
比如：

  • 我们对一个值用h1,h2,h3……hn，分别将值写入到v1,v2,v3…..vn中。
  • 查询时候我们分别判断如果h1~hn都为true，返回true,只要有一个为false，就返回false

  • 缺点：

    • 存在误判的情况，随着bloomfilter里1的值越来越多，误判率会加大，最好支持扩容;
    • 删除会很麻烦;

    开头提到的问题：我们可以采用10倍的bloomfilter存储url，同时进行排重

引申问题

  1. 假设我们有1亿个整数，数据范围是从1到10亿，进行排序;
  2. 海量图库的排重;
1
2
3
4
5
6
7
8
9
10
11
12
//排序
    public void sort() {
        for (int i = 0; i < bytes.length; i++) {
            for (int j = 0; j < 32; j++) {
                if ((bytes[i] & (1 << j)) != 0) {
                    System.out.print((i*32+j) + " ");
                }
            }
        }

        System.out.println();
    }

bitmap在语言中的应用

java的中bitSet
google库guava中的BloomFilter的实现类