Java 程序员面试宝典 笔记

• Hash 法
• Bit-map 法
• Bloom filter 法
• 数据库优化法
• 倒排索引法
• 外排序法
• Trie 树
• 堆
• 双层桶法
• MapReduce 法

Hash 法

散列

• hash 函数尽可能简单
• 函数的值域必须在散列表的范围内
• 尽可能减少冲突

Bit-map 法

位图 法的基本原理是使用位数组成来表示某些元素是否存在. 本方法适用于海量数据的快速查找/判重/删除等等.
与其说是算法, 不如说是一种紧凑的数据结构.

Bloom filter 法 (重点)

引入了 K (K>1)个相互独立的哈希函数, 保证在给定的空间, 误判率下, 完成元素判定重复的过程. 图是 k = 3 时的 bloom filter.

bloom filter k = 3

x, y, z 经由哈希函数映射将各自在 bitmap 中的三个位置置为 1, 当 w 出现时,仅当 3 个标志位都为 1 时, 才表示 w 在集合中. 图中的情况会判定为 w 不在集合中.

bloom filter 的误差

假设所有哈希函数散列足够均匀, 散列后落到 bitmap 每个位置的 概率均等. bitmap 的大小为 m, 原始数集大小为 n, 哈希函数个数为 k:

1. 1 个散列函数时, 接受一个元素时 bitmap 中某一位置为 0 的概率为:
   1 - 1/m

2. k 个相互独立的散列函数, 接受一个元素时 bitmap 中某一位置为 0 的概率为:
   (1 - 1/m)^2

3. 假设原始集合中, 所有元素都不相等 (最严格的情况), 讲所有元素都输入 bloom filter, 此时某一位置仍为 0 的概率为:
   ( 1 - 1/m ) ^ {nk}
   某一位置为 1 的概率为
   1-(1-1/m)^{nk}

4. 当我们对某个元素进行判重时, 误判即这个元素对应的 k 个标志位不全为 1, 但所有 k 个标志位都被置为 1, 误判率 \epsilon 约为:
   \epsilon \approx [1-(1-1/m)^{nk} ]^k
   这个误判率比实际比值大, 因为讲判断正确的情况也算进去了. 根据极限 {\lim_{n \to \infty}}(1+1/n)^n = e 可以得到:
   \epsilon \approx [1-e^{-{nk}/m} ]^k
   \epsilon得到最优解,当且仅当
   k={m/n}In2 \approx 0.7* {m/n}
   此时, 误判率 \epsilon 与数集大小和
   \epsilon \approx (1-e^{-In2})^{-In2* m/n}=0.5^{In2*m/n} = 0.5^k

同时, 由于硬盘空间时限制死的, 集合元素个数 n 的大小反而与单个数据的比特数成反比, 数据长度为 64 bit 时,
n= 5TB/64bit = 5 * 2^{40} Byte / 8 Byte \approx 2^{34}

若以 m = 16n 计算, bitmap 集合的大小为
2^{38}Bit = 2^{35} Byte = 32 GB, 此时的 \epsilon \approx 0.0005, 这是误差的上限.

bloom filter 通过引入一定的错误率, 使得海量数据判重在可以接受的内存代价中得以实现, 从上述公式可以看出, 随着集合中的元素不断输入过滤器中(n增大), 误差将越来越大. 但是, 当 bitmap 的大小 m (指 bit 数)足够大时, 比如比 所有可能出现的不重复元素个数 还要大 10 倍以上时, 错误概率时可以接受的.

import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;
import java.util.HashSet;
import java.util.Random;

public class testBloomFilter {

    static int sizeOfNumberSet = Integer.MAX_VALUE >> 4;

    static Random generator = new Random();

    public static void main(String[] args) {

        int error = 0;
        HashSet<Integer> hashSet = new HashSet<Integer>();
        BloomFilter<Integer> filter = BloomFilter.create(Funnels.integerFunnel(), sizeOfNumberSet);

        for(int i = 0; i < sizeOfNumberSet; i++) {
            int number = generator.nextInt();
            if(filter.mightContain(number) != hashSet.contains(number)) {
                error++;
            }
            filter.put(number);
            hashSet.add(number);
        }

        System.out.println("Error count: " + error + ", error rate = " + String.format("%f", (float)error/(float)sizeOfNumberSet));
    }
}

参考: https://blog.csdn.net/zdxiq000/article/details/57626464

数据库优化法

通过选择合适的数据库系统来优化数据处理

倒排索引法

外排序法

Trie 法

堆

双层桶法

MapReduce 法