海量数据处理计算及算法实现总结_布隆过滤器能够以极小的空间开销解决海量数据判重问题

此博客主要讲解海量数据处理计算及算法实现，了解海量数据处理方法可移步海量数据处理方法总结，了解数据处理问题可移步海量数据处理问题总结

方法回顾

1. 分而治之 / Hash 映射 + Hash 统计 + 堆 / 快速 / 归并排序
2. 双层桶划分
3. BitMap / Bloom Filter
4. Trie 树 / 数据库索引 / 倒排索引
5. 外排序
6. 分布式处理之Hadoop / Mapreduce

海量数据计算

计算容量

在解决问题之前，要先计算一下海量数据需要占多大的容量。常见的单位换算如下：

• 1 byte = 8 bit
• 1 KB = $2^{10}$ byte = 1024 byte ≈ $10^3$ byte
• 1 MB = $2^{20}$ byte ≈ $10^6$ byte
• 1 GB = $2^{30}$ byte ≈ $10^9$ byte
• 1 亿 = $10^8$
• 1 个整数占 4 byte，1 亿个整数占 4 * $10^8$ byte ≈ 400 MB。

拆分

可以将海量数据拆分到多台机器上和拆分到多个文件上：

• 如果数据量很大，无法放在一台机器上，就将数据拆分到多台机器上。这种方式可以让多台机器一起合作，从而使得问题的求解更加快速。但是也会导致系统更加复杂，而且需要考虑系统故障等问题；
• 如果在程序运行时无法直接加载一个大文件到内存中，就将大文件拆分成小文件，分别对每个小文件进行求解。

有以下策略进行拆分：

• 按出现的顺序拆分：当有新数据到达时，先放进当前机器，填满之后再将数据放到新增的机器上。这种方法的优点是充分利用系统的资源，因为每台机器都会尽可能被填满。缺点是需要一个查找表来保存数据到机器的映射，查找表可能会非常复杂并且非常大。
  
• 按散列值拆分：选取数据的主键 key，然后通过哈希取模 hash(key)%N 得到该数据应该拆分到的机器编号，其中 N 是机器的数量。优点是不需要使用查找表，缺点是可能会导致一台机器存储的数据过多，甚至超出它的最大容量。
  
• 按数据的实际含义拆分：例如一个社交网站系统，来自同一个地区的用户更有可能成为朋友，如果让同一个地区的用户尽可能存储在同一个机器上，那么在查找一个用户的好友信息时，就可以避免到多台机器上查找，从而降低延迟。缺点同样是需要使用查找表。
  

整合

拆分之后的结果还只是局部结果，需要将局部结果汇总为整体的结果。

注：大部分海量数据都可以使用 hash 取模来处理，因为同一个值 hash 取模后一定会分配到同一个位置。如果内存实在小，N 的值可以取大一些。再者，Hadoop 和 spark 也是处理海量数据的方案，不过非大数据方向应该不做要求。

算法实现

HashSet

考虑到数据是海量的，那么就使用拆分的方式将数据拆分到多台机器上，分别在每台机器上使用 HashSet 存储。我们需要使得相同的数据拆分到相同的机器上，可以使用哈希取模的拆分方式进行实现。

BitSet

如果海量数据是整数，并且范围不大时，就可以使用 BitSet 存储。通过构建一定大小的比特数组，并且让每个整数都映射到这个比特数组上，就可以很容易地知道某个整数是否已经存在。因为比特数组比整型数组小的多，所以通常情况下单机就能处理海量数据。

class BitSet {
    int[] bitset;
    
    public BitSet(int size) {
        bitset = new int[(size >> 5) + 1]; // divide by 32
    }
    
    boolean get(int pos) {
        int wordNumber = (pos >> 5); // divide by 32
        int bitNumber = (pos & 0x1F); // mod 32
        return (bitset[wordNumber] & (1 << bitNumber)) != 0;
    }
    
    void set(int pos) {
        int wordNumber = (pos >> 5); // divide by 32
        int bitNumber = (pos & 0x1F); // mod 32
        bitset[wordNumber] |= 1 << bitNumber;
    }
 }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

