Bitmap（位图）：用 1 个 bit 表示元素状态

2026-07-15

[ Computer ]

Bitmap（位图、位集合）是一种用二进制位（bit）来表示状态的数据结构。

它的核心思想非常简单：

一个 bit 表示一个元素是否存在。

0 → 不存在

1 → 存在

因为 1 bit 只占 1/8 字节，所以 Bitmap 的空间利用率极高。

一、先理解为什么会有 Bitmap

假设有这样一个需求：

判断一个用户 ID 是否存在。

用户 ID 范围：

0 ~ 99999999

（1亿个用户）

最直接的方法：

map[int]bool

例如：

m[123] = true
m[456] = true
m[789] = true

查询：

if m[123] {
    ...
}

但问题来了：

Go 的 map 很耗内存。

一个 key：

int = 8 Byte

再加上：

value
hash
bucket
overflow bucket

实际可能十几到几十字节。

如果存 1 亿个数字：

1亿 × 20B
≈ 2GB

甚至更多。

Bitmap 的思路：

数字 123 是否存在？

直接用第123个bit表示

例如：

index

0 1 2 3 4 5 6 7

0 0 1 0 1 1 0 0

表示：

2存在
4存在
5存在

二、Bitmap 长什么样

假设：

数字范围：

0~15

需要：

16个bit

存储：

00000000 00000000

两个字节即可。

插入：

加入数字3

变成：

00001000 00000000

再加入：

变成：

10001000 00000000

再加入：

变成：

10001000 00010000

最终：

bit位置:

15........8
7.........0

00010000 10001000

表示：

3
7
12

存在。

三、Bitmap 如何存储

CPU 最喜欢处理：

8位
16位
32位
64位

所以 Bitmap 一般用：

[]uint64

存储。

例如：

var bitmap []uint64

每个 uint64：

64 bit

表示：

64个数字

比如：

数字 130

怎么算位置？

第一步：找到在哪个 uint64

130 / 64

结果：

说明：

bitmap[2]

里面。

第二步：找到第几位

130 % 64

结果：

说明：

bitmap[2] 的第2位

所以：

word = n / 64
bit  = n % 64

四、Bitmap 的三大操作

插入

设置为 1

bitmap[word] |= 1 << bit

例如：

bitmap[2] |= 1 << 2

图示：

原来：

00000000

1<<2

00000100

OR之后：

00000100

删除

设置为 0

bitmap[word] &= ^(1 << bit)

例如：

00010100

删除：

bit2

mask：

11111011

AND：

00010000

查询

bitmap[word]&(1<<bit) != 0

例如：

00010100

检查bit2

mask：

00000100

结果：

00000100

非0

说明存在。

五、Bitmap 为什么省内存

这是 Bitmap 最重要的价值。

假设：

记录1亿个数字

范围：

0~99999999

需要：

100000000 bit

换算：

100000000 / 8
=
12.5 MB

仅：

12.5MB

而 map：

可能需要几个GB

对比：

结构	空间
Bitmap	12.5MB
HashMap	数GB

差距：

几十倍~上百倍

六、Bitmap 的时间复杂度

查询：

bitmap[word]&(1<<bit)

本质：

数组访问
+
位运算

复杂度：

O(1)

插入：

O(1)

删除：

O(1)

所以：

操作	复杂度
查询	O(1)
插入	O(1)
删除	O(1)

七、Bitmap 经典应用场景

场景1：用户签到

假设：

一个月31天

用户签到记录：

111011001110...

第1位：

表示：

1号签到了

第2位：

表示：

2号签到了

第3位：

表示：

没签到

很多大厂：

Redis Bitmap

就是这么做的。

场景2：布隆过滤器

BloomFilter 底层：

Bitmap
+
多个Hash函数

流程：

key
 ↓
hash1
hash2
hash3

对应bit置1

查询：

有一个bit=0

一定不存在

这是：

Redis
Elasticsearch
HBase

常见技术。

场景3：海量去重

例如：

10亿个手机号

判断是否出现过。

手机号：

138xxxxxxx

映射成数字。

Bitmap：

出现过 -> 1
没出现 -> 0

比 HashSet 省大量内存。

场景4：统计活跃用户

例如：

今天登录用户：

1
5
100
9999

对应位：

置为 1。

统计：

有多少个1

即可得到：

DAU（日活）

八、Bitmap 最大缺点

Bitmap 不是万能的。

假设：

只有两个数字。

Bitmap 需要：

0~1000000000

全部开出来。

空间：

1000000001 bit
≈125MB

实际上只存了：

2个数字

非常浪费。

所以 Bitmap 适合：

✅ 数据稠密

1
2
3
4
5
...

不适合：

❌ 数据稀疏

1
1000000000

九、Bitmap 与 HashMap 的本质区别

对比项	Bitmap	HashMap
存储内容	状态位	Key-Value
空间占用	极低	较高
查询	O(1)	O(1)
删除	O(1)	O(1)
支持任意Key	否	是
适合稠密数据	✓	一般
适合稀疏数据	✗	✓

十、一句话理解 Bitmap

可以把 Bitmap 想象成：

一排开关

位置: 0 1 2 3 4 5 6 7

状态: 0 1 0 1 1 0 0 1

其中：

第 i 个开关
=
数字 i 是否存在

Bitmap 的本质就是：

用 1 个 bit 表示一个元素的状态，从而把海量数据的存在性判断压缩到极小的内存中。

因此它特别适合：

用户签到
在线状态
海量去重
Bloom Filter
DAU统计
Redis Bitmap
搜索引擎索引压缩

这些场景背后的共同特点是：

只关心“有没有”，不关心“具体存了什么”。