关于数据结构和算法:BitMap原理以及Go语言实现

89次阅读

共计 2012 个字符,预计需要花费 6 分钟才能阅读完成。

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
}

正文完
 0