Redis 实用小技巧——神奇的 bitmap（上）

简介

早在《Redis 实用小技巧——一文教你如何选择合适的 Key 类型》一文中时，就有老铁跟我留言说：「听说签到用 bitmap 实现效率更高哦」。没错，我也曾「听说」过，而且在工作当中也确实用过，给我的感觉是：bitmap 确实是个神奇的东西。

很久之前就想写篇关于 bitmap 文章了，但是又感觉仅是介绍几个案例并不足以让大家认识到它的神奇之处，于是，我打算从理论基础到实战应用，分成三个部分来给大家介绍。

OK，现在就跟我一起走进神奇的 bitmap 吧~

什么是 bitmap ？

让我们先来看一组图：

一张由 ASCII 字符组成的「像素图片」，一张电影院选座示意图，一张经典的扫雷图片，三者有什么关系呢？

发挥一下你的想象力：是不是都像是在一个「矩阵」里，按规则进行了一些「占位」操作，然后使这些位置具有了某种「表达力」呢？

「矩阵」+「占位」+「表达力」，正是我们今天讨论的主角「bitmap」的功力所在

bitmap，网上有译作「位图」的，其实在我们的应用场景中，把它译为「位映射」更为贴切，为什么这么说呢？且听我道来。

我们把 bitmap 拆成两个词来看：bit 和 map 。bit 描述的是我们的数据结构，即通过 bit 位的形式来进行存储。map 描述的是算法，一种具有映射功能的算法。bit-map 连在一起就可以用一句话来描述它的特点：

通过映射算法将数据映射到固定的 bit 位进行存储

这么做有什么特性呢？或者说为什么要变着法的这么玩呢？别急，让我们从 bit 和 map 单独说一说。

bit 存储

bit 存储的思想离不开它的应用场景。首先让我们来看这样的一个应用场景：

判断某一个 int 类型数据是否存在于一个 int 类型的数据集中？

假设我们现在是一个长度为 4 的 int 类型数组：[1, 3, 5, 7]，现在要判断 5 是否存在于这个数组中。
我们通常会这么做：首先我们需要把这个数组存下来。在 32 位的操作系统中，一个 int 类型的数据需要占用 4 个字节，四个 int 类型数据需要占用 16 字节，也就是说存储这个数组至少需要开辟 16 字节的内存空间。
如果现在有 20 亿 int 类型数据呢？需要分配多大空间呢？
2000000000 × 4 / 1024 / 1024 / 1024 ≈ 7.45 GB。是不是感觉快要撑爆了。
说明：
1 GB = 1024 MB
1 MB = 1024 KB
1 KB = 1024 Byte
1 Byte = 8 Bit

那有没有什么更好的存储办法呢？

让我们回过头来看一看这个场景：我们之所以需要 7.45 GB 的存储空间，是因为我们真真切切地把这些数据在计算机中存储下来了，但我们真的有必要把这些数据原封不动地存储下来吗？

还记得下面这个熟悉的画面吗？

曾几何时，一张纸也能代替三个人「占位」。如果后面的大哥不介意的话，一张纸将具有给三个人「占位」的威力。

联想到我们上面那个问题：我们的目的只是为了判断某个元素是否存在于一个数据集中。同样道理，我们能不能换种方式表达：判断某个位置上是否被「占用」呢？

这样，我们的处理思路就从原来的「存储数据」变成「位置赋值」了。那这样操作的话，存储空间上会带来什么变化呢？让我们来算一下：

同样还是 20 亿的 int 类型数据，这次我们需要申请 20 亿 bit 位的空间，占用的内存空间为：
2000000000 / 8 / 1024 / 1024 / 1024 ≈ 0.23 GB

比之前的方式节省了 32 倍的存储空间！是不是很划算呢？

但是你需要清楚，我们这么用是对应用场景有限制的：

• 因为使用的是比特位 0 或 1 来表示是否占用，用位置「即偏移量」来表示具体的数值，所以「表达力」有限，仅限于「某个位置是否有值」或者「有多少位置被赋予了值」类似的应用场景
• 与普通的 int 存储有所不同，在 32 位操作系统中，一个无符号的 int 类型占用 4 个字节，共 32 bit ，可以存储 0 - 2^32 - 1 之间的任意数值，而在位存储中，如果需要存储 2^32 - 1 这个数值的话，需要分配 2^32 个 bit 的内存空间，即 2^29 字节，512 MB 。可见，位存储分配的空间大小受到「最大边界」的影响，普通的存储则不会。反之，当数据集越来越大时，普通存储分配的空间也会随之变大，而位存储则不会发生变化（「最大边界」未发生变化的话）

