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结构的定义:
1
2
3
4
|
type BitMap struct { bits [] byte vmax uint } |
创建BitMap结构
1
2
3
4
5
6
7
8
9
10
11
|
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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
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中删除数据
1
2
3
4
5
6
7
|
func (bm *BitMap)UnSet(num uint ) { if num > bm.vmax { return } //&^:将1左移num%8后,然后进行与非运算,将运算符左边数据相异的位保留,相同位清零 bm.bits[num/ 8 ] &^= 1 << (num% 8 ) } |
判断BitMap中是否存在指定的数据
1
2
3
4
5
6
7
|
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的资料请关注服务器之家其它相关文章!
原文链接:https://segmentfault.com/a/1190000041811459