知识点回顾

布隆过滤器

  1. 流程
    • 准备 k 个 hash 函数，每个函数可以把 key 散列成为一个整数
    • 初始化一个尽可能长的比特数组，每个比特位初始化为0
    • 某个key加入集合时，用k个 hash 函数算出 k 个散列值，并把比特数组中对应的比特位置为1
    • 判断某个key是否在集合时，用 k 个hash 函数算出k 个散列值，并查询比特数组中所有的 k 个位置，如果都为 1，认为在集合中。
  2. 特点
    • 如果 key 在集合中，那么一定可以判断出来在；但是如果元素不在集合中，有可能会误判这个元素在集合中。
    • 无法删除！（因为并不能确定某个位置是因为删除的元素而被设为1的！）

bitmap

  1. 利用内存中连续的二进制位，来对大量整形数据做重和查询！
  2. 不仅方便，还可以去掉重复的整型数，而且做并集和交集也很方便
  3. 可以解决用户和标签的问题，以标签为key，然后将用户存储在bitmap中
  4. bitmap无法做非运算，比如从标签90后对应的bitmap中可以查询到哪些用户是90后，但是无法查出哪些不是九零后；解决方法是添加一个全量bitmap，那些在全量位图，且不在90后位图中的用户都是非90后。
  5. 可以用 int 类型的数组或者 long 类型的数组来实现 bitmap。
  6. java中的两个优化的比较好的位图包：RoaringBitmap 和 JavaEWAH.
 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

import java.util.ArrayList;
import java.util.List;

public class BitMap {
    // 需要存放的数据个数
    private static final int N = 200000000;
    // 用一个 int 类型的数组作为位图，一个int最多可以存放32个整型数（4字节32位！）
    // 相当于压缩了 32 倍的空间！
    private int[] a = new int[N >> 32 + 1];

    /**
     * 设置 n 所在的bit位为 1
     *
     * @param n
     */
    public void addValue(int n) {
        // 计算 n 在数组 a 中的下标
        int row = n >> 5;
        // 计算 n 在a[row] 元素中的下标
        // 相当于 a[row] = a[row] | (2^(n%32))
        a[row] |= 1 << (n & 0x1F);
    }

    public boolean isExist(int n) {
        /**
         * 判断 n 所在比特位是否为1
         */
        int row = n >> 5;
        return (a[row] & (1 << (n & 0x1F))) != 0;
    }

    public void display(int begin, int end) {
        /**
         * 展示部分位图
         */
        System.out.println("BitMap位图展示");
        for (int i = begin; i < end; i++) {
            List<Integer> list = new ArrayList<Integer>();
            int temp = a[i];
            for (int j = 0; j < 32; j++) {
                list.add(temp & 1);
                temp >>= 1;
            }
            System.out.println("a[" + i + "]" + list);
        }
    }

    public static void main(String[] args) {
        BitMap bm = new BitMap();
        bm.addValue(12);
        bm.addValue(100000000);
        System.out.println(bm.isExist(100000000));
        bm.display(0, 1);
    }

}

哈希分桶

  1. 通过哈希函数来对数据进行划分，将不同的划分安排给不同的机器或者分为不同的文件批次处理。
  2. 哈希分桶的优点在于可以将相同的数据分到同一文件中，也就是说不同的划分间不存在相同的元素！
  3. MapReduce的本质就是哈希分桶？

需要保持敏感的数据

  1. $1GB = 2^{10}MB = 2^{20}KB = 2^{30}B = 2^{33}bit$
  2. $100亿 \approx 2^{34} $, $10亿 \approx 2^{30}$
  3. 所以 1GB 用位图的话，至少可以存放10亿个数。

常见题目

出现次数最多的IP

给一个超过100G大小的log file，log中存着IP地址，设计算法找到出现次数最多的IP地址.

  1. 哈希分桶法
    • 将100G文件分成1000份，将每个IP地址映射到相应文件中（%1000）
    • 在每个文件中分别找出出现频率最高的IP，得到1000个IP
    • 再从1000个IP中找出频率最高的IP

只出现一次的数

给定100亿个整数，设计算法找到只出现一次的整数

  1. 哈希分桶法
  2. 位图法
    • 00 表示没出现过
    • 01 表示出现一次
    • 10 表示出现过一次以上

两个文件的交集

给两个我呢见，分别有100亿个整数（去重后不超过10亿），我们只有1G内存，如何找到两个文件的交集

  1. 位图法
    • 每个数用两位表示，00表示在两个文件中均没出现过，01表示在文件1中出现，10 表示izai文件2中出现，11表示在两个文件中都出现过
    • 先遍历文件1中所有整数作出标记，再遍历文件2中的整数。
    • 所有被标为 11 的数都是在两个文件中都出现过的数
  2. 哈希分桶
    • 将两个文件分别分为N个小文件，然后小文件之间分别求交集
    • 将所有的N个交集合并即可
  3. 布隆过滤器（近似算法？？？）

给出若干个文件，统计这些文件中不重复数据的个数。

  1. 哈希分桶法
  2. 位图法

如何扩展布隆过滤器使得它支持删除/计数操作？

  1. 将BloomFilter中的每一位扩展为一个计数器，记录有多少个hash函数映射到这一位；删除的时候，只有当引用计数变为0时，才真正将该位置为0。
  2. 将BloomFilter中的每一位扩展为一个计数器，每个输入元素都要把对应位置加1，从而支持计数操作。计数个数为所有映射到的位置计数的最小值（？？？）

有一个词典，包含N个英文单词，现在任意给一个字符串，设计算法找出包含这个字符串的所有英文单词。

  1. 字典树？

有一百万个数，是在1到一亿当中随机取值，找出这一亿个数中没出现的数

  1. 位图

100亿个整数如何找到中位数？

  1. 内存够用：快速选择（快排变形）（时间复杂度是O(N)和构建堆的时间复杂度一样）
  2. 内存不够用且无重复数据：bitmap
  3. 内存不够，且有重复数据：哈希分桶？按照每个数的最高8位进行分桶（最多255个桶），这样的话桶之间就有了大小关系，方便找中位数。