【高阶数据结构】位图（BitMap）

1. 概念

位图：很多地方也叫做Bitmap、BitSet，本质上就是一种 Hash 映射的方式，原先一个整数需要使用 4 个字节存储（在Java中）但是存储的效率非常低下，比如数字 1 的比特位表示为"00000000 00000000 00000000 00000001"，事实上高 31 位完全没有用到，因此我们可以构建出一种结构 "00000001"表示数字1存在，"00000011"表示数字1、2都存在，即 将一个整数映射到一个比特位上，这样一来就大大节省了内存开销！

2. 腾讯面试题

在介绍位图的数据结构实现之前，先来思考一下为什么要引入位图？

题目：给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个数中。【腾讯】

本题有以下经典解题思路：

思路一：使用暴力解法，比如使用 Java 当中 Array 数组结构存储 40 亿个整数，然后遍历查找 target 目标元素，单论时间复杂度为O(N)，但是这里有一个致命的问题：一个整数占据 4 个字节，40 亿个整数（160亿字节）大概占据 16G 内存，这可是一笔不小的开销呀！
思路二：使用二分查找解法，先对数组进行排序，时间复杂度为：O(NlogN）+ O(logN)，的确在时间上可以进行优化，但是仍旧没办法解决内存上的开销！
思路三：使用 HashSet 等树形结构进一步优化时间复杂度，但是仍旧没有办法解决内存上的开销！

因此引出了本篇文章的主角：位图

由于一个整数只使用一个比特位进行存储，因此存储 40 亿个整数只需要 0.5G 的内存空间，这样一来就大大节省了内存开销！

💡 小技巧：10 亿字节大约是 0.9G，可以近似看做 1G

3. 位图 Go 语言实现

3.1 结构定义

// MyBitMap 自定义位图结构体
type MyBitMap struct {elem     []byte // 字节数组usedSize int    // 存储的元素个数
}// initBitMap 初始化函数
func initBitMap(bitMap *MyBitMap) {bitMap.elem = make([]byte, 1, 5)bitMap.usedSize = 0
}

自定义的位图结构如上述代码所示：

elem：我们定义了一个MyBitMap结构体，使用字节数组切片作为底层元素，初始长度为1，容量为5
usedSize：表示当前已经存储的元素个数

3.2 添加元素

// set 添加元素
func (bitMap *MyBitMap) set(num int) {if num < 0 {panic("num必须大于等于0!")}// 1. 获取字节数组对应存储下标var elemIndex = num / 8// 2. 获取所在字节的比特位var bitIndex = num % 8// 3. 使用或运算bitMap.elem[elemIndex] |= 1 << bitIndex// 4. 存储元素个数+1bitMap.usedSize++
}

核心步骤如下：

获取字节数组对应的存储下标，比如第一个字节应当存储【0-7】，第二个字节存储【8-15】，因此使用num / 8就可以找到目标字节
获取目标字节中对应的比特位，使用num % 8可以获取到对应映射比特位
使用或运算强制让目标位变成1（添加元素），图解如下：

❗ 注意：这里不能使用异或运算，因为如果原先已经存储了该元素，即目标比特位为1，此时使用异或就会变成0不符合原意

将已经存储的的元素个数++

3.3 查看元素是否存在

// get 查找某个元素是否存在
func (bitMap *MyBitMap) get(num int) bool {if num < 0 {panic("num必须大于等于0!")}// 1. 获取字节数组对应存储下标var elemIndex = num / 8// 2. 获取所在字节的比特位var bitIndex = num % 8// 3. 使用与运算return !(bitMap.elem[elemIndex]&(1<<bitIndex) == 0)
}

核心步骤如下：

获取字节数组对应的存储下标，比如第一个字节应当存储【0-7】，第二个字节存储【8-15】，因此使用num / 8就可以找到目标字节
获取目标字节中对应的比特位，使用num % 8可以获取到对应映射比特位
使用与运算（判断某一位是否为1）可以用于进行查找元素是否存在，图解如下：

3.4 重置元素

方式一：直接进行操作

// reset 重置某个元素
func (bitMap *MyBitMap) reset(num int) {if num < 0 {panic("num必须大于等于0!")}// 1. 获取字节数组对应存储下标var elemIndex = num / 8// 2. 获取所在字节的比特位var bitIndex = num % 8// 3. 查找元素是否存在if bitMap.get(num) {bitMap.usedSize--}// 4. 使用 ~运算 + &运算bitMap.elem[elemIndex] &= ^(1 << bitIndex)
}

方式二：先判断后操作

func (bitMap *MyBitMap) reset2(num int) {if num < 0 {panic("num必须大于等于0!")}// 1. 获取字节数组对应存储下标var elemIndex = num / 8// 2. 获取所在字节的比特位var bitIndex = num % 8// 3. 查找元素是否存在if bitMap.get(num) {// 使用异或bitMap.elem[elemIndex] ^= 1 << bitIndexbitMap.usedSize--} else {// nothing to do....}
}

核心步骤如下：

获取字节数组对应的存储下标，比如第一个字节应当存储【0-7】，第二个字节存储【8-15】，因此使用num / 8就可以找到目标字节
获取目标字节中对应的比特位，使用num % 8可以获取到对应映射比特位
先使用 ~ 按位取反然后再使用 & 运算可以强制让目标位变为0，图解如下：

❗ 注意：这里不能直接使用异或运算！因为如果原来不存在该元素（目标位为0），直接使用异或运算则会变成1，应该考虑用与运算强制变为0！如果一定想要用异或运算则应参考方式二代码

3.5 获取存储的元素个数

// getUsedSize 获取已经存储元素个数
func (bitMap *MyBitMap) getUsedSize() int {return bitMap.usedSize
}

3.6 完整代码

package mainimport "fmt"// MyBitMap 自定义位图结构体
type MyBitMap struct {elem     []byte // 字节数组usedSize int    // 存储的元素个数
}// initBitMap 初始化函数
func initBitMap(bitMap *MyBitMap) {bitMap.elem = make([]byte, 1, 5)bitMap.usedSize = 0
}// set 添加元素
func (bitMap *MyBitMap) set(num int) {if num < 0 {panic("num必须大于等于0!")}// 1. 获取字节数组对应存储下标var elemIndex = num / 8// 2. 获取所在字节的比特位var bitIndex = num % 8// 3. 使用或运算bitMap.elem[elemIndex] |= 1 << bitIndex// 4. 存储元素个数+1bitMap.usedSize++
}// get 查找某个元素是否存在
func (bitMap *MyBitMap) get(num int) bool {if num < 0 {panic("num必须大于等于0!")}// 1. 获取字节数组对应存储下标var elemIndex = num / 8// 2. 获取所在字节的比特位var bitIndex = num % 8// 3. 使用与运算return !(bitMap.elem[elemIndex]&(1<<bitIndex) == 0)
}// reset 重置某个元素
func (bitMap *MyBitMap) reset(num int) {if num < 0 {panic("num必须大于等于0!")}// 1. 获取字节数组对应存储下标var elemIndex = num / 8// 2. 获取所在字节的比特位var bitIndex = num % 8// 3. 查找元素是否存在if bitMap.get(num) {bitMap.usedSize--}// 4. 使用 ~运算 + &运算bitMap.elem[elemIndex] &= ^(1 << bitIndex)
}// reset2 重置某个元素
func (bitMap *MyBitMap) reset2(num int) {if num < 0 {panic("num必须大于等于0!")}// 1. 获取字节数组对应存储下标var elemIndex = num / 8// 2. 获取所在字节的比特位var bitIndex = num % 8// 3. 查找元素是否存在if bitMap.get(num) {// 使用异或bitMap.elem[elemIndex] ^= 1 << bitIndexbitMap.usedSize--} else {// nothing to do....}
}// getUsedSize 获取已经存储元素个数
func (bitMap *MyBitMap) getUsedSize() int {return bitMap.usedSize
}func main() {// 声明MyBitMapvar myBitMap MyBitMap// 初始化MyBitMapinitBitMap(&myBitMap)myBitMap.set(1)myBitMap.set(3)myBitMap.set(4)fmt.Println(myBitMap.get(7))myBitMap.set(7)fmt.Println(myBitMap.get(7))myBitMap.reset(7)fmt.Println(myBitMap.get(7))myBitMap.reset2(2)fmt.Println(myBitMap.getUsedSize())
}