你好，我是看山。

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

這個(gè)問(wèn)題一般會(huì)有一個(gè)前提和一個(gè)約束：

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

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

分析考點(diǎn)

一般來(lái)說(shuō)，面試題和我們之前的考試是相似的，每個(gè)問(wèn)題都會(huì)有一個(gè)考察點(diǎn)。

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

說(shuō)實(shí)在的，隨著Java棧發(fā)展越來(lái)越完善，面試中的問(wèn)題也越來(lái)越難。

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

整個(gè)行業(yè)都是如此，入門(mén)門(mén)檻越來(lái)越高，對(duì)應(yīng)屆生要求越來(lái)越高，要求大家更加專(zhuān)業(yè)。大勢(shì)如此，我們只能順勢(shì)而為。

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

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

紙上與躬行

紙上得來(lái)終覺(jué)淺，覺(jué)知此事需躬行。

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

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

    // 創(chuàng)建布隆過(guò)濾器
    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生成布隆過(guò)濾器BloomFilter，我們定義下期望數(shù)量是10億，誤差率是0.0001，此時(shí)布隆過(guò)濾器占用位數(shù)是 19,170,116,754 位，需要使用13個(gè)hash函數(shù)。

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

到這里，是不是發(fā)現(xiàn)很簡(jiǎn)單的一道題。很多時(shí)候，不是不會(huì)，而是沒(méi)見(jiàn)過(guò)。見(jiàn)過(guò)之后，發(fā)現(xiàn)，不過(guò)如此。

總結(jié)

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