Java 海量数据处理方法总结
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 个散列函数时, 接受一个元素时 bitmap 中某一位置为 0 的概率为:
1 - 1/m -
k 个相互独立的散列函数, 接受一个元素时 bitmap 中某一位置为 0 的概率为:
(1 - 1/m)^2 -
假设原始集合中, 所有元素都不相等 (最严格的情况), 讲所有元素都输入 bloom filter, 此时某一位置仍为 0 的概率为:
( 1 - 1/m ) ^ {nk}
某一位置为 1 的概率为
1-(1-1/m)^{nk} -
当我们对某个元素进行判重时, 误判即这个元素对应的 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
数据库优化法
通过选择合适的数据库系统来优化数据处理
