一、概述

本文將講述Bit-Map演算法的相關原理,Bit-Map演算法的一些利用場景，例如BitMap解決海量數據尋找重複、判斷個別元素是否在海量數據當中等問題.最後說說BitMap的特點已經在各個場景的使用性。

二、Bit-Map演算法

先看看這樣的一個場景（來自《編程珠璣》）：給一台普通PC，2G內存，要求處理一個包含40億個不重複並且沒有排過序的無符號的int整數，給出一個整數，問如果快速地判斷這個整數是否在文件40億個數據當中？

問題思考：

40億個int占（40億*4）/1024/1024/1024 大概為14.9G左右，很明顯內存只有2G，放不下，因此不可能將這40億數據放到內存中計算。

要快速的解決這個問題最好的方案就是將數據擱內存了，所以現在的問題就在如何在2G內存空間以內存儲著40億整數。

一個int整數在golang中是佔4個位元組的即要32bit位，如果能夠用一個bit位來標識一個int整數那麼存儲空間將大大減少，算一下40億個int需要的內存空間為40億/8/1024/1024大概為476.83 mb，這樣的話我們完全可以將這40億個int數放到內存中進行處理。

具體思路：

1個int佔4位元組即4*8=32位，那麼我們只需要申請一個int數組長度為 int tmp[1+N/32]即可存儲完這些數據，其中N代表要進行查找的總數，tmp中的每個元素在內存在佔32位可以對應表示十進位數0~31,所以可得到BitMap表:

tmp[0]:可表示0~31

tmp[1]:可表示32~63

tmp[2]可表示64~95

如何判斷int數字在tmp數組的哪個下標？

這個其實可以通過直接除以32取整數部分，例如：整數8除以32取整等於0，那麼8就在tmp[0]上。另外，我們如何知道了8在tmp[0]中的32個位中的哪個位，這種情況直接mod上32就ok，又如整數8，在tmp[0]中的第8 mod上32等於8，那麼整數8就在tmp[0]中的第八個bit位（從右邊數起）。

go簡單實現：

package bitmap

import (
"bytes"
"fmt"
)

type Bitmap struct {
words []uint64
length int
}

func New() *Bitmap {
return &Bitmap{}
}
func (bitmap *Bitmap) Has(num int) bool {
word, bit := num/64, uint(num%64)
return word < len(bitmap.words) && (bitmap.words[word]&(1<<bit)) != 0
}

func (bitmap *Bitmap) Add(num int) {
word, bit := num/64, uint(num%64)
for word >= len(bitmap.words) {
bitmap.words = append(bitmap.words, 0)
}
// 判斷num是否已經存在bitmap中
if bitmap.words[word]&(1<<bit) == 0 {
bitmap.words[word] |= 1 << bit
bitmap.length++
}
}

func (bitmap *Bitmap) Len() int {
return bitmap.length
}

func (bitmap *Bitmap) String() string {
var buf bytes.Buffer
buf.WriteByte({)
for i, v := range bitmap.words {
if v == 0 {
continue
}
for j := uint(0); j < 64; j++ {
if v&(1<<j) != 0 {
if buf.Len() > len("{") {
buf.WriteByte( )
}
fmt.Fprintf(&buf, "%d", 64*uint(i)+j)
}
}
}
buf.WriteByte(})
fmt.Fprintf(&buf,"
Length: %d", bitmap.length)
return buf.String()
}

推薦閱讀：

相关文章