什么是 Bitmap
Bitmap（位图）是一种使用位数组来表示数据的数据结构，每个位(bit)可以表示某种状态（通常是存在或不存在）。Bitmap 主要用于高效地存储和操作大量布尔值或整数集合。
Bitmap 的主要特点
- 空间效率：每个元素只占用一个 bit，比传统数组或哈希表更节省空间
- 快速操作：位运算使得集合操作（如并集、交集）非常高效
- 适合密集数据：当数据范围不大但数量很多时特别高效
Bitmap 的基本操作
- 设置位（Set）：将某一位设为 1
- 清除位（Clear）：将某一位设为 0
- 测试位（Test）：检查某一位是否为 1
- 计数（Count）：统计所有设置为 1 的位数
- 遍历（Iterate）：遍历所有设置为 1 的位
Go 语言实现 Bitmap
基础实现
package bitmap
import (
"errors"
)
// Bitmap 结构体
type Bitmap struct {
data []uint64
size uint64
}
// NewBitmap 创建一个新的 Bitmap
func NewBitmap(size uint64) *Bitmap {
// 计算需要多少个 uint64 来存储 size 个 bit
length := (size + 63) / 64
return &Bitmap{
data: make([]uint64, length),
size: size,
}
}
// Set 将指定位设置为 1
func (b *Bitmap) Set(pos uint64) error {
if pos >= b.size {
return errors.New("position out of range")
}
index := pos / 64
offset := pos % 64
b.data[index] |= 1 << offset
return nil
}
// Clear 将指定位设置为 0
func (b *Bitmap) Clear(pos uint64) error {
if pos >= b.size {
return errors.New("position out of range")
}
index := pos / 64
offset := pos % 64
b.data[index] &^= 1 << offset
return nil
}
// Test 检查指定位是否为 1
func (b *Bitmap) Test(pos uint64) (bool, error) {
if pos >= b.size {
return false, errors.New("position out of range")
}
index := pos / 64
offset := pos % 64
return (b.data[index] & (1 << offset)) != 0, nil
}
// Count 统计所有设置为 1 的位数
func (b *Bitmap) Count() uint64 {
var count uint64
for _, num := range b.data {
// 使用 Brian Kernighan 算法计算一个数中 1 的位数
for num != 0 {
num &= num - 1
count++
}
}
return count
}
// Size 返回 Bitmap 的总大小（位数）
func (b *Bitmap) Size() uint64 {
return b.size
}
// Reset 将所有位重置为 0
func (b *Bitmap) Reset() {
for i := range b.data {
b.data[i] = 0
}
}
// And 与另一个 Bitmap 进行按位与操作
func (b *Bitmap) And(other *Bitmap) error {
if b.size != other.size {
return errors.New("bitmaps have different sizes")
}
for i := range b.data {
b.data[i] &= other.data[i]
}
return nil
}
// Or 与另一个 Bitmap 进行按位或操作
func (b *Bitmap) Or(other *Bitmap) error {
if b.size != other.size {
return errors.New("bitmaps have different sizes")
}
for i := range b.data {
b.data[i] |= other.data[i]
}
return nil
}
// Xor 与另一个 Bitmap 进行按位异或操作
func (b *Bitmap) Xor(other *Bitmap) error {
if b.size != other.size {
return errors.New("bitmaps have different sizes")
}
for i := range b.data {
b.data[i] ^= other.data[i]
}
return nil
}
// Not 对所有位进行取反操作
func (b *Bitmap) Not() {
for i := range b.data {
b.data[i] = ^b.data[i]
}
// 处理最后一个 uint64 可能未使用的位
if b.size%64 != 0 {
unusedBits := 64 - b.size%64
lastIndex := len(b.data) - 1
b.data[lastIndex] &= ^uint64(0) >> unusedBits
}
}
// ToSlice 将所有设置为 1 的位转换为切片
func (b *Bitmap) ToSlice() []uint64 {
var result []uint64
for i := uint64(0); i < b.size; i++ {
if val, _ := b.Test(i); val {
result = append(result, i)
}
}
return result
}
使用示例
package main
import (
"fmt"
"bitmap" // 假设上面的代码保存在 bitmap 包中
)
func main() {
// 创建一个能存储 1000 个位的 Bitmap
bm := bitmap.NewBitmap(1000)
// 设置一些位
bm.Set(1)
bm.Set(2)
bm.Set(3)
bm.Set(100)
bm.Set(999)
// 测试位
fmt.Println(bm.Test(1)) // true
fmt.Println(bm.Test(4)) // false
fmt.Println(bm.Test(999)) // true
// 统计
fmt.Println("Count:", bm.Count()) // 5
// 转换为切片
fmt.Println("Set bits:", bm.ToSlice()) // [1 2 3 100 999]
// 清除位
bm.Clear(2)
fmt.Println(bm.Test(2)) // false
// 创建另一个 Bitmap 并进行位运算
bm2 := bitmap.NewBitmap(1000)
bm2.Set(2)
bm2.Set(3)
bm2.Set(4)
bm.Or(bm2)
fmt.Println("After OR:", bm.ToSlice()) // [1 2 3 4 100 999]
bm.And(bm2)
fmt.Println("After AND:", bm.ToSlice()) // [2 3 4]
// 取反
bm.Not()
fmt.Println("After NOT:", bm.ToSlice()) // [0 1 5 6 ... 999] (除了 2,3,4 的所有位)
}
性能优化考虑
- 批量操作：对于连续位的设置/清除，可以实现批量操作来提高性能
- 并行处理：对于大型 Bitmap，可以使用 goroutine 并行处理不同的 uint64 块
- 压缩存储：对于稀疏 Bitmap，可以考虑使用压缩存储格式如 RLE (Run-Length Encoding)
应用场景
- 大数据去重：快速判断元素是否存在
- 布隆过滤器：Bitmap 是布隆过滤器的基础组件
- 权限系统：用位表示不同权限
- 数据库索引：某些数据库使用 Bitmap 索引加速查询
- 图像处理：二值图像可以用 Bitmap 表示
扩展：Roaring Bitmap
对于更高级的 Bitmap 实现，可以考虑 Roaring Bitmap，它结合了数组、Bitmap 和 Run-Length Encoding，适合处理稀疏和密集数据混合的场景。
