你好，我是看山。

本文分析下一個經(jīng)典面試題：如何在兩組10億數(shù)據(jù)中查找重復(fù)數(shù)據(jù)？

這個問題一般會有一個前提和一個約束：

1. 前提是內(nèi)存或存儲空間受限，不足以使用Map等數(shù)據(jù)結(jié)構(gòu)，即無法完全加載數(shù)據(jù)后再做對比；
2. 約束是重復(fù)數(shù)據(jù)的篩選粒度，是模糊篩選還是精確篩選，不同的約束需要使用不同的方式。

本文先講解下模糊篩選約束下如何實(shí)現(xiàn)。

分析考點(diǎn)

一般來說，面試題和我們之前的考試是相似的，每個問題都會有一個考察點(diǎn)。

那本題的考察點(diǎn)是什么呢？作為面試官，我希望從這個問題中考察同學(xué)的知識的寬度和對位圖的理解。

說實(shí)在的，隨著Java棧發(fā)展越來越完善，面試中的問題也越來越難。

回想十年前，面試能夠講清楚JMM，就已經(jīng)算是頭部選手的。但是十年后的今天，如果不會JMM，估計連一面都過不了。所以很多時候，都已經(jīng)跳過問這么簡單問題了。

整個行業(yè)都是如此，入門門檻越來越高，對應(yīng)屆生要求越來越高，要求大家更加專業(yè)。大勢如此，我們只能順勢而為。

第二個要考察的點(diǎn)是能夠想到資源有限，并能夠回答位圖的優(yōu)勢是占用資源少。

如果能夠答出這兩個點(diǎn)，這個題就是90分，如果再有更深的理解，我甚至可以忽略面試者不懂JMM。

紙上與躬行

紙上得來終覺淺，覺知此事需躬行。

我們直接編寫一下代碼，結(jié)束Guava的布隆過濾器。

public class FuzzyFilter {
    static final int nums = 1_000_000_000;

    // 創(chuàng)建布隆過濾器
    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("重復(fù)key數(shù)量為：" + count);
    }
}

我們先借助Guava生成布隆過濾器BloomFilter，我們定義下期望數(shù)量是10億，誤差率是0.0001，此時布隆過濾器占用位數(shù)是 19,170,116,754 位，需要使用13個hash函數(shù)。

差不多2.2G的空間，就可以處理10億的數(shù)據(jù)，相當(dāng)節(jié)省空間了。

到這里，是不是發(fā)現(xiàn)很簡單的一道題。很多時候，不是不會，而是沒見過。見過之后，發(fā)現(xiàn)，不過如此。

總結(jié)

本文介紹了如何在兩組10億數(shù)據(jù)中模糊查找重復(fù)數(shù)據(jù)，通過布隆過濾器的能力，實(shí)現(xiàn)2G空間實(shí)現(xiàn)10億個數(shù)據(jù)比對。