如何判斷一個元素是否在億級資料是否存在
前幾天看到強哥(“純潔的微笑”)轉載的一篇文章《如何判斷一個元素是否在億級資料是否存在》。對其中的解決思路有一些不一樣的想法，先闡述一下問題：
題目要求
文章給出了思路：首先想到的是 Hash 演算法，它的時間複雜度是 O(1)，在常量時間判斷出資料是否存在。文章給出的辦法是直接使用了 Java 的集合物件 HashSet(內部用 HashMap 實現)。文章給出的結論是裝載資料太慢，直接討論了後面的一種方法—— Bloom Filter。最後發現 Bloom Filter 也不可能完美解決這個問題，有“誤判”。
總結一下題目的要求：
- 裝載資料儘可能的快
- 查詢速度儘可能的塊
- 資料判斷不存在誤判
演算法複雜度上考慮，最優的是 O(1)在常量級時間內完成查詢，以及基於 Hash 演算法。所以我的解決思路也是採用 Hash。
現代 CPU 多流水線完成 1000W 次迴圈是非常快的，所以理論上是“裝載資料”應該是非常塊的。上面文章中提到的裝載資料太慢其實是由於HashSet 的 put 方法裡面有複雜的邏輯——畢竟 HashSet 是一個通用的 Hash 演算法。
新思路
1000W 條資料，我們可以用 1000W 個二進位制位表示，初始化為全 0 如果某個資料存在，就置為 1。。Java 中沒有辦法直接操作一大塊連續記憶體空間，我用一個 int 型別的陣列表示，每個陣列元素可以表示 32 個元素。比如分別裝載 5、13、29(注意：位元組順序)。
這些資料都小於 32，放在第一個陣列元素就可以了。程式碼如下：
1000W 條資料有可能是在 1-100 以內取，只需要 100 個 bit 就可以了;也可能是在 1-1000W 以內取，此時需要 1000W 個 bit。所以單獨用一個變數boundOfData表示資料的上限，需要的 bit 數量則是 boundOfData，每個 int 是 32 個 bit ，計算需要的陣列數量是boundOfData/32 後向上取整。
資料除32 商是陣列下標，餘數是相應的 bit 位置。比如 10，它應該在第一個陣列元素的，第 10 個 bit 位，定位到位置後只要通過位運算設定為 1 就行了。判斷的時候只要按同樣的演算法定位到陣列位置，判斷某個 bit 為是否為 1。
我們測試一下速度，某次執行結果
分析一下演算法：
裝載資料部分是 O(N)——即線性複雜度，這個是沒有辦法避免的。查詢部分是 O(1)——常量級。當然這裡肯定不會存在“誤判”，因為每個資料都會被準確的 Hash。
看一下空間複雜度，1000W 的資料需要 312500 個 int 型別的資料大概是 1.1M 記憶體空間。
我嘗試了 1 一條資料，大概 13 秒;如果不用隨機數(直接用下標)大概是 200 ms。
總結
其實面試問題很多情況下不是考察你是否知道答案，而是解題過程。希望在資訊爆炸的今天，我們能夠靜下心來分析一個問題，仔細思考它的答案。
答案是什麼?誰還在乎這個，我們思考的過程才是最有價值的部分。
【本文是51CTO專欄作者“邢森”的原創文章，轉載請聯絡作者本人獲取授權】
ofollow,noindex" target="_blank">戳這裡，看該作者更多好文