布隆过滤器

• 布隆过滤器能够以极小的空间开销解决海量数据判重问题，但是会有一定的误判概率。它主要用在网页黑名单系统、垃圾邮件过滤系统、爬虫的网址判重系统。
• 布隆过滤器也是使用 BitSet 存储数据，但是它进行了一定的改进，从而解除了 BitSet 要求数据的范围不大的限制。在存储时，它要求数据先经过 k 个哈希函得到 k 个位置，并将 BitSet 中对应位置设置为 1。在查找时，也需要先经过 k 个哈希函数得到 k 个位置，如果所有位置上都为 1，那么表示这个数据存在。
• 由于哈希函数的特点，两个不同的数通过哈希函数得到的值可能相同。如果两个数通过 k 个哈希函数得到的值都相同，那么使用布隆过滤器会将这两个数判为相同。
• 可以知道，令 k 和 m 都大一些会使得误判率降低，但是这会带来更高的时间和空间开销。
• 布隆过滤器会误判，也就是将一个不存在的数判断为已经存在，这会造成一定的问题。例如在垃圾邮件过滤系统中，会将一个邮件误判为垃圾邮件，那么就收不到这个邮件。可以使用白名单的方式进行补救。

public class BloomFilter {
    //你的布隆过滤器容量
    private static final int DEFAULT_SIZE = 2 << 28;
    //bit数组，用来存放key
    private static BitSet bitSet = new BitSet(DEFAULT_SIZE);
    //后面hash函数会用到，用来生成不同的hash值，可随意设置，别问我为什么这么多8，图个吉利
    private static final int[] ints = {1, 6, 16, 38, 58, 68};

    //add方法，计算出key的hash值，并将对应下标置为true
    public void add(Object key) {
        Arrays.stream(ints).forEach(i -> bitSet.set(hash(key, i)));
    }

    //判断key是否存在，true不一定说明key存在，但是false一定说明不存在
    public boolean isContain(Object key) {
         boolean result = true;
        for (int i : ints) {
        	//短路与，只要有一个bit位为false，则返回false
            result = result && bitSet.get(hash(key, i));
        }
        return result;
    }

    //hash函数，借鉴了hashmap的扰动算法，强烈建议大家把这个hash算法看懂，这个设计真的牛皮加闪电
    private int hash(Object key, int i) {
        int h;
        return key == null ? 0 : (i * (DEFAULT_SIZE - 1) & ((h = key.hashCode()) ^ (h >>> 16)));
    }
}

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

前缀树(Trie)

字典树，又称单词查找树或键树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：最大限度地减少无谓的字符串比较，查询效率比哈希表高。

Trie 的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。

三个基本性质：

• 根节点不包含字符，除根节点外每一个节点都只包含一个字符。
• 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
• 每个节点的所有子节点包含的字符都不相同。

class Trie {
    private class Node {
        Node[] childs = new Node[26];
        boolean isLeaf;
    }
    
    private Node root = new Node();
    
    public Trie() {
    }
    
    public void insert(String word) {
        insert(word, root);
    }
    
    private void insert(String word, Node node) {
        if (node == null) return;
        if (word.length() == 0) {
            node.isLeaf = true;
            return;
        }
        int index = indexForChar(word.charAt(0));
        if (node.childs[index] == null) {
            node.childs[index] = new Node();
        }
        insert(word.substring(1), node.childs[index]);
    }
    
    public boolean search(String word) {
        return search(word, root);
    }
    
    private boolean search(String word, Node node) {
        if (node == null) return false;
        if (word.length() == 0) return node.isLeaf;
        int index = indexForChar(word.charAt(0));
        return search(word.substring(1), node.childs[index]);
    }
    
    public boolean startsWith(String prefix) {
        return startWith(prefix, root);
    }
    
    private boolean startWith(String prefix, Node node) {
        if (node == null) return false;
        if (prefix.length() == 0) return true;
        int index = indexForChar(prefix.charAt(0));
        return startWith(prefix.substring(1), node.childs[index]);
    }
    
    private int indexForChar(char c) {
        return c - 'a';
    }
}
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