位图 (Bitmap) 与 BitSet 原理（布隆过滤器前置）

回到总览：00 基础知识（Foundations）
相关模块：位运算基础（Java / Android 复习用）（位运算基础）· 缓存更新策略与常见坑：穿透、击穿、雪崩与一致性

一句话定义

位图（Bitmap / BitSet）= 用连续 bit 标记"整数下标是否在集合里"，1 个元素只花 1 bit，整数域内精确。键不是整数（字符串 / URL / 身份证）就必须先哈希成下标；单哈希一冲突就误判，所以用 k 个哈希的布隆过滤器把误判压到可接受水平。

代码索引

主题	Lab 说明	源码
手写 long[] 位图 + BitSet 集合运算	bitmap-bitset-demo	BitmapBasicsDemo.java
k 哈希布隆（零漏判 + 误判实测）	bitmap-bitset-demo	BloomFilterDemo.java

为什么需要

• 为什么 40 亿个不重复 int 用 HashSet 会 OOM，用位图只要 476MB？
  • 一句话答：HashSet<Integer> 存装箱对象 + 对象头，一个数几十字节；位图 1 bit 一个数，40亿 / 8 ≈ 476MB。
• 为什么 Android 源码到处是位掩码（Intent.FLAG_*、MeasureSpec、权限）？
  • 一句话答：一个 int 就是 32 个开关，O(1) 位运算且省内存，是位图思想的"单字形态"。
• 为什么 Flutter / Dart 里没有内置 BitSet？
  • 一句话答：Dart 核心库没提供；用 Uint64List + 位运算手写（见下文），或社区包 bitset / bloom_filter。

底层机制

1. long[] 位图：定位公式

对应 Lab：bitmap-bitset-demo · BitmapBasicsDemo.java

概念：位图底层是一个 long[]，每个 long 装 64 个 bit。数字 N 的"住址"两步算出——wordIndex = N >> 6（第几个 long）、offset = N & 63（该 long 第几位），按位或置 1：

public class SimpleBitmapDemo {
    static class SimpleBitmap {
        private final long[] words;
        SimpleBitmap(int capacityBits) { words = new long[(capacityBits + 63) >> 6]; }
        void set(int bit)     { words[bit >> 6] |= 1L << (bit & 63); }
        boolean get(int bit)  { return (words[bit >> 6] & (1L << (bit & 63))) != 0; }
    }
    public static void main(String[] args) {
        SimpleBitmap bm = new SimpleBitmap(1000);
        bm.set(69);
        System.out.println("bit 69 -> word " + (69 >> 6) + ", offset " + (69 & 63));
        System.out.println("get(69)=" + bm.get(69) + ", get(70)=" + bm.get(70));
    }
}

图下备注：bitIndex=69 → 69>>6=1（第 1 个 long）、69&63=5（第 5 位）；一次只读写一个 long 的某一位。

• 可能执行顺序：set(69) 置 words[1] 第 5 位 → 两次 get → 打印。
• 可能输出

  bit 69 -> word 1, offset 5
  get(69)=true, get(70)=false

• 预期现象：69 命中、70 未命中。
• 观察重点：每次只读写一个 long 的某一位——这就是"1 bit 一个数、O(1) 定位"的来源。

2. 为什么用 long，而不是 int / double？

• 字可用任意定宽整数（byte / int / long / 128 位）；double 不行——它是 IEEE-754 布局（符号+指数+尾数），不是可逐位寻址的 bit 序列，语义错乱且无收益。
• 总内存 ≈ 容量(bit) / 8 字节，与字宽无关；选 long 只因 64 位 CPU 一条指令处理 64 bit、数组更短。
• 速算：10 亿数 ≈ 125MB；40 亿数 ≈ 476MB；14 亿人 ≈ 175MB。

3. 布隆过滤器：位图 + k 个哈希

对应 Lab：BloomFilterDemo.java

概念：字符串没法当下标，先哈希成整数。单哈希一旦冲突就误判（14 亿要 1% 误判得 ~17.5GB，不划算）；布隆改用 k 个独立哈希，把元素映射到 k 个 bit 全置 1：

图下备注：插入把 k 个位置全置 1；查询任一为 0 必不存在、全为 1 才"可能存在"——零漏判、有误判。

• 插入：k 个位置全置 1；查询：任一为 0 → 必不存在，全为 1 → 可能存在。
• 调参：m = -N·ln(p)/(ln2)²（位数），k = (m/N)·ln2（哈希数）。例：14 亿身份证、误判率 1% → 约 1.68GB / k≈7。
• 标准布隆不可删除 / 枚举 / 计数（变体"计数布隆"可删）。
• 与位图关系：布隆 = 位图（存储层）+ 多哈希（算法层） ；纯位图 + 整数下标 = 精确，+1 哈希 = 易误判，+k 哈希 = 布隆。

4. 量级估算：全中国身份证"是否已保存"

