位图（BitMap）基础

raw/articles/2026/05/位图

一句话总结

位图（BitMap）是一种极致节省空间的数据结构，用 1 个比特位（bit）的 0/1 来标记元素是否存在，相比布尔数组节省 7/8 的内存空间，适用于超大规模数据场景。

核心原理

问题背景

在算法题中，常用 boolean[] visited 布尔数组记录元素访问状态：

boolean[] visited = new boolean[nums.length];
visited[10] = true;

空间浪费问题：

• 布尔类型只需 1 bit（0/1）即可表示
• 但大部分编程语言中，一个 boolean 占用 1 字节（8 bits） 内存
• 布尔数组实际浪费了 7/8 的存储空间

位图设计

位图直接用 1 个 bit 表示一种状态：

• 0 表示元素不存在 / 未访问
• 1 表示元素存在 / 已访问

空间对比：

数据结构	存储 1000 个状态所需空间
boolean[1000]	1000 bytes ≈ 0.98 KB
位图（1000 bits）	125 bytes ≈ 0.12 KB

关键要点

1. 极致空间效率：位图将空间压缩到布尔数组的 1/8
2. 适用场景有限：除非数据规模非常大（如布隆过滤器场景），否则没必要使用位图
3. 替代方案：实际开发中，编程语言内置的布尔数组已足够
4. 后续延伸：位图是 布隆过滤器 的基础组件，用于处理超大规模数据

实践建议

提示：在实际开发和求解算法题时，使用编程语言提供的布尔数组就够了。除非需要处理的数据规模非常大，否则没必要为了节省这一点内存空间而引入位图这种结构。

相关概念

• 位图：位图的定义、原理和应用场景
• 布隆过滤器：基于位图的概率型数据结构，用于判断元素是否存在，适用于超大规模数据场景

相关实体

• labuladong：算法学习平台作者