数据结构与算法 - BitMap

2022-08-24

全文 ≈ 564字 | 预计阅读时长 2分钟

BitMap（位图）是一种以 bit 方式存储数据的数据结构，以此来提高空间利用率。

BitMap，通过字面意思理解利用 bit 映射数据的存储结构。所以它应该有 Key、Value，Key 是 bit、Value 是要存储的具体的值。核心思想是通过 bit 来记录数据是否存储：0 不存在、1 存在。

定义一个长度为 8 的 bit 数组，从 0 ～ 7 分别映射对应的整型数值。

当整数 4 存储时，则改变对应 bit 的状态（值）。

这样做带来的好处，同样一个整数在数组中存储需要 4byte*8bit=32bit 空间，在 BitMap 中只需要 1bit 空间。

定义一个可以存储 0 ～ 32 的 BitMap

1
2
3

bits := make([]byte, (32>>3)+1) // 32 >> 3 等价于 floor(32 / 8)
// fmt.Printf("%08b\n", bits)
// [00000000 00000000 00000000 00000000 00000000]

把 31 存储进 BitMap，利用按位或操作改变 bit 值

1
2
3

bits[31>>3] |= 1 << (31 % 8)
// 拆解逻辑
// bits[3] = 00000000 | 10000000

遇见数据去重，判断 31 是不是已存在

1
2
3

bits[31>>3]&1<<(31%8) == 0
// 拆解逻辑
// 10000000 & 10000000

从 BitMap 删除指定数据

bits[31>>3] &^= 1 << (31 % 8)
// 拆解逻辑
// 10000000 & 10000000 = 10000000
// 10000000 ^ 10000000 = 00000000

完整代码：bitmap

BitMap 通过位操作去实现，所以温习以下操作符：

1
2
3

// 将操作符左右两侧数值的bit进行对应 && 运算
4 & 5 = 4
00000100 & 00000101 = 00000100

1
2
3

// 将操作符左右两侧数值的bit进行对应 || 运算
4 | 5 = 5
00000100 | 00000101 = 00000101

1
2
3

// 将操作符左右两侧数值的bit进行逻辑预算，规则如下：1 ^ 1 = 0、1 ^ 0 = 1、0 ^ 1 = 1、0 ^ 0 = 0
4 ^ 5 = 1
00000100 ^ 00000101 = 00000001

其他语言一般是 ~，Go语言是 ^

1
2
3

// 将操作符右侧数值的bit进行取反，0 -> 1、1 -> 0
^4 = -5
-(00000100 + 00000001) = -0000101 = 10000101

1
2
3

// 将操作符左侧数值的bit按照右侧数值进行左移（溢出位则舍弃）
4 << 5 = 128
[00000]100 << 5 = 100[00000] // 左侧舍弃的位在右侧进行补位