1. BitMap介紹

BitMap可以理解為通過一個bit數(shù)組來存儲特定數(shù)據(jù)的一種數(shù)據(jù)結(jié)構(gòu)。BitMap常用于對大量整形數(shù)據(jù)做去重和查詢。
在這類查找中，我們可以通過map數(shù)據(jù)結(jié)構(gòu)進(jìn)行查找。但如果數(shù)據(jù)量比較大map數(shù)據(jù)結(jié)構(gòu)將會大量占用內(nèi)存。
BitMap用一個比特位來映射某個元素的狀態(tài)，所以這種數(shù)據(jù)結(jié)構(gòu)是非常節(jié)省存儲空間的。

BitMap用途

• BitMap用于數(shù)據(jù)去重
  BitMap可用于數(shù)據(jù)的快速查找，判重。
• BitMap用于快速排序
  BitMap由于其本身的有序性和唯一性，可以實(shí)現(xiàn)快速排序：將其加入bitmap中，然后再遍歷獲取出來，從而得到排序的結(jié)果。

如何判斷數(shù)字在bit數(shù)組的位置

在后面的代碼中，我們使用[]byte來存儲bit數(shù)據(jù)，由于一個byte有8個二進(jìn)制位。因此：

• 數(shù)字/8=數(shù)字在字節(jié)數(shù)組中的位置。
• 數(shù)字%8=數(shù)字在當(dāng)前字節(jié)中的位置。
  例如：數(shù)字10，
• 10/8=1，即數(shù)字10對應(yīng)的字節(jié)數(shù)組的位置為：1
• 10%8=2，即數(shù)字10對應(yīng)的當(dāng)前字節(jié)的位置為：2

設(shè)置數(shù)據(jù)到bit數(shù)組

• num/8得到數(shù)字在字節(jié)數(shù)組中的位置 => row
• num%8得到數(shù)字在當(dāng)前字節(jié)中的位置 => col
• 將1左移col位，然后和以前的數(shù)據(jù)做|運(yùn)算，這樣就可以將col位置的bit替換成1了。

從bit數(shù)組中清除數(shù)據(jù)

• num/8得到數(shù)字在字節(jié)數(shù)組中的位置 => row
• num%8得到數(shù)字在當(dāng)前字節(jié)中的位置 => col
• 將1左移col位，然后對取反，再與當(dāng)前值做&，這樣就可以將col位置的bit替換成0了。

數(shù)字是否在bit數(shù)組中

• num/8得到數(shù)字在字節(jié)數(shù)組中的位置 => row
• num%8得到數(shù)字在當(dāng)前字節(jié)中的位置 => col
• 將1左移col位，然后和以前的數(shù)據(jù)做&運(yùn)算，若該字節(jié)的值!=0，則說明該位置是1，則數(shù)據(jù)在bit數(shù)組中，否則數(shù)據(jù)不在bit數(shù)組中。

2. Go語言位運(yùn)算

在Go語言中支持以下幾種操作位的方式：

• & 按位與：兩者全為1結(jié)果為1，否則結(jié)果為0
• | 按位或：兩者有一個為1結(jié)果為1，否則結(jié)果為0
• ^ 按位異或：兩者不同結(jié)果為1，否則結(jié)果為0
• &^ 按位與非：是"與"和"非"操作符的簡寫形式
• << 按位左移：
• >> 按位右移：

左移

將二進(jìn)制向左移動，右邊空出的位用0填補(bǔ)，高位左移溢出則舍棄該高位。
由于每次移位數(shù)值會翻倍，所以通常用代替乘2操作。當(dāng)然這是建立在移位沒有溢出的情況。
例如：1<<3 相當(dāng)于1×8=8，3<<4 相當(dāng)于3×16=48

右移

將整數(shù)二進(jìn)制向右移動，左邊空出的位用0或者1填補(bǔ)。正數(shù)用0填補(bǔ)，負(fù)數(shù)用1填補(bǔ)。
負(fù)數(shù)在內(nèi)存中的二進(jìn)制最高位為符號位——使用1表示，所以為了保證移位之后符號位的正確性，所以需要在高位補(bǔ)1。
相對于左移來說，右移通常用來代替除2操作。
例如：24>>3 相當(dāng)于24÷8=3

使用&^和位移運(yùn)算來給某一位置0

這個操作符通常用于清空對應(yīng)的標(biāo)志位，例如 a = 0011 1010，如果想清空第二位，則可以這樣操作:
a &^ 0000 0010 = 0011 1000

3. BitMap的Go語言實(shí)現(xiàn)

接下來我們給出BitMap的Go語言實(shí)現(xiàn)，目前代碼已經(jīng)上傳到github中，下載地址

定義

首先給出BitMap結(jié)構(gòu)的定義：

type BitMap struct {
    bits []byte
    vmax uint
}

創(chuàng)建BitMap結(jié)構(gòu)

func NewBitMap(max_val ...uint) *BitMap {
    var max uint = 8192
    if len(max_val) > 0 && max_val[0] > 0 {
        max = max_val[0]
    }
    bm := &BitMap{}
    bm.vmax = max
    sz := (max + 7) / 8
    bm.bits = make([]byte, sz, sz)
    return bm
}

將數(shù)據(jù)添加到BitMap

func (bm *BitMap)Set(num uint) {
    if num > bm.vmax {
        bm.vmax += 1024
        if bm.vmax < num {
            bm.vmax = num
        }
        dd := int(num+7)/8 - len(bm.bits)
        if dd > 0 {
            tmp_arr := make([]byte, dd, dd)
            bm.bits = append(bm.bits, tmp_arr...)
        }
    }
    //將1左移num%8后，然后和以前的數(shù)據(jù)做|，這樣就替換成1了
    bm.bits[num/8] |= 1 << (num%8)
}

從BitMap中刪除數(shù)據(jù)

func (bm *BitMap)UnSet(num uint) {
    if num > bm.vmax {
        return
    }
    //&^:將1左移num%8后，然后進(jìn)行與非運(yùn)算，將運(yùn)算符左邊數(shù)據(jù)相異的位保留，相同位清零
    bm.bits[num/8] &^= 1 << (num%8)
}

判斷BitMap中是否存在指定的數(shù)據(jù)

func (bm *BitMap)Check(num uint) bool {
    if num > bm.vmax {
        return false
    }
    //&:與運(yùn)算符，兩個都是1，結(jié)果為1
    return bm.bits[num/8] & (1 << (num%8)) != 0
}

以上就是go數(shù)據(jù)結(jié)構(gòu)和算法BitMap原理及實(shí)現(xiàn)示例的詳細(xì)內(nèi)容，更多關(guān)于go數(shù)據(jù)結(jié)構(gòu)算法BitMap的資料請關(guān)注腳本之家其它相關(guān)文章！

最新評論