本文分析下一个经典面试题：如何在两组10亿数据中查找重复数据？
这个问题一般会有一个前提和一个约束：
- 前提是内存或存储空间受限，不足以使用Map等数据结构，即无法完全加载数据后再做对比；
- 约束是重复数据的筛选粒度，是模糊筛选还是精确筛选，不同的约束需要使用不同的方式。
本文先讲解下模糊筛选约束下如何实现。
分析考点
一般来说，面试题和我们之前的考试是相似的，每个问题都会有一个考察点。
那本题的考察点是什么呢？作为面试官，我希望从这个问题中考察同学的知识的宽度和对位图的理解。
说实在的，随着Java栈发展越来越完善，面试中的问题也越来越难。
回想十年前，面试能够讲清楚JMM，就已经算是头部选手的。但是十年后的今天，如果不会JMM，估计连一面都过不了。所以很多时候，都已经跳过问这么简单问题了。
整个行业都是如此，入门门槛越来越高，对应届生要求越来越高，要求大家更加专业。大势如此，我们只能顺势而为。
第二个要考察的点是能够想到资源有限，并能够回答位图的优势是占用资源少。
如果能够答出这两个点，这个题就是90分，如果再有更深的理解，我甚至可以忽略面试者不懂JMM。
纸上与躬行
纸上得来终觉浅，觉知此事需躬行。
我们直接编写一下代码，结束Guava的布隆过滤器。
public class FuzzyFilter {
static final int nums = 1_000_000_000;
// 创建布隆过滤器
static final BloomFilter bloomFilter = BloomFilter.create(Funnels.stringFunnel(UTF_8), nums, 0.0001);
public void add(String key) {
bloomFilter.put(key);
}
public boolean contains(String key) {
return bloomFilter.mightContain(key);
}
public static void main(String[] args) {
final FuzzyFilter fuzzyFilter = new FuzzyFilter();
final Random random = new Random(Integer.MIN_VALUE);
for (int i = 0; i < nums; i++) {
final String key = random.nextInt() + "";
fuzzyFilter.add(key);
}
int count = 0;
for (int i = 0; i < nums; i++) {
final String key = random.nextInt() + "";
if (fuzzyFilter.contains(key)) {
count++;
}
}
System.out.println("重复key数量为：" + count);
}
} 我们先借助Guava生成布隆过滤器BloomFilter，我们定义下期望数量是10亿，误差率是0.0001，此时布隆过滤器占用位数是 19,170,116,754 位，需要使用13个hash函数。
差不多2.2G的空间，就可以处理10亿的数据，相当节省空间了。
到这里，是不是发现很简单的一道题。很多时候，不是不会，而是没见过。见过之后，发现，不过如此。
总结
本文介绍了如何在两组10亿数据中模糊查找重复数据，通过布隆过滤器的能力，实现2G空间实现10亿个数据比对。
