第go數(shù)據(jù)結(jié)構(gòu)和算法BitMap原理及實(shí)現(xiàn)示例目錄1.BitMap介紹如何判斷數(shù)字在bit數(shù)組的位置設(shè)置數(shù)據(jù)到bit數(shù)組從bit數(shù)組中清除數(shù)據(jù)數(shù)字是否在bit數(shù)組中2.Go語(yǔ)言位運(yùn)算左移右移使用^和位移運(yùn)算來(lái)給某一位置03.BitMap的Go語(yǔ)言實(shí)現(xiàn)定義創(chuàng)建BitMap結(jié)構(gòu)將數(shù)據(jù)添加到BitMap從BitMap中刪除數(shù)據(jù)判斷BitMap中是否存在指定的數(shù)據(jù)

1.BitMap介紹

BitMap可以理解為通過(guò)一個(gè)bit數(shù)組來(lái)存儲(chǔ)特定數(shù)據(jù)的一種數(shù)據(jù)結(jié)構(gòu)。BitMap常用于對(duì)大量整形數(shù)據(jù)做去重和查詢。

在這類查找中，我們可以通過(guò)map數(shù)據(jù)結(jié)構(gòu)進(jìn)行查找。但如果數(shù)據(jù)量比較大map數(shù)據(jù)結(jié)構(gòu)將會(huì)大量占用內(nèi)存。

BitMap用一個(gè)比特位來(lái)映射某個(gè)元素的狀態(tài)，所以這種數(shù)據(jù)結(jié)構(gòu)是非常節(jié)省存儲(chǔ)空間的。

BitMap用途

BitMap用于數(shù)據(jù)去重

BitMap可用于數(shù)據(jù)的快速查找，判重。BitMap用于快速排序

BitMap由于其本身的有序性和唯一性，可以實(shí)現(xiàn)快速排序：將其加入bitmap中，然后再遍歷獲取出來(lái)，從而得到排序的結(jié)果。

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

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

數(shù)字/8=數(shù)字在字節(jié)數(shù)組中的位置。數(shù)字%8=數(shù)字在當(dāng)前字節(jié)中的位置。

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

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

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

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

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

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

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

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

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

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

左移

將二進(jìn)制向左移動(dòng)，右邊空出的位用0填補(bǔ)，高位左移溢出則舍棄該高位。

由于每次移位數(shù)值會(huì)翻倍，所以通常用代替乘2操作。當(dāng)然這是建立在移位沒(méi)有溢出的情況。

例如：13相當(dāng)于18=8，34相當(dāng)于316=48

右移

將整數(shù)二進(jìn)制向右移動(dòng)，左邊空出的位用0或者1填補(bǔ)。正數(shù)用0填補(bǔ)，負(fù)數(shù)用1填補(bǔ)。

負(fù)數(shù)在內(nèi)存中的二進(jìn)制最高位為符號(hào)位使用1表示，所以為了保證移位之后符號(hào)位的正確性，所以需要在高位補(bǔ)1。

相對(duì)于左移來(lái)說(shuō)，右移通常用來(lái)代替除2操作。

例如：243相當(dāng)于248=3

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

這個(gè)操作符通常用于清空對(duì)應(yīng)的標(biāo)志位，例如a=00111010，如果想清空第二位，則可以這樣操作:

a^00000010=00111000

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

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

定義

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

typeBitMapstruct{

bits[]byte

vmaxuint

}

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

funcNewBitMap(max_val...uint)*BitMap{

varmaxuint=8192

iflen(max_val)0max_val[0]0{

max=max_val[0]

bm:=BitMap{}

bm.vmax=max

sz:=(max+7)/8

bm.bits=make([]byte,sz,sz)

returnbm

}

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

func(bm*BitMap)Set(numuint){

ifnumbm.vmax{

bm.vmax+=1024

ifbm.vmaxnum{

bm.vmax=num

dd:=int(num+7)/8-len(bm.bits)

ifdd0{

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(numuint){

ifnumbm.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(numuint)bool{

ifnumbm.vmax{

returnfalse