前幾天看到強(qiáng)哥(“純潔的微笑”)轉(zhuǎn)載的一篇文章《如何判斷一個(gè)元素是否在億級(jí)數(shù)據(jù)是否存在》。對(duì)其中的解決思路有一些不一樣的想法，先闡述一下問題：

題目要求

文章給出了思路：首先想到的是 Hash 算法，它的時(shí)間復(fù)雜度是 O(1)，在常量時(shí)間判斷出數(shù)據(jù)是否存在。文章給出的辦法是直接使用了 Java 的集合對(duì)象 HashSet(內(nèi)部用 HashMap 實(shí)現(xiàn))。文章給出的結(jié)論是裝載數(shù)據(jù)太慢，直接討論了后面的一種方法—— Bloom Filter。***發(fā)現(xiàn) Bloom Filter 也不可能***解決這個(gè)問題，有“誤判”。

總結(jié)一下題目的要求：

• 裝載數(shù)據(jù)盡可能的快
• 查詢速度盡可能的塊
• 數(shù)據(jù)判斷不存在誤判

算法復(fù)雜度上考慮，***的是 O(1)在常量級(jí)時(shí)間內(nèi)完成查找，以及基于 Hash 算法。所以我的解決思路也是采用 Hash。

現(xiàn)代 CPU 多流水線完成 1000W 次循環(huán)是非?？斓?，所以理論上是“裝載數(shù)據(jù)”應(yīng)該是非常塊的。上面文章中提到的裝載數(shù)據(jù)太慢其實(shí)是由于HashSet 的 put 方法里面有復(fù)雜的邏輯——畢竟 HashSet 是一個(gè)通用的 Hash 算法。

新思路

1000W 條數(shù)據(jù)，我們可以用 1000W 個(gè)二進(jìn)制位表示，初始化為全 0 如果某個(gè)數(shù)據(jù)存在，就置為 1。。Java 中沒有辦法直接操作一大塊連續(xù)內(nèi)存空間，我用一個(gè) int 類型的數(shù)組表示，每個(gè)數(shù)組元素可以表示 32 個(gè)元素。比如分別裝載 5、13、29(注意：字節(jié)順序)。

這些數(shù)據(jù)都小于 32，放在***個(gè)數(shù)組元素就可以了。代碼如下：

1000W 條數(shù)據(jù)有可能是在 1-100 以內(nèi)取，只需要 100 個(gè) bit 就可以了;也可能是在 1-1000W 以內(nèi)取，此時(shí)需要 1000W 個(gè) bit。所以單獨(dú)用一個(gè)變量boundOfData表示數(shù)據(jù)的上限，需要的 bit 數(shù)量則是 boundOfData，每個(gè) int 是 32 個(gè) bit ，計(jì)算需要的數(shù)組數(shù)量是boundOfData/32 后向上取整。

數(shù)據(jù)除32 商是數(shù)組下標(biāo)，余數(shù)是相應(yīng)的 bit 位置。比如 10，它應(yīng)該在***個(gè)數(shù)組元素的，第 10 個(gè) bit 位，定位到位置后只要通過位運(yùn)算設(shè)置為 1 就行了。判斷的時(shí)候只要按同樣的算法定位到數(shù)組位置，判斷某個(gè) bit 為是否為 1。

我們測(cè)試一下速度，某次執(zhí)行結(jié)果

分析一下算法：

裝載數(shù)據(jù)部分是 O(N)——即線性復(fù)雜度，這個(gè)是沒有辦法避免的。查詢部分是 O(1)——常量級(jí)。當(dāng)然這里肯定不會(huì)存在“誤判”，因?yàn)槊總€(gè)數(shù)據(jù)都會(huì)被準(zhǔn)確的 Hash。

看一下空間復(fù)雜度，1000W 的數(shù)據(jù)需要 312500 個(gè) int 類型的數(shù)據(jù)大概是 1.1M 內(nèi)存空間。

我嘗試了 1 一條數(shù)據(jù)，大概 13 秒;如果不用隨機(jī)數(shù)(直接用下標(biāo))大概是 200 ms。

總結(jié)

其實(shí)面試問題很多情況下不是考察你是否知道答案，而是解題過程。希望在信息爆炸的今天，我們能夠靜下心來分析一個(gè)問題，仔細(xì)思考它的答案。

答案是什么?誰還在乎這個(gè)，我們思考的過程才是最有價(jià)值的部分。

【本文是51CTO專欄作者“邢森”的原創(chuàng)文章，轉(zhuǎn)載請(qǐng)聯(lián)系作者本人獲取授權(quán)】

戳這里，看該作者更多好文