如何在项目中选择Bitmap 和布隆过滤器？

引言

在我们日常业务开发中特别是在开发大数据量业务和高并发项目中。 Bitmap 和布隆过滤器 作为 Redis 的高级扩展数据结构在这种业务场景下使用频率是非常高的。像什么签到、查重过滤等场景都非常适合使用这两种数据结构来实现，但是我们在面试的时候如果回答项目中使用到了这两种数据结构就非常可能会被问到有关这两者的区别和联系，所以今天我们就重新梳理下 Bitmap 和布隆过滤器的底层原理，分析下它们的 优缺点 及适用的 业务场景。

Bitmap

Bitmap，又称位图，是一种简单高效的位数组数据结构，用于表示布尔值集合。它通过以位（bit）为基本单位实现存储，能够以极少的空间快速判断某个元素是否存在，非常适合用于固定范围的数据场景。

为了更直观地理解 Bitmap，我们可以将它想象成一个由 N 个 位（bit） 组成的数组。在这个数组中，每一位对应一个偏移量，通过将某个位的状态设置为 0 或 1 来表示不同的状态或信息。

位状态示例

Bitmap 使用 1 表示该整数存在， 0 表示不存在。假设初始位数组的状态如下：

偏移量	1	2	3	4	5	6	7
位状态	0	0	0	0	0	0	0

假设我们需要记录某个用户一周内（7 天）的签到情况，我们就可以用 Bitmap 来高效实现。每一位对应一周中的一天，状态为 1 表示签到， 0 表示未签到。

我们给每一个用户都设置一个单独的key。比如是 user:sign:xxx 然后我们用Bitmap的偏移量代表一周的每一天，每个偏移量的位状态来代表该用户是否签到。

假如用户在周三（第 3 天）签到，将 user:sign:12345 的第 2 位（索引从 0 开始）设置为 1：

偏移量	1	2	3	4	5	6	7
位状态	0	0	1	0	0	0	0

接下来我们可以通过 GETBIT 命令来查询该用户该周的某一天是否签到。返回状态为 1 表示签到， 0 表示未签到。我们还可以通过 Redis 的 BITCOUNT 命令统计用户一周内签到的总天数。这样相比较传统方式的计算方式 Bitmap 通过更高效的存储和操作方式，显著提升了系统性能和扩展能力，特别适合在 用户签到、数据标记、统计分析 等需要高性能和低存储成本的场景中使用。

操作命令

在 Redis 中，Bitmap 是通过位操作实现的，主要常用的有以下几个核心命令：

1. 设置某个位的值

命令： SETBIT key offset value
- 作用：设置指定偏移位置的位值为 0 或 1。
- 示例：
```
SETBIT user:sign:12345 3 1  # 将第 4 位设置为 1
```
- 结果：偏移位置的位被更新。

2. 获取某个位的值

命令： GETBIT key offset
- 作用：获取指定偏移位置的位值（ 0 或 1）。
- 示例：
```
GETBIT user:sign:12345 3  # 获取第 4 位的值
```
- 结果：返回对应偏移位置的位值。

3. 统计位数组中值为 `1` 的总数

命令： BITCOUNT key [start end]

作用：统计位数组中值为 1 的位数，支持按字节范围统计。
示例：

BITCOUNT user:sign:12345        # 统计所有位中值为 1 的总数
BITCOUNT user:sign:12345 0 0   # 统计第 1 字节（前 8 位）中值为 1 的总数

结果：返回值为 1 的位的总数。

4. 按位操作（支持多个键）

命令： BITOP operation destkey key [key ...]
- 作用：对一个或多个键的位数组进行按位运算，并将结果存储到目标键中。
- 支持的操作：
  - AND：按位与
  - OR：按位或
  - XOR：按位异或
  - NOT：按位取反（仅支持单个键）
- 示例：
```
BITOP AND result user:sign:12345 user:sign:67890  # 计算两用户签到的交集
BITOP OR result user:sign:12345 user:sign:67890   # 计算两用户签到的并集
```
- 结果：目标键存储按位运算的结果。

操作命令总结

命令	功能	示例
`SETBIT`	设置位值	`SETBIT user:sign:12345 3 1`
`GETBIT`	获取位值	`GETBIT user:sign:12345 3`
`BITCOUNT`	统计值为 1 的位数	`BITCOUNT user:sign:12345`
`BITOP`	按位运算（AND/OR/XOR）	`BITOP AND result user:sign:12345 ...`

Bitmap 的优缺点

我们再简单总结下使用Bitmap的优缺点

优点

