bitmap-bitset-demo

验证目标：手写 long[] 位图的定位公式、java.util.BitSet 集合运算、k 哈希布隆过滤器的"零漏判 + 误判率实测"。

关键实现速览

• BitmapBasicsDemo：SimpleBitmap 用 bit >> 6（第几个 long）与 bit & 63（第几位）定位，1 个元素 1 bit；再演示 BitSet.and() 交集与 cardinality() 计数。
• BloomFilterDemo：由 hashCode 双哈希派生 k 个位置（k≈7），插入时全置 1；查询时任一位置为 0 即"必不存在"。实测 1 万条录入 + 10 万条随机查询的误判率 ≈ 理论 1%。

运行

cd labs/foundations/bitmap-bitset-demo
javac -d out src/*.java
java -cp out BitmapBasicsDemo
java -cp out BloomFilterDemo

可能输出（节选）

get(69)=true, get(70)=false
a ∩ b = {3}
已录入 1 万条，漏判数 = 0（应为 0，零漏判）
未录入随机 10 万条误判 98X 条（0.9X%），理论 ≈ 1%

观察重点

• 手写位图每次只读写一个 long 的某一位 → O(1)、1 bit / 元素。
• 布隆漏判恒为 0；误判率由 m、k 决定（m = -N·ln(p)/(ln2)²）。

对应知识库文档

• 理论主文档：位图 (Bitmap) 与 BitSet 原理（布隆过滤器前置）