Bitmap 和 布隆过滤器傻傻分不清？你这不应该啊

Bitmap 和布隆过滤器傻傻分不清？你这不应该啊

线上做用户去重、风控拦截、缓存穿透保护的时候，这俩东西经常一起出现。名字也都带点“位”的味道，所以很多人会混着用。可一到真写代码，问题就出来了：明明要判断“这个用户是不是存在过”，结果你用了 Bitmap；明明要做大规模精确去重，结果你上了布隆过滤器，最后还在那怀疑 Redis 不准。

这俩东西看着像，路子其实不一样。

先说 Bitmap。 它本质上就是一个超紧凑的位数组，核心动作只有一个：用下标映射状态。某个值出现过，就把对应位置置成 1。

比如统计当天活跃用户 id，用户 id 是连续整数，或者至少能映射成一个不太离谱的整数区间，那 Bitmap 就很顺手。

public class SimpleBitmap {

  private final long[] words;

  public SimpleBitmap(int maxValue) {

      this.words = new long[(maxValue >> 6) + 1];

  }

  public void add(int value) {

      words[value >> 6] |= 1L << (value & 63);

  }

  public boolean contains(int value) {

      return (words[value >> 6] & (1L << (value & 63))) != 0;

  }

}

这种写法很直接。 用户 id = 10086，就把第 10086 位设成 1。后面判断在不在，直接读这一位。

它的优点也很明显：判断快，结果准，内存省。 但有个前提，值域得适合映射。

比如你现在存的是用户 id，最大 1000 万，那还能玩。 可你要存手机号13800138000，或者订单号202603091234567890，你总不能真开那么大的位图。很多人就是在这一步把 Bitmap 用废了。

看个很常见的误用：

public void markPhone(String phone) {

  int index = Integer.parseInt(phone);

  bitmap.add(index); // 这行基本已经宣告内存爆炸了

}

这种场景你该先想的不是“怎么压缩位图”，而是：这玩意儿到底适不适合 Bitmap。

再看布隆过滤器。 它不是拿“一个值对应一个位置”，而是拿多个哈希函数，把一个值打到多个位置上。查询时只要这些位置里有一个是 0，那这个值一定没出现过；如果全是 1，只能说大概率出现过。

注意这个“大概率”，就是它和 Bitmap 最关键的区别。

public class SimpleBloomFilter {

  private final BitSet bits;

  private final int size;

  public SimpleBloomFilter(int size) {

      this.size = size;

      this.bits = new BitSet(size);

  }

  public void add(String value) {

      int h1 = hash1(value);

      int h2 = hash2(value);

      int h3 = hash3(value);

      bits.set(Math.abs(h1 % size));

      bits.set(Math.abs(h2 % size));

      bits.set(Math.abs(h3 % size));

  }

  public boolean mightContain(String value) {

      int h1 = hash1(value);

      int h2 = hash2(value);

      int h3 = hash3(value);

      return bits.get(Math.abs(h1 % size))

          && bits.get(Math.abs(h2 % size))

          && bits.get(Math.abs(h3 % size));

  }

  private int hash1(String s) { return s.hashCode(); }

  private int hash2(String s) { return s.hashCode() * 31 + 17; }

  private int hash3(String s) { return s.hashCode() * 131 + 7; }

}

这里就能看出它的定位了：适合做“快速排除”，不适合做“精确确认”。

线上最常见的用法是挡缓存穿透。 请求先查布隆过滤器，如果它说一定不存在，那连数据库都不用打；如果它说可能存在，再去查缓存、查库。

伪代码一般是这样：

public UserInfo queryUser(long userId) {

  String key = "user:" + userId;

  if (!bloomFilter.mightContain(key)) {

      return null;

  }

  UserInfo cache = redis.get(key);

  if (cache != null) {

      return cache;

  }

  UserInfo db = userRepository.findById(userId);

  if (db != null) {

      redis.set(key, db);

  }

  return db;

}

这段逻辑真正值钱的地方，不是“查得快”，而是把那些明显不存在的数据，在入口就拦掉了。

那到底怎么区分？

你可以记两句很土但很实用的话：

Bitmap 解决的是“这个下标有没有被标记过”。布隆过滤器解决的是“这个对象大概率来过没有”。