⭐ 题目日期：

阿里 - 2024/8/21

📝 题解：

Bitmap 和布隆过滤器原理详解

1. Bitmap（位图）

原理：
Bitmap 是一种通过 二进制位（bit） 存储数据存在性（0 或 1）的紧凑数据结构。

• 核心思想：每个位代表一个独立的元素（如 ID、状态），通过位的位置（偏移量）标识元素，通过位的值（0/1）表示是否存在。
• 存储优化：例如，用 1 个字节（8 bits）可以表示 8 个元素的状态，相比传统布尔数组（每个元素占 1 字节）节省 8 倍内存。

示例：
假设用 Bitmap 记录用户 ID 的活跃状态：

• 用户 ID 为 3 → 对应第 3 个 bit 设为 1。
• 用户 ID 为 100 → 对应第 100 个 bit 设为 1。
• 内存占用：若最大 ID 为 10^6，仅需约 125 KB（10^6 / 8 / 1024）。

操作：

• 设置存在：bitmap[offset] = 1
• 检查存在：bitmap[offset] == 1
• 统计总数：计算二进制中 1 的个数（如 popcount 指令）。

优点：

• 极低的内存占用（每个元素仅 1 bit）。
• 高效的范围查询（如统计某区间活跃用户数）。

缺点：

• 元素范围需预先确定，若元素稀疏（如最大 ID 为 10^9，但仅存 1000 个元素）会导致内存浪费。
• 仅支持整数类型（需将非整数映射为唯一整数）。

应用场景：

• 用户签到（每日签到记录）。
• 统计活跃用户（如 DAU）。
• 去重（如海量整数去重）。

---

2. 布隆过滤器（Bloom Filter）

原理：
布隆过滤器是一种 概率型数据结构，用于快速判断元素是否 可能存在 于集合中。

• 核心思想：
  1. 使用 多个哈希函数 将元素映射到 一个位数组 的多个位置。
  2. 插入元素时，将所有映射的位置置为 1。
  3. 查询元素时，若所有映射位置均为 1，则认为元素可能存在；否则一定不存在。

示例：
假设位数组大小为 10，哈希函数为 h1(x) 和 h2(x)：

• 插入 "apple" → h1("apple")=3，h2("apple")=7 → 置位 3 和 7 为 1。
• 查询 "banana" → 若 h1("banana")=3（已为 1），h2("banana")=5（为 0）→ 判定不存在。

误判率（False Positive）：

• 元素不存在时，可能因哈希碰撞被误判为存在。
• 误判率公式：
  ( P \approx \left(1 - e^{-k n / m}\right)^k )
  • ( m ): 位数组大小
  • ( n ): 元素数量
  • ( k ): 哈希函数个数

参数设计：

• 根据预期元素数量 ( n ) 和可接受误判率 ( P ) 计算最优 ( m ) 和 ( k ):
  ( m = -\frac{n \ln P}{(\ln 2)^2} ),
  ( k = \frac{m}{n} \ln 2 ).

优点：

• 空间效率极高，远低于哈希表。
• 查询时间复杂度为 O(k)（k 为哈希函数个数）。

缺点：

• 存在误判，不适用于要求 100% 准确的场景。
• 不支持删除操作（删除可能影响其他元素）。

改进变种：

• Counting Bloom Filter：用计数器代替位，支持删除（但占用更多内存）。
• Cuckoo Filter：结合布谷鸟哈希，支持删除且误判率更低。

应用场景：

• 缓存穿透防护（快速过滤不存在的数据）。
• 爬虫 URL 去重。
• 数据库查询前置过滤（减少磁盘 IO）。

---

对比总结

特性	Bitmap	布隆过滤器
准确性	精确（无误判）	概率性（可能误判）
支持元素类型	整数（需映射）	任意类型（需哈希函数）
内存占用	与最大元素值相关	与元素数量和误判率相关
删除支持	支持（置 0）	不支持（需 Counting 变种）
适用场景	整数范围小、精确判断	大数据量、容忍误判的过滤

---

代码示例（Python 布隆过滤器）

import mmh3
from bitarray import bitarray

class BloomFilter:
    def __init__(self, size, hash_num):
        self.size = size
        self.hash_num = hash_num
        self.bit_array = bitarray(size)
        self.bit_array.setall(0)

    def add(self, item):
        for seed in range(self.hash_num):
            index = mmh3.hash(item, seed) % self.size
            self.bit_array[index] = 1

    def contains(self, item):
        for seed in range(self.hash_num):
            index = mmh3.hash(item, seed) % self.size
            if not self.bit_array[index]:
                return False
        return True

# 使用示例
bf = BloomFilter(1000000, 5)
bf.add("apple")
print(bf.contains("apple"))   # True
print(bf.contains("banana"))  # False（可能误判为 True）

---

选择建议

• 需要精确判断且元素为整数 → Bitmap。
• 大数据量、容忍误判且元素类型多样 → 布隆过滤器。
• 需支持删除 → Counting Bloom Filter 或 Cuckoo Filter。