后端、算法和数据库领域中的Bitmap(位图)
后端、算法和数据库领域中的Bitmap(位图)是一种非常精妙的数据结构。 简单来说，Bitmap是利用计算机中最小的单位—Bit（位/比特）—来存放数据结构的一种技术。
1. 核心原理：它是如何工作的？
通常我们存储一个数字，使用int类型需要占用4个字节（32bit）。而在Bitmap中，我们只用1个bit来表示这个数字是否存在。
- 映射规则：我们申请一块连续的内存（bit数组）。数组的下标（Index）代表数据的值（比如用户的ID），而该位上的值（0或1）代表状态（比如“存在/不存在”、“未签到/已签到”）。
- 例子：假如我们要记录ID为1、4、6的用户已签到。
- 第1位为1
- 第4位为1
- 第6位为1
- 其它为默认为0 空间对比：如果我们要存储1亿个用户的签到状态：
- 使用Set/List（int）：1亿 4字节 381 MB
- 使用Bitmap：1亿 bits 12.5 MB
- 结论：空间节省了约30倍。
2. Bitmap主要用来干什么？（应用场景）
Bitmap最擅长处理海量数据的布尔状态（Yes/No）统计和查找 A.用户行为统计（活跃度/签到） 互联网大厂（如使用Redis）最常用的场景。
- 场景：统计App的日活（DAU）、月活（MAU），或者用户连续签到记录。
- 做法：每一天作为一个Bitmap key，用户ID作为offset。
B.快速去重与排序（海量整数）
- 场景：给你40亿个不重复的乱序整数，如何快速判断某个数是否存在？或者对他们进行排序？
- 做法：建立一个能覆盖最大整数范围的Bitmap。遍历数据，将对应位置设为1。
- 查找：直接看该位是0还是1，时间复杂度 。
- 排序：遍历Bitmap，输出所有为1的下标，即为有序序列。
C. 布隆过滤器（Bloom Filter） 这是Bitmap的进阶应用，用于解决缓存穿透的问题。
- 原理：当数据极大（如URL去重、垃圾邮件黑名单）且允许极低误判率时，使用多个Hash函数将数据映射到Bitmap的不同位置。
- 作用：能够极快告诉你：“这个数据一定不存在，或者可能存在”。
D.权限与标签系统
- 场景：Linux文件权限（rwx对应421）或用户标签（如“男”、“90后”、“极客”）。
- 做法：每一位代表一种权限或标签。通过位运算（AND、OR）快速判断用户是否具备某些复杂特征。
3. 优缺点分析
| 特性 | 描述 |
|---|---|
| 优势 | 极致省空间：相比普通存储节省几十倍内存。 极致速度：基于位运算，CPU 处理速度极快，时间复杂度通常为 。 方便的集合运算：求交集、并集、补集（AND, OR, XOR）非常高效。 |
| 劣势 | 数据稀疏问题：如果只需存 ID 为 1 和 ID 为 1亿 的两个用户，Bitmap 仍需申请 1亿个 bit 的空间，中间全是 0，极其浪费。 只能存整数：无法直接存储字符串（需要先 Hash 成整数）。 不可逆：通常只知道“存在”，无法存储具体的复杂信息（如用户名）。 |
4. 进阶：Roaring Bitmap（咆哮位图）
为了解决Bitmap在数据稀疏（Sparse）时的空间浪费问题，业界普遍使用Roaring Bitmap。
- 原理：它将大块的Bitmap切分成小的容器（Container）。
- 如果数据密集，使用普通的Bitmap容器。
- 如果数据稀疏，使用Array容器（只存数值本身）。
- 应用：Elasticsearch、Spark、Hive、Lucene等大数据与搜索引擎底层都在广泛使用Roaring Bitmap来做索引优化。
图形图像领域的Bitmap
Android中的Bitmap
1. 它是做什么的？
在Android中，Bitmap是一张图片在内存中的表现形式。
- 当你把一张
.jpg或.png图片加载到内存中准备显示在屏幕上时，它就会被解码成一个Bitmap对象。 - 本质上是一个像素矩阵。每一个像素点都包含颜色信息（红、绿、蓝、透明度）。 简单理解：
- 文件形式：JPG/PNG（经过压缩，体积小，CPU无法直接绘制）。
- 内存形式：Bitmap（未压缩的像素点集合，体积大，可以直接交个GPU/CPU绘制到屏幕）。
2. 为什么Android开发者都很怕它？（内存杀手）
Bitmap时导致OOM崩溃的头号杀手。
为什么？因为它极其占用内存。
内存计算公式：
举个例子：假设你有一张拍摄的照片，分辨率是 （1080P），格式是标准的 ARGB_8888（每个像素占 4 字节）。
注意：
- 硬盘上这张JPG可能只有200KB，因为JPG是压缩格式。
- 但加载到内存变成Bitmap后，它会瞬间膨胀成8MB。
- 如果在一个列表加载100张这样的图，瞬间就需要800MB内存，App直接就奔溃了。
总结：
- 算法中用空间换时间（且空间也很小），Android中用空间换画质。