go数据结构和算法BitMap原理及实现示例

第go数据结构和算法BitMap原理及实现示例目录1.BitMap介绍如何判断数字在bit数组的位置设置数据到bit数组从bit数组中清除数据数字是否在bit数组中2.Go语言位运算左移右移使用^和位移运算来给某一位置03.BitMap的Go语言实现定义创建BitMap结构将数据添加到BitMap从BitMap中删除数据判断BitMap中是否存在指定的数据

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对应的字节数组的位置为：110%8=2，即数字10对应的当前字节的位置为：2

设置数据到bit数组

num/8得到数字在字节数组中的位置=rownum%8得到数字在当前字节中的位置=col将1左移col位，然后和以前的数据做|运算，这样就可以将col位置的bit替换成1了。

从bit数组中清除数据

num/8得到数字在字节数组中的位置=rownum%8得到数字在当前字节中的位置=col将1左移col位，然后对取反，再与当前值做，这样就可以将col位置的bit替换成0了。

数字是否在bit数组中

num/8得到数字在字节数组中的位置=rownum%8得到数字在当前字节中的位置=col将1左移col位，然后和以前的数据做运算，若该字节的值!=0，则说明该位置是1，则数据在bit数组中，否则数据不在bit数组中。

2.Go语言位运算

在Go语言中支持以下几种操作位的方式：

按位与：两者全为1结果为1，否则结果为0|按位或：两者有一个为1结果为1，否则结果为0^按位异或：两者不同结果为1，否则结果为0^按位与非：是与和非操作符的简写形式按位左移：按位右移：

左移

将二进制向左移动，右边空出的位用0填补，高位左移溢出则舍弃该高位。

由于每次移位数值会翻倍，所以通常用代替乘2操作。当然这是建立在移位没有溢出的情况。

例如：13相当于18=8，34相当于316=48

右移

将整数二进制向右移动，左边空出的位用0或者1填补。正数用0填补，负数用1填补。

负数在内存中的二进制最高位为符号位使用1表示，所以为了保证移位之后符号位的正确性，所以需要在高位补1。

相对于左移来说，右移通常用来代替除2操作。

例如：243相当于248=3

使用^和位移运算来给某一位置0

这个操作符通常用于清空对应的标志位，例如a=00111010，如果想清空第二位，则可以这样操作:

a^00000010=00111000

3.BitMap的Go语言实现

接下来我们给出BitMap的Go语言实现，目前代码已经上传到github中，下载地址

定义

首先给出BitMap结构的定义：

typeBitMapstruct{

bits[]byte

vmaxuint

}

创建BitMap结构

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

}

将数据添加到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后，然后和以前的数据做|，这样就替换成1了

bm.bits[num/8]|=1(num%8)

}

从BitMap中删除数据

func(bm*BitMap)UnSet(numuint){

ifnumbm.vmax{

return

//^:将1左移num%8后，然后进行与非运算，将运算符左边数据相异的位保留，相同位清零

bm.bits[num/8]^=1(num%8)

}

判断BitMap中是否存在指定的数据

func(bm*BitMap)Check(numuint)bool{

ifnumbm.vmax{

returnfalse