存储高效
- 每个状态仅占用 1 位（bit），相比传统的布尔数组或其他结构（如 HashSet），节省了大量内存。
- 适合处理大规模、稠密数据的场景，例如百万用户的签到记录。
操作高效
- 插入、查询、删除等操作通过简单的位操作即可完成，时间复杂度为 O(1)，在高并发场景下表现尤为突出。
支持批量操作
- 通过按位操作（如 BITOP），可以快速完成集合运算，如交集（AND）、并集（OR）等。
灵活扩展
- 位数组长度可以根据需求动态扩展，适合各种固定范围的标记或记录需求，例如按周、按月、按年记录。
适合多场景应用
- 常见于用户签到、数据去重、布尔标记、统计分析等场景，特别适合固定范围的大数据集合。

缺点

不适合稀疏数据
- 当数据范围较大但实际数据稀疏时，会导致大量位被浪费。例如，需要存储 {1, 1000000} 的集合，Bitmap 会分配 100 万个位，仅使用两个位。
仅支持整数键
- Bitmap 的索引必须是整数，对于字符串等非整数数据，需要通过哈希函数映射，可能会引入哈希冲突。
位操作复杂性
- 位数组的操作虽然高效，但对开发者的位运算逻辑要求较高，特别是在多位范围查询时，代码可读性和维护性可能会降低。
缺乏容错性
- 位数组一旦发生误修改，难以恢复具体的数据内容。
功能单一
- 主要用于布尔状态标记，无法直接存储其他复杂类型数据。

布隆过滤器

前面我们提到， Bitmap 的索引必须是整数。如果需要判断字符串等非整数数据（如用户名是否被占用，或某个 IP 是否在黑名单中），需要先通过哈希函数将字符串映射为整数。

然而，这种方法存在一个不可避免的问题： 哈希冲突。不同的字符串可能会得出相同的哈希值，从而导致数据碰撞。

但是我们在日常大数据量的业务中可能会遇到以下几个问题：

如何判断某个用户名是否已被占用？

用户名是字符串类型，直接使用 Bitmap 存储时，哈希冲突会导致误判或遗漏。

如何高效判断某个 IP 是否在黑名单中？

对于大规模 IP 列表，稀疏性和哈希冲突的问题都会影响 Bitmap 的准确性。

为了解决这些问题，我们需要一种既能高效处理字符串等非整数数据，又能在一定程度上规避哈希冲突的数据结构。这时， 布隆过滤器（Bloom Filter） 就派上了用场。

布隆过滤器 针对哈希冲突问题做了进一步优化，采用了 多个哈希函数 和 位数组 的设计，允许一定的误判率，但保证不会漏判，并且可以通过参数调整误判率大小，使其可控。

举例：用户名去重

假设我们需要一个高效的系统，判断用户名是否已经被使用，布隆过滤器可以这样工作：

用户名添加到集合中
- 当一个用户名（如 "user123"）需要添加到集合时，布隆过滤器会通过多个哈希函数将它映射到位数组的多个位置，并将这些位置的值设置为 1。
- 例如，哈希函数将 "user123" 映射到位数组的第 5 位、第 11 位和第 20 位：
```
 位数组：000001000001000000001000000000
```
检查用户名是否已存在
- 当需要判断 "user123" 是否已经存在时，布隆过滤器会再次使用相同的多个哈希函数计算位置，并检查这些位置是否都为 1。
- 如果这些位置的值全为 1，则可能存在；如果有任意一位是 0，则一定不存在。
误判情况
- 如果多个不同的用户名通过哈希函数碰巧映射到了相同的位置，布隆过滤器可能会误判某个用户名已存在（尽管实际上并未添加）。
- 这种误判概率可通过位数组大小和哈希函数数量调整，确保误判率在可接受范围内。

简单理解

布隆过滤器通过 牺牲部分精确性（可能误判） ，换来了更高的空间效率和查询速度，非常适合用于 大规模数据去重 或 快速存在性判断 的场景。

常用操作命令

1. 初始化布隆过滤器

命令： BF.RESERVE key error_rate capacity
- 功能：创建一个布隆过滤器，设置误判率和预期元素数量。
- 参数说明：
  - key：布隆过滤器的名称。
  - error_rate：允许的误判率（如 0.01 表示 1%）。
  - capacity：预期存储的最大元素数量。
- 示例：
```
BF.RESERVE user_filter 0.01 10000
```
初始化一个名为 user_filter 的布隆过滤器，误判率为 1%，最大存储 10000 个元素。

2. 添加元素