由此可见，位存储只有在数据量巨大的时候，才能体现出它的优势，像简单的数据集，优势反而体现不出来。

让我们通过一张图来对比一下：

这个 1 byte 的比特位表示图，如果是普通存储的话，这里代表的是二进制整数 10001000 ，即十进制的 2^3 + 2^7 = 136 ，而在位存储中，这张图表达的含义则是：3 和 7 这两个位置被占用。直白点讲：前者表达的是整体的值，后者表达的是设置了值的偏移量。

map 映射

介绍完存储「数据结构」，接下来我们再来了解一下怎么存储的问题「算法」。我们把数据映射到具体的比特位的过程称之为「映射」，这里我们根据映射算法的区别来分成「普通映射」和「Hash 映射」介绍。

普通映射

因为在位存储中，偏移量都是通过整数来表示的，所以，所有通过整数来表达的数据我们都可以直接映射到对应的偏移量上。像上边的例子中，我们就是直接把需要存储的整数转换为对应的偏移量。

有些情况下，我们可能需要一些简单的逻辑转换，把数据转换成对应的偏移量。比如我们用 bitmap 来记录用户的签到情况，我们可以用日期来表示偏移量（20230605当成数字处理），bit 位的值表示是否签到。但这会导致我们初始分配的 bitmap 就很大，而且因为这样转换后的数字并不是连续的，在 bitmap 上会出现「断断续续」的数据分布。

更好的一种做法是换一种思路：我们可以单独记录下用户初始化签到的日期，然后用签到日期距离初始化日期的偏移量来当作 bitmap 的偏移量，这样处理就会好很多。

Hash 映射

在实际应用中，还有一些数据是无法直接用「普通映射」的方式映射成对应的偏移量的。比如，我们现在需要把每个人的信息记录到一张 bitmap 中，这里我们用用户的身份证号作为唯一标识，那么问题来了：如何把一个身份证号映射到对应的 bit 偏移量呢？

我们都知道，身份证号是一个 18 位的数字和字母（可能存在 X ）组成的「字符串」，显然不能直接转换成一个整数。那可不可以通过某种算法，把一个「字符串」最终转换成一个「整数」呢？

我们可能需要一个类似以下功能的映射函数：

N = f(s)
说明：N 表示转换后的整数，f() 表示映射函数，s 表示需要转换的身份证号。

这种映射函数用更专业的叫法叫作「哈希算法」。一个好的哈希算法一般具有以下特点：

• 正向快速: 给定明文和 Hash 算法，能在有限时间和有限资源内快速计算出 Hash 值
• 逆向困难: 对于给定 Hash 值，在有限时间和资源内很难 (基本不可能) 逆推出明文
• 输入敏感: 原始输入信息任意一点改动，产生的 Hash 值都应该是完全不同的
• 冲突避免: 很难找到两段内容不同的明文，使得它们生成的的 Hash 值一致

其中「快速计算」和「均匀分布」是考量 Hash 算法是否优秀的两个主要原则。

一般情况下的哈希算法生成定长的二进制值串就可以了，但是在 bitmap 操作中，我们还需要将定长的二进制值串转成一个整数的偏移量，以达到「映射」到 bit 位的目的。

尽管一个优秀的哈希算法会尽可能地「避免冲突」，但概率再低的事件，并非意味着不可发生。当分布区间分布的值超过一定量时，碰撞的几率将会上升。所以在实战部分，我们会看到为了降低 Hash 碰撞产生的「误判」，我们将会同时通过多个 Hash 算法来计算映射的值。

总结

在本文中，我们并没有过多地介绍复杂的理论知识，而是尽量通过通俗易懂的语言，让大家对 bitmap 有更形象的认识。纵观全文，其实理解 bitmap 并不难，可以通过以下一句话来概括：

bit 位存储，哈希映射，赋予「表达力」。

在下篇部分《Redis 实用小技巧——神奇的 bitmap（下）》，我们将来介绍 Redis 中 bitmap 相关的内容。

感谢大家的持续关注～

本作品采用《CC 协议》，转载必须注明作者和本文链接