一、问题背景
在海量数据处理场景中，我们经常需要解决判重问题：
- 爬虫爬取 10 亿网页，如何避免重复爬取？
- 统计网站日活 UV，如何对重复用户去重？
- 缓存系统中，如何快速判断数据是否一定不存在？
用散列表存储 10 亿条 URL（平均 64 字节），需要 100GB+ 内存。有没有更省空间的方案？
二、位图（BitMap）
2.1 核心思想
用一个二进制位表示一个数字是否存在，以数组下标定位数据。
1 千万个整数，范围 1~1 亿：
- 散列表：至少 40MB（每个 int 4 字节）
- 位图：1 亿个 bit ≈ 12MB
2.2 实现原理
借助 int/long 等类型的位运算，用其中某一位表示某个数字：
public class BitMap {
private long[] bits;
private int nbits;
public BitMap(int nbits) {
this.nbits = nbits;
this.bits = new long[nbits / 64 + 1];
}
public void set(int k) {
if (k > nbits) return;
int wordIndex = k / 64;
int bitIndex = k % 64;
bits[wordIndex] |= (1L << bitIndex);
}
public boolean get(int k) {
if (k > nbits) return false;
int wordIndex = k / 64;
int bitIndex = k % 64;
return (bits[wordIndex] & (1L << bitIndex)) != 0;
}
}