你难道分不清Bitmap和布隆过滤器，这不是常识吗？

大家好，我是小富～ 有个兄弟私下跟我说，他在面试狗东时，有一道面试题没回答上来：Redis 的Bitmap和布隆过滤器啥区别与关系？ 其实就是考小老弟对这两种工具的底层数据结构是否了解，不算太难的题。不过，bitmap和布隆过滤器在大数据量和高并发业务的使用频率不低，知识点应该掌握下，既然问了那咱们简单的梳理下它们的底层原理、应用场景以及它们之间的关联。 Bitmap Redis中的Bitmap（位图）是一种较为特殊数据类型，它以最小单位bit来存储数据，我们知道一个字节由 8个 bit 组成，和传统数据结构用字节存储相比，这使得它在处理大量二值状态（true、false 或 0、1等只有两种状态）数据时具有极高的空间效率。不过，它不是一种全新的数据类型，其底层实现仍是基于 String 类型。 便于理解，你可以将 Bitmap 的底层结构看成是由一系列 bit 位组成的数组，在此数组中，每个位都对应一个偏移量（类似数组的下标）。通过将特定偏移量上的位值设置为 0 或 1，来表示不同的状态。 比如我们要设计一个答题游戏系统。其规则为：若用户答对全部 7 道题，则可获得大奖。 每个答题用户都有自己的 key，即 answer:user:X。使用 bitmap 记录用户的答题情况，将题号设置为对应偏移量，当用户答对 ✅ 题目时 ，偏移量位值设为 1；当用户答错 ❌ 题目时，位值设为 0。 假如用户user:1 答对了 2、5、7 号题，可将对应偏移量为 2、5、7 的位值设置为 1，其余位值默认设为 0。若要查看该用户对某个题目的回答情况，只需按照偏移量遍历此数据结构，一旦碰到位值为 1 的情况，即表示该题回答正确。 答题活动结束后，接下来需要统计获奖者，即那些全部答对 7 道题的用户。 要快速统计用户是否全部答对题目，可以使用 BITCOUNT 命令来统计位值中被设置为 1 的数量。通过执行 BITCOUNT answer:userX == 7 这样的操作进行判断，若结果等于 7，则表明该用户全部答对了题目。 聪明的你或许会产生疑惑，如果想用 bitmap 判断邮箱地址是否在黑名单内，偏移量该如何设置呢？遗憾的是，bitmap 并不支持直接以字符串作为偏移量。不过，我们可以对邮箱进行哈希运算得到哈希值，进而算出偏移量。 由于用到哈希运算，就不可避免地会出现数据碰撞问题，即不同的字符串可能得出相同的哈希值。这样一来，状态判断就可能不准确。别急，后边介绍布隆过滤器（Bloom Filter）看它如何来优化这个问题。 操作命令 Bitmap 的操作命令不多且使用简单，主要用到的就是SETBIT、GETBIT、BITCOUNT、BITOP几个命令。 SETBIT：用于设置指定偏移量上的位值，其时间复杂度为 O (1)。例如，当用户答对了第 7 题时，可以将题号对应的偏移量为 7 的位值设置为 1，以此表示该题已被答对。 # 用户key answer:user:1 # 偏移量：题号 7 # 题答对，置为 1 SETBIT answer:user:1 7 1 GETBIT：获取指定偏移量上的位值，同样具有高效的时间复杂度。可以快速查询用户对特定题号的回答状态。 # 查询用户第 7 题的回答情况，1-答对 0-答错 GETBIT answer:user:1 7 BITCOUNT：用于统计位值中被设置为 1 的数量。比如上边我可以很容易统计答对全部题目的用户，但也仅能知道个数，无法查看具体的哪个题目。 # 统计用户答对题为 1 的个数 BITCOUNT answer:user:1 BITOP：对一个或多个 bitmap 进行位运算，并将结果保存到新的键中，支持 AND、OR、NOT、XOR 四种操作。这个命令的用法是将多个bitmap中相同偏移量的位值进行运算。若我想知道用户 1 和用户 2 都答对的题目，经过 AND 运算后，假如只有题号 1 是两个用户都答对的题目，那么生成新的结果集中就只有题号 1 对应的位值为 1。 # 用户1 和 用户2 都答对的题目，可以看出只有题号1的都答对了 SETBIT answer:user:1 1 1 SETBIT answer:user:1 2 0 SETBIT answer:user:1 3 1 SETBIT answer:user:2 1 1 SETBIT answer:user:2 2 1 SETBIT answer:user:2 3 0 BITOP AND resultbitmap answer:user:1 answer:user:2 扬长避短 优点 极高空间效率：bitmap 是真的节省数据存储空间。