命令： BF.ADD key item
- 功能：将一个元素添加到布隆过滤器中。
- 示例：
```
BF.ADD user_filter "user123"
```
将用户名 "user123" 添加到布隆过滤器中。
命令： BF.MADD key item1 item2 ...
- 功能：一次性添加多个元素到布隆过滤器中。
- 示例：
```
BF.MADD user_filter "user123" "user456" "user789"
```
批量添加 "user123"、 "user456" 和 "user789" 到布隆过滤器中。

3. 查询元素是否存在

命令： BF.EXISTS key item
- 功能：检查一个元素是否可能存在于布隆过滤器中。
- 示例：
```
BF.EXISTS user_filter "user123"
```
如果返回 1，表示 "user123" 可能存在；返回 0，表示 "user123" 一定不存在。
命令： BF.MEXISTS key item1 item2 ...
- 功能：一次性检查多个元素是否存在。
- 示例：
```
BF.MEXISTS user_filter "user123" "user456" "user000"
```
返回结果可能为 [1, 1, 0]，分别表示 "user123" 和 "user456" 可能存在， "user000" 一定不存在。

4. 统计布隆过滤器信息

命令： BF.INFO key
- 功能：查看布隆过滤器的配置信息，包括误判率、当前插入的元素数量等。
- 示例：
```
BF.INFO user_filter
```
返回信息示例：
```
Capacity: 10000
Size: 81920
Number of filters: 1
Number of items inserted: 5000
Expansion rate: 2
```

总结表格

命令	功能	示例
`BF.RESERVE`	创建布隆过滤器，设置误判率和容量	`BF.RESERVE user_filter 0.01 10000`
`BF.ADD`	添加一个元素	`BF.ADD user_filter "user123"`
`BF.MADD`	批量添加多个元素	`BF.MADD user_filter "user123" "user456"`
`BF.EXISTS`	检查元素是否可能存在	`BF.EXISTS user_filter "user123"`
`BF.MEXISTS`	批量检查多个元素是否可能存在	`BF.MEXISTS user_filter "user123" "user456"`
`BF.INFO`	查看布隆过滤器的配置信息	`BF.INFO user_filter`

布隆过滤器的优缺点

同样我们也简单总结一下布隆过滤器的优缺点：

优点

高效的空间利用率
- 布隆过滤器使用位数组表示集合状态，比传统的数据结构（如哈希表或数组）占用更少的存储空间，特别适合处理大规模数据。
查询速度快
- 插入和查询操作通过哈希函数和位数组实现，时间复杂度为 O(k)，其中 k 是哈希函数的数量，效率极高。
误判率可控
- 通过调整位数组的大小和哈希函数的数量，可以控制误判率在可接受范围内。例如，适当增大位数组或减少哈希函数数量，可降低误判概率。
灵活适用于稀疏数据
- 对于大范围但稀疏的数据集合（如黑名单 IP、海量用户名等），布隆过滤器在存储效率和查询性能上有显著优势。
无额外存储需求
- 不需要存储完整的元素数据，仅记录哈希结果对应的位置状态，适用于无法存储完整数据的场景（如隐私敏感数据）。

缺点

存在误判
- 布隆过滤器可能会误判某个不存在的元素为存在（假阳性）。
- 对于需要完全精确判断的场景（如金融数据处理），可能不适用。
不支持删除操作
- 布隆过滤器无法直接删除某个特定元素，因为多个元素可能共享同一个位，清除某个位会影响其他元素。
哈希函数的设计复杂性
- 需要选取多个高质量的哈希函数。如果哈希函数设计不合理，会导致哈希冲突增加，从而提高误判率。
误判率随使用增长
- 随着插入的元素增多，位数组被设置为 1 的比例上升，误判率也会随之增大。
- 需要在初始设计时合理预估元素数量，并分配足够大的位数组。
查询限制
- 布隆过滤器只能用于判断元素“可能存在”或“肯定不存在”，无法查询具体的数据内容。

大致总结

布隆过滤器以其高效的空间利用和快速的查询性能，在 大规模数据去重、 黑名单过滤、 缓存穿透防护 等场景中表现优异。虽然存在误判和删除操作的局限，但其优点在许多应用场景中足以弥补这些缺点。

布隆过滤器误判的影响与适用场景

布隆过滤器的误判特点

误判定义：
- 布隆过滤器可能将某些实际上不存在的元素误判为“可能存在”（假阳性）。
- 但它绝不会将存在的元素判断为不存在（无假阴性）。
误判原因：
- 多个不同的元素可能通过哈希函数映射到同一组位，导致布隆过滤器无法区分这些元素。
误判率可控：
- 误判率由以下因素决定：
  - 位数组的大小（越大误判率越低）。
  - 哈希函数的数量（适量的哈希函数可降低误判率，但过多会增加计算开销）。
