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

題目要求

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

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

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

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

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

新思路

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

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

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

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

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

分析一下算法：

裝載數(shù)據(jù)部分是 O(N)——即線性復(fù)雜度，這個是沒有辦法避免的。查詢部分是 O(1)——常量級。當(dāng)然這里肯定不會存在“誤判”，因為每個數(shù)據(jù)都會被準確的 Hash。

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

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

總結(jié)

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

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

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

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