我們聊聊如何在兩組10億數據中查找重復數據？
作者：看山灬
回想十年前，面試能夠講清楚JMM，就已經算是頭部選手的。但是十年后的今天，如果不會JMM，估計連一面都過不了。所以很多時候，都已經跳過問這么簡單問題了。
你好，我是看山。
本文分析下一個經典面試題：如何在兩組10億數據中查找重復數據？
這個問題一般會有一個前提和一個約束：
- 前提是內存或存儲空間受限，不足以使用Map等數據結構，即無法完全加載數據后再做對比；
- 約束是重復數據的篩選粒度，是模糊篩選還是精確篩選，不同的約束需要使用不同的方式。
本文先講解下模糊篩選約束下如何實現。
分析考點
一般來說，面試題和我們之前的考試是相似的，每個問題都會有一個考察點。
那本題的考察點是什么呢？作為面試官，我希望從這個問題中考察同學的知識的寬度和對位圖的理解。
說實在的，隨著Java棧發展越來越完善，面試中的問題也越來越難。
回想十年前，面試能夠講清楚JMM，就已經算是頭部選手的。但是十年后的今天，如果不會JMM，估計連一面都過不了。所以很多時候，都已經跳過問這么簡單問題了。
整個行業都是如此，入門門檻越來越高，對應屆生要求越來越高，要求大家更加專業。大勢如此，我們只能順勢而為。
第二個要考察的點是能夠想到資源有限，并能夠回答位圖的優勢是占用資源少。
如果能夠答出這兩個點，這個題就是90分，如果再有更深的理解，我甚至可以忽略面試者不懂JMM。
紙上與躬行
紙上得來終覺淺，覺知此事需躬行。
我們直接編寫一下代碼，結束Guava的布隆過濾器。
public class FuzzyFilter {
static final int nums = 1_000_000_000;
// 創建布隆過濾器
static final BloomFilter<String> 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億個數據比對。
責任編輯：武曉燕
來源：
看山的小屋
