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，容量为5usedSize：表示当前已经存储的元素个数
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. 存储元素个数+1
bitMap.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< } 核心步骤如下： 获取字节数组对应的存储下标，比如第一个字节应当存储【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 << bitIndex bitMap.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 main import "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. 存储元素个数+1 bitMap.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< } // 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 << bitIndex bitMap.usedSize-- } else { // nothing to do.... } } // getUsedSize 获取已经存储元素个数 func (bitMap *MyBitMap) getUsedSize() int { return bitMap.usedSize } func main() { // 声明MyBitMap var myBitMap MyBitMap // 初始化MyBitMap initBitMap(&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()) } 4. 位图总结 位图具有以下优点： 位图具有哈希映射的性质，因此可以快速在海量数据中快速查找某个元素是否存在位图较传统哈希占用存储空间更小位图天然可以用于排序和去重 位图也具有以下缺点： 仅限于存储整数类型，不能用于字符串等其他类型仅限于数据不重复的场景，如果具有重复可能失效