大資料計數原理1+0=1這你都不會算(二)

<a href="http://s1.51cto.com/wyfs02/M01/06/64/wKiom1m3isTStBFcAABqA28wgvU877.jpg-wh_651x-s_2561526470.jpg" target="_blank"></a>

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

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

<a href="http://s5.51cto.com/wyfs02/M00/A5/15/wKioL1m3iBGCf6JFAAA9NfT-zvo426.jpg" target="_blank"></a>

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

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

<a href="http://s1.51cto.com/wyfs02/M01/A5/15/wKioL1m3iDii1QqPAAA-XzmMbwg848.jpg" target="_blank"></a>

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

<a href="http://s1.51cto.com/wyfs02/M02/06/64/wKiom1m3iI6yIYVSAABBVFh0Moc477.jpg" target="_blank"></a>

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

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

那有小夥伴就有疑問了，如果超過了32個數字怎麼辦?

可以使用數組來進行拓展，比如一個a = int[2]的數組。

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

相比較于HashSet，BitMap 進行統計所使用的存儲隻需要 HashSet 的1/32。但是這個資料結構簡單，相對于 HashSet 有一點小問題，就是hash在資料量巨大的情況下，碰撞會比較嚴重，那麼統計精度會下降，需要怎麼改善呢?

本文作者：大蕉

來源：51CTO