大數據計數原理1+0=1這你都不會算(二)No.50

02-12

上一次我們說完了用 HashSet 來進行計數了。我們可以發現，如果我們估計有N個數，那麼我們至少需要N*32bit（按照int在32位操作系統下佔用32個bit）的空間來進行存儲，這太費錢了。有沒有辦法進行改進呢？這就引出了一個新的數據結構 - BitMap。

這時候看到一張圖代表了一個存儲int的位元組bit信息。

我們可以發現，每一個bit都有自己的值，比如一個int的空間除了作為int類型的數字外，是否還可以做其他的利用？數字可以表示0~31位置的情況，如果我們使用bit的位置信息來存儲會怎樣？我們來試試看。

如果我們得到Hash的值為0，那就直接將第0位置上的bit位置為1。

如果我們得到Hash的值為31，那就直接將第31上的bit位置為1。

如果發現位置上已經有值了，那當前的值就已經存在了，不再進行統計，這樣子就可以完成超大數據量的統計啦。

這樣進行存儲的數據結構就叫BitMap，使用每個bit位來進行信息存儲，而不是一個int數字。

那有小夥伴就有疑問了，如果超過了32個數字怎麼辦？可以使用數組來進行拓展，比如一個a = int[2]的數組。

a[0] 可以表示0~31位，a[1] 可以表示32~63位，以此類推，幾乎可以無限大。如果數據確實非常巨大，連下標也到達int的界限了，也可以用其他的單個空間更大的數據類型來進行存儲。

相比較於HashSet，BitMap 進行統計所使用的存儲只需要 HashSet 的1/32。但是這個數據結構簡單，相對於 HashSet 有一點小問題，就是hash在數據量巨大的情況下，碰撞會比較嚴重，那麼統計精度會下降，需要怎麼改善呢？請關注下一篇布隆過濾器。