自学内容网 自学内容网
自学内容网 > 正文

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

🕗 发布于 2025-01-18 07:50 数据结构  

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. 存储元素个数+1
bitMap.usedSize++
}

核心步骤如下：

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

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

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

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)
}

核心步骤如下：

  1. 获取字节数组对应的存储下标，比如第一个字节应当存储【0-7】，第二个字节存储【8-15】，因此使用num / 8就可以找到目标字节
  2. 获取目标字节中对应的比特位，使用num % 8可以获取到对应映射比特位
  3. 使用与运算（判断某一位是否为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....
}
}

核心步骤如下：

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

位图具有以下优点：

  1. 位图具有哈希映射的性质，因此可以快速在海量数据中快速查找某个元素是否存在
  2. 位图较传统哈希占用存储空间更小
  3. 位图天然可以用于排序和去重

位图也具有以下缺点：

  1. 仅限于存储整数类型，不能用于字符串等其他类型
  2. 仅限于数据不重复的场景，如果具有重复可能失效

原文地址：https://blog.csdn.net/weixin_62533201/article/details/145216138

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

相关文章

自学内容网
Copyright © 2015-2025