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}