方案	内存	特点
顺序整数位图（需完美映射到 0…14亿）	~175 MB	精确
单哈希位图（目标 1% 误判）	~17.5 GB	冲突即误判，最差
布隆过滤器（1% / 0.1% / 0.01%）	1.68 / 2.5 / 3.4 GB	零漏判
直接存原文（18B × 14亿）	~25 GB	精确但最贵

Android / Flutter / Web / Backend 对照

Android（主线深写）

• java.util.BitSet：RecyclerView 多选态、日历标记、签到去重；and() / or() 做集合交集，cardinality() 统计。Kotlin 直接复用（无独立 API），可用扩展函数封装。
• SparseBooleanArray / SparseIntArray：int → boolean 缓存，替代 HashMap<Integer,Boolean>，省掉装箱与对象头。
• 位掩码：Intent.FLAG_*、Paint.FLAG_*、Gravity、MeasureSpec——一个 int 当 32 个开关（呼应 01 位运算）。
• 布隆：广告曝光去重、推送"已展示"防刷，long[] + 双哈希手写即可（lab 里有）。
• 同名异物：Android 的 Bitmap 常指图片像素（android.graphics.Bitmap），不是位集合，别混淆。

图下备注：BitSet（多选/签到/交集）、int 位掩码（FLAG_*/MeasureSpec）、SparseBooleanArray（int→boolean）、布隆（去重/防刷）；android.graphics.Bitmap 是图片像素，别混。

Flutter（主线深写）

Dart 没有内置 BitSet——这是 Android→Flutter 最典型的迁移点。用 Uint64List 手写（同一套定位公式）：

final m = Uint64List(6);                         // 365 天打卡
void mark(int day) => m[day >> 6] |= 1 << (day & 63);
bool done(int day) => (m[day >> 6] & (1 << (day & 63))) != 0;

或直接用包：bitset、bloom_filter。

Web / Backend（对照浅写）

Redis SETBIT / GETBIT（亿级签到、在线状态）；ClickHouse / Druid 位图索引加速多条件查询。

常见场景

1. 签到 / 去重：BitSet 标记"第 N 天已签"，cardinality() 数连续天数。
2. 集合运算："既买过 A 又点过 B 的用户" = 两张位图 and()。
3. 缓存穿透防护：查库前先过布隆，返回"必不存在"的直接挡掉，只有"可能存在"才查库。

常见误配、事故后果与排障

1. 拿位图装超大整数域（如身份证 10^18）→ 内存直接爆炸；必须先哈希 / 完美映射到小整数域。
2. 单哈希位图：FPR ≈ 1 - e^(-N/m)，14 亿要 1% 需 ~17.5GB；别用单哈希，用布隆。
3. 布隆不调参：m 太小或 k 不当 → 误判率飙升；先按公式算 m、k。
4. 标准布隆"删除"：清位会误伤其它元素 → 需要计数布隆。
5. 概念混淆：把图形学 Bitmap（像素）当位集合用，排障方向会错。

排障路径：先估量级（容量 / 8）→ 选精确（位图 / 哈希集合）还是概率（布隆）→ 用 lab 打点验证误判率。

与相近概念对比

概念	存储	精确性	键类型	删除
Bitmap / BitSet	bit 数组	整数域精确	非负整数	可（清位会误伤他人）
单哈希位图	bit 数组	概率	任意（需哈希）	不可
布隆过滤器	bit 数组 + k 哈希	概率（零漏判）	任意	不可（计数布隆可）
HashSet	哈希表 + 对象	精确	任意	可
图形学 Bitmap	像素矩阵	—	—	—

对应实验

Lab	说明	源码
bitmap-bitset-demo	手写位图 + BitSet 运算 + 布隆误判实测	BitmapBasicsDemo.java · BloomFilterDemo.java

复习检查题

1. 40 亿个不重复 int，用位图要多少内存？

   答：40亿 / 8 ≈ 476MB；HashSet<Integer> 存装箱对象会到几十 GB。

2. 为什么布隆只会误判、不会漏判？

   答：k 个位置任一为 0 就说明从未写入过（零漏判）；全为 1 可能是其它元素"填满"的巧合（误判）。

3. 14 亿身份证、允许 1% 误判，布隆要多大、几个哈希？

   答：m ≈ 1.34e10 bit ≈ 1.68GB，k ≈ 7（m = -N·ln(p)/(ln2)²）。

4. Flutter / Dart 里做位集合怎么办？

   答：Uint64List 手写（bit >> 6、bit & 63），或用 bitset / bloom_filter 包。

速记

• 位图 = 1 bit 一个数，内存 ≈ 容量 / 8 字节；定位公式 bit >> 6、bit & 63。
• 整数域精确；非整数键必须哈希 → 单哈希会误判 → 布隆（k 哈希）零漏判。
• Dart 无内置 BitSet，Uint64List 手写；Android 的 Bitmap 常指图片像素，别混淆。