go資料結構和演演算法BitMap原理及實現範例

2022-07-22 18:01:06

1. BitMap介紹

BitMap可以理解為通過一個bit陣列來儲存特定資料的一種資料結構。BitMap常用於對大量整形資料做去重和查詢。
在這類查詢中，我們可以通過map資料結構進行查詢。但如果資料量比較大map資料結構將會大量佔用記憶體。
BitMap用一個位元位來對映某個元素的狀態，所以這種資料結構是非常節省儲存空間的。

BitMap用途

BitMap用於資料去重
BitMap可用於資料的快速查詢，判重。
BitMap用於快速排序
BitMap由於其本身的有序性和唯一性，可以實現快速排序：將其加入bitmap中，然後再遍歷獲取出來，從而得到排序的結果。

如何判斷數位在bit陣列的位置

在後面的程式碼中，我們使用[]byte來儲存bit資料，由於一個byte有8個二進位制位。因此：

數位/8=數位在位元組陣列中的位置。
數位%8=數位在當前位元組中的位置。
例如：數位10，
10/8=1，即數位10對應的位元組陣列的位置為：1
10%8=2，即數位10對應的當前位元組的位置為：2

設定資料到bit陣列

num/8得到數位在位元組陣列中的位置 => row
num%8得到數位在當前位元組中的位置 => col
將1左移col位，然後和以前的資料做|運算，這樣就可以將col位置的bit替換成1了。

從bit陣列中清除資料

num/8得到數位在位元組陣列中的位置 => row
num%8得到數位在當前位元組中的位置 => col
將1左移col位，然後對取反，再與當前值做&，這樣就可以將col位置的bit替換成0了。

數位是否在bit陣列中

num/8得到數位在位元組陣列中的位置 => row
num%8得到數位在當前位元組中的位置 => col
將1左移col位，然後和以前的資料做&運算，若該位元組的值!=0，則說明該位置是1，則資料在bit陣列中，否則資料不在bit陣列中。

2. Go語言位運算

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

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

左移

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

右移

將整數二進位制向右移動，左邊空出的位用0或者1填補。正數用0填補，負數用1填補。
負數在記憶體中的二進位制最高位為符號位——使用1表示，所以為了保證移位之後符號位的正確性，所以需要在高位補1。
相對於左移來說，右移通常用來代替除2操作。
例如：24>>3 相當於24÷8=3

使用&^和位移運算來給某一位置0

這個操作符通常用於清空對應的標誌位，例如 a = 0011 1010，如果想清空第二位，則可以這樣操作:
a &^ 0000 0010 = 0011 1000

3. BitMap的Go語言實現

接下來我們給出BitMap的Go語言實現，目前程式碼已經上傳到github中，下載地址

定義

首先給出BitMap結構的定義：

type BitMap struct {
    bits []byte
    vmax uint
}

建立BitMap結構

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
}

將資料新增到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後，然後和以前的資料做|，這樣就替換成1了
    bm.bits[num/8] |= 1 << (num%8)
}

從BitMap中刪除資料

func (bm *BitMap)UnSet(num uint) {
    if num > bm.vmax {
        return
    }
    //&^:將1左移num%8後，然後進行與非運算，將運運算元左邊資料相異的位保留，相同位清零
    bm.bits[num/8] &^= 1 << (num%8)
}

判斷BitMap中是否存在指定的資料

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

以上就是go資料結構和演演算法BitMap原理及實現範例的詳細內容，更多關於go資料結構演演算法BitMap的資料請關注it145.com其它相關文章！