Bitmap

作者： /

什么是 Bitmap

Bitmap（位图）用一个 bit 表示一个状态（通常是有/无），本质是一个”超紧凑的布尔数组”。三个核心特点：

  • 空间效率：每个元素只占 1 bit，1 亿个标记只要约 12MB；
  • 操作快：并集/交集等集合操作直接按位运算，O(位数/字长)；
  • 适合密集数据：值域不大但数量多的场景（如用户 ID 标记、状态位）。

基本操作

Set（置 1）、Clear（置 0）、Test（检查）、Count（统计 1 的个数）、Iterate（遍历）、And/Or/Xor/Not（集合运算）。

Go 实现

package bitmap

import "errors"

type Bitmap struct {
    data []uint64
    size uint64
}

func NewBitmap(size uint64) *Bitmap {
    return &Bitmap{data: make([]uint64, (size+63)/64), size: size}
}

func (b *Bitmap) Set(pos uint64) error {
    if pos >= b.size { return errors.New("out of range") }
    b.data[pos/64] |= 1 << (pos % 64)
    return nil
}

func (b *Bitmap) Clear(pos uint64) error {
    if pos >= b.size { return errors.New("out of range") }
    b.data[pos/64] &^= 1 << (pos % 64)
    return nil
}

func (b *Bitmap) Test(pos uint64) (bool, error) {
    if pos >= b.size { return false, errors.New("out of range") }
    return b.data[pos/64]&(1<<(pos%64)) != 0, nil
}

// Count：逐字统计 1 的个数（Brian Kernighan 逐位清零法）
func (b *Bitmap) Count() uint64 {
    var n uint64
    for _, w := range b.data {
        for x := w; x != 0; x &= x - 1 { n++ }
    }
    return n
}

// And / Or / Xor：集合运算（要求 size 相同）
func (b *Bitmap) Or(other *Bitmap) error {
    if b.size != other.size { return errors.New("size mismatch") }
    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] }
    if b.size%64 != 0 {
        last := len(b.data) - 1
        b.data[last] &= ^uint64(0) >> (64 - b.size%64)
    }
}

要点：取反后必须掩掉最后一个 uint64 里超出 size 的位，否则 Count/遍历会统计到不存在的”位”——这是手写 Bitmap 最常见的 bug。

性能优化

  • Count 用查表法（预计算 256 项 popcount 表）代替逐位循环，可快数倍；Go 里直接用 bits.OnesCount64；
  • 连续位的批量设置/清除可以按字操作；
  • 大 Bitmap 可以按字分块并行处理；
  • 稀疏数据用压缩格式（RLE 或 Roaring Bitmap）。

应用场景

  • 去重/存在性判断：海量 ID 快速标记（也是布隆过滤器的基础组件）；
  • 权限系统：一个整数按位表示多组权限；
  • 数据库索引：Bitmap 索引加速多维查询（如 ClickHouse）；
  • 游戏：在线状态、签到记录等海量布尔状态。

进阶：Roaring Bitmap

稀疏 + 密集混合数据下，普通 Bitmap 或数组都有短板。Roaring Bitmap 组合数组 + Bitmap + Run-Length 编码三种容器，按块密度自动切换，是目前工程界的事实标准（数据库、搜索引擎都在用）。Go 实现：github.com/RoaringBitmap/roaring。

滚动至顶部