- 通过合理设计参数（如 RedisBloom 的 BF.RESERVE 命令），可以将误判率控制在业务可接受的范围内。

场景选择：允许误判的应用场景

由于布隆过滤器的误判特性，只有在 允许一定程度的不准确 的场景下，才适合使用。以下是我们日常业务中比较常见的适用场景：

缓存穿透防护
- 误判可接受：误判时会多查询缓存或数据库，但不会导致数据丢失或重大错误。
- 适用性：误判只增加少量额外的查询成本，对性能影响有限。
黑名单过滤
- 误判可接受：误将非黑名单用户误判为黑名单用户可能导致访问被拒，但一般对业务影响不大。
- 适用性：适用于防止垃圾请求或恶意攻击的场景。
去重检查
- 误判可接受：误判为已存在的数据会被略过，但不会影响数据完整性。
- 适用性：如爬虫系统的 URL 去重，重复爬取少量网页对整体效率影响较小。
推荐系统
- 误判可接受：误判为已浏览的内容会被跳过推荐，但不会影响用户体验。
- 适用性：适合过滤已交互内容的场景。
分布式系统同步
- 误判可接受：误判为已存在的数据可能会多次同步，但不会导致数据丢失。
- 适用性：适合在节点间快速判断需要同步的数据时使用。

场景选择：不允许误判的应用场景

在以下场景中，由于误判可能导致严重后果，不适合使用布隆过滤器：

金融交易系统
- 误判问题：误将非法交易用户判断为合法用户可能造成严重安全隐患。
- 替代方案：使用精确的哈希表或其他数据结构。
关键性权限验证
- 误判问题：误将非授权用户判断为已授权用户可能导致安全漏洞。
- 替代方案：采用更严格的验证机制。
数据准确性要求极高的场景
- 误判问题：如医疗数据处理、科研数据分析等，对误判完全无法容忍。
- 替代方案：使用传统的准确数据结构（如哈希表、数据库等）。

总结

布隆过滤器的使用场景必须满足以下条件：

允许少量误判：误判不会造成严重后果，只影响性能或用户体验的场景。
高效性优先：需要在大规模数据处理时节省空间和时间的场景。

通过合理设计和调整参数，布隆过滤器能在许多业务中提供高效、低成本的解决方案，但在对准确性要求极高的场景中，应慎重选择。

Bitmap 和布隆过滤器的区别与联系

上面我们大概说了Bitmap 和布隆过滤器的区别和分布的适用场景。接下来我们也是最终总结一下两者的去呗和联系。

一、联系

基础数据结构
- 布隆过滤器是基于 Bitmap 扩展的：布隆过滤器的底层使用了位数组（Bitmap）来存储数据状态。
- 它们都通过位操作实现存储和查询，具有高效的空间利用率。
用于存在性判断
- 二者都可以用来快速判断某个元素是否存在，且查询效率高，适合处理大规模数据。
空间高效
- 二者都利用位数组来节省存储空间，相比传统数据结构（如哈希表），在处理海量数据时优势明显。

二、区别

特性	Bitmap	布隆过滤器
存储方式	每个元素对应一个固定的位，直接通过索引操作。	使用多个哈希函数将一个元素映射到位数组中的多个位置。
误判情况	完全精确，无误判或漏判。	存在误判（假阳性），但保证不会漏判（假阴性）。
删除操作	支持精准删除，通过将对应的位设置为 `0` 即可。	不支持删除操作，因多个元素共享位，无法准确清除单个元素。
适用数据类型	索引必须是整数。	支持任意数据类型（通过哈希函数映射）。
空间利用率	对于稠密数据高效，但处理稀疏数据时容易造成空间浪费。	对稀疏数据更高效，适合存储大量稀疏集合的存在性判断。
复杂性	实现简单，操作直接（如插入、查询、删除）。	需要设计多个哈希函数，且需平衡误判率与空间效率的关系。
适用场景	用户签到、统计分析、固定范围布尔标记。	缓存穿透防护、黑名单过滤、大规模数据去重。

三、总结

Bitmap 的核心优势 在于它的简单性和精确性，适合小规模、稠密数据的布尔值标记和集合操作。
布隆过滤器的核心优势 在于它的灵活性和空间效率，适合大规模、稀疏数据的存在性判断，尽管存在一定的误判。
选择依据：
- 如果需要绝对的精确性，且数据范围固定，可以使用 Bitmap。
- 如果允许一定的误判，并需要处理大规模数据时，布隆过滤器是更好的选择。

原文阅读