你好，我是你的数据结构课老师蔡元楠，欢迎进入第 02 课时的内容“位数组在 Redis 中的应用”。 在上一讲中，我们一起深入学习了数组这个数据结构。这一讲我们来探讨数组的高阶应用，即位数组（Bit Array），以及这种数据结构是如何在 Redis 中应用的。 #### 统计每个月学习专栏的用户活跃度 在开始之前，我们先来考虑一个关于用户行为分析的问题，假设要统计《数据结构精讲：从原理到实战》这个专栏每个月的用户活跃度。在每个月中，只要有用户登录并且学习了这个专栏，都会将这个用户的 ID 写入一张 MySQL 表中。如果想知道在 2019 年 11 和 12 这两个月内都在学习这个专栏的用户有多少，应该怎么做呢？ 很直观的一个做法是执行类似下面的一个 SQL 语句： ``` SELECT COUNT(*) FROM nov_stats INNER JOIN dec_stats ON nov_stats.user_id = dec_stats.user_id WHERE nov_stats.logged_in_month = "2019-11" AND dec_stats.logged_in_mont = "2019-12" ``` 不过这种做法需要进入到数据库中去读取数据并且做内连接，效率不是那么高。是不是有更简单高效的做法呢？学完这一讲的内容后相信就能找到答案了。 * [ ] 比特与字节 我们经常听到一些人打趣地说：“在程序员的眼中，永远只有 0 和 1 ”。确实，计算机处理信息时的最小单位其实就是一个二进制单位，即比特（Bit）。而每 8 个二进制比特位都可以组成另一个单位，即字节（Byte），字节是内存空间中的一个基本单位。 因为比特只能表达“0”或者“1”两种状态，它非常适合用来表示布尔类型的状态。例如，我们可以用比特来表示用户是否有订阅《数据结构精讲：从原理到实战》这个专栏，“0”的状态位表示没有订阅，“1”的状态位表示已经订阅。 如果我们需要声明一个以比特为基本单位的数组，应该怎么做呢？我们都知道，一般在高级语言里面，是无法直接声明一个以比特为单位的基本类型的，而比特只有“0”或者“1”这两种状态，那最简单的方法是可以声明一个以 int 为单位的数组，这个数组的值我们规定只能为“0”或者“1”，用来表示比特位的“0”和“1”。 下面以 Java 为例，假设我们要声明一个大小为 2 的“比特数组”，其代码如下所示。 ``` int[] d = new int[2]; ``` 根据上面的声明，我们可以利用这个数组来表示两种不同的状态。但是这种方法有一个很明显的缺点，那就是消耗了过多的存储空间。无论是在 32 位还是 64 位的机器上，int 这种基本类型在 Java 中的大小都是占 4 个字节空间的，即总共占有 4 × 8 = 32 个比特位。从理论上来说，我们只是需要其中的一个比特位来记录状态，所以在这里整个数组浪费掉了 31 / 32 = 96.875% 的内存空间。 * [ ] 位数组 那有没有更好的方法呢？当然有，既然一个 int 类型是有 32 个比特位的，我们其实可以把数组中一个 int 类型的元素当作是可以表达布尔状态的 32 个比特位元素。这种将每个元素中的每一个比特位都作为状态信息存储的数组称之为位数组（Bit Array）或者位图（Bit Map）。 那我们来看看上面声明的拥有两个元素的 int 数组的内存模型是怎么样的。  这个位数组总共可以表达 64 个状态位，通过上图，我们可以得知，位数组在内存中的结构以及这个位数组索引的分布。 当我们要操作位数组中在位置为“i”这个比特位的时候，应该如何定位它呢？很简单，可以按照下面的公式来定位。 ``` 所在数组中的元素为： i / data_size 比特位在元素中的位置为：i % data_size ``` 那我们以定位索引为 35 这个比特位为例子来说明一下，套用上面的公式，可以得出： ``` 所在数组中的元素为： 35 / 32 = 1 比特位在元素中的位置为：35 % 32 = 3 ``` 所以这个比特位是位于 d[1] 这个元素上索引为 3 的位置。 一般来说因为位数组的元素只保存“0”或者“1”两种状态，所以对于位数组的操作有以下几种： * 获取某个位置的比特位状态； * 设置某个位置的比特位，也就是将那个位置的比特位设置为“1”； * 清除某个位置的比特位，也就是将那个位置的比特位设置为“0”。 * [ ] 位数组的实现 下面我们就以 Java 为例，自己动手来实现这三个操作的核心部分。 * （1）GetBit 我们可以声明 GetBit 的方法签名为： ``` boolean GetBit(int[] array, long index); ``` 这个方法将用于获取在 array 位数组中 index 位上的比特位是什么状态，如果为“1”则返回 true，如果为“0”则返回 false。 根据前面的介绍，获取比特位所在的元素以及比特位在元素中的位置公式，核心的算法如下： ``` boolean GetBit(int[] array, int index) { ... int elementIndex = index / 32; int position = index % 32; long flag = 1; flag = flag << position; if ((array[elementIndex] & flag) != 0) { return true; } else { return false; } } ``` 我们用以下这个位数组来验证一下，假设这个位数组的值如下图所示：  如果调用了 GetBit(d, 35) 这条语句，将得到 elementIndex 为 1、position 为 3、flag 为 0x08，将 d[1] 和 0x08 进行位操作的与运算，最后可以得出一个非 0 的结果，所以这个函数返回 true。 而如果调用了 GetBit(d, 32) 这条语句，我们将得到 elementIndex 为 1、position 为 0、flag 为 0x1，将 d[1] 和 0x1 进行位操作的与运算，最后可以得出一个 0 的结果，所以这个函数返回 false。 * [ ] SetBit 我们可以声明 SetBit 的方法签名为： ``` void SetBit(int[] array, long index); ``` 这个方法用于将 array 位数组中 index 位上的比特位设置为 1。 根据前面的介绍，获取比特位所在的元素以及比特位在元素中的位置公式，核心的算法如下： ``` void SetBit(int[] array, int index) { ... int elementIndex = index / 32; int position = index % 32; long flag = 1; flag = flag << position; array[elementIndex] | flag; } ``` 我们用下面这个位数组来验证一下，假设这个位数组的值如下图所示：  如果调用了 SetBit(d, 35) 这条语句，我们将得到 elementIndex 为1、position 为 3、flag 为 0x08，将 d[1] 和 0x08 进行位操作的或运算，设置完之后位数组的状态如下图所示  * [ ] ClearBit 我们可以声明 ClearBit 的方法签名为： ``` void ClearBit(int[] array, long index); ``` 这个方法用于将 array 位数组中 index 位上的比特位设置为 0。 根据前面的介绍，获取比特位所在的元素以及比特位在元素中的位置公式，核心的算法如下： ``` void ClearBit(int[] array, int index) { ... int elementIndex = index / 32; int position = index % 32; long flag = 1; flag = ~(flag << position); array[elementIndex] & flag; } ``` 我们用下面这个位数组来验证一下，假设这个位数组的值如下图所示：  如果调用了 ClearBit(d,32) 这条语句，我们将得到 elementIndex 为1、position 为 0、flag 为 0xFFFFFFFE，将 d[1] 和 0xFFFFFFFE 进行位操作的与运算，设置完之后位数组的状态如下图所示：  上面所介绍的三个位数组的函数操作时间复杂度都是 O(1)。 * [ ] Redis 中的 Bitmap 数据结构 在了解完位数组，以及我们自己实现了位数组的基本操作之后，我想和你介绍位数组在Redis中的应用。Redis 是一个开源的并且使用内存来作为存储空间的高效数据库，感兴趣的同学可以到官网 https://redis.io 上查看相关文档。 今天我想介绍的是在 Redis 里面的一个数据结构——Bitmap。Bitmap 在这里其实就是我们刚刚讲解的位数组。 Bitmap 的本质其实是在 Redis 里面通过一个 Strings 类型来表示的。在 Redis 中，Strings 的最大长度可以是 512MB。  也就是说，根据上面的计算，Bitmap 可以用来表示大概 42 亿多个状态，这对于大多数的应用已经足够了。 在 Redis 里面对 Bitmap 的操作命令有以下几种：BITCOUNT、BITFIELD、BITOP、GETBIT、SETBIT。其中，GETBIT 和 SETBIT 命令和前面我们自己所实现的 GetBit 和 SetBit 操作原理是一样的，感兴趣的同学可以前往 GitHub 链接来查看 Redis 中 Bitmap 的源码。 那回到这一讲最开始的那个问题，如果想知道同时在 2019 年 11 和 12 月学习这个专栏的用户有多少，可以做怎样的优化呢？ 我们可以用 Redis 里的 BITCOUNT、SETBIT 和 BITOP 来完成。BITCOUNT 这个命令其实是可以计算一个位数组里有多少比特位是为“1”的，而 BITOP 可以针对位数组进行“与”、“或”、“非”、“异或”这样的操作。 首先针对 11 月学习的用户和 12 月学习的用户，我们可以为它们创建单独的位数组，例如，logins:2019:11 和 logins:2019:12。在 11 月，每当有用户登录学习时，程序会自动调用“SETBIT logins:2019:11 user_id 1”，同理，对于 12 月登录学习的用户，我们也可以调用“SETBIT logins:2019:12 user_id 1”。SETBIT命令可以将user_id在位数组中相应的位设为“1”。 当要获得在这两个月内同时都学习了这个专栏的用户数时，可以调用“BITOP AND logins:2019:11-12 logins:2019:11 logins:2019:12”。将 logins:2019:11 和 logins:2019:12 这两个位数组做位运算中的与操作，将结果存放在“logins:2019:11-12”这个位数组中。最后调用“BITCOUNT logins:2019:11-12”来得到结果。 Redis 的 Bitmap 操作之所以强大，是因为所有操作都是位运算以及发生在内存中，所以速度极快。 我们今天一起学习了位数组这个数组的高级概念以及自己实现了它的基本操作，同时通过实例了解了位数组在 Redis 中的应用。位数组这种数据结构可以极大地优化内存空间，当我们要表达的状态只有true和false时，便可以考虑使用这种数据结构。 OK，这节课就讲到这里啦，下一课时我将分享“链表基础原理”，记得按时来听课哈。 #### 课后问答 * 1、老师，这个redis里面bitmap数据类型strings是一创建类型就有个512m的空间呢，还是动态增长，最大512呢？另外例子中user_id是个整形类型的吧，如果是非整型的字符串呢？在这里这个user_id是bitmap数组的index吧？如果user_id起始值很大，是否浪费了很多空间呢？谢谢？ 讲师回复： Redis的strings是动态增长 最大可以有512M，一般来说，处理id这种应用场景很少很少会用到非整数类型的。如果自己控制不了这个要求，可以通过hash function重新映射。这例子中为了方便讲解，里面的user_id就是bitmap位数组的index，当然如果实际情况id的offset非常厉害，我们也可以同样通过hash function重新映射到小一点的区间上。 * 2、假设一个对象有16种数据项，而每一种数据项都只有，是和否2种状态，那么就可以用一个字符数组 char bitchar[2]={0,0}表示初始状态。如果该对象其中某一个或者某几个数据项的状态为是，那么就修改对应的位为1，而此时bitchar中的数据值会发生相应的变化。这样只需要一个字符数组就可以存储该对象的16种状态值。相应的如果该对象的16个数据项都用一个byte来存放的话，需要16个字节，所以位数组节省了14个字节内存。极大的节省了空间。而且所有操作都是位运算以及发生在内存中，所以速度极快。可以这样理解吗？ 讲师回复： 是的，理解得完全正确，要保存16个状态位需要两个字节，可以像用户的那样声明，也可以short[1]这样声明，只要最终数据在内存中占据16 bits就好 * 3、想问下在setbit和clearbit函数中，做完逻辑运算不需要把结果赋值给array中相应的elementindex元素么？？ 讲师回复： 需要的，以SetBit(int[] array, int index)为例，这个函数的最后一个statement “array[elementIndex] | flag;”就是将结果赋予array中相应的元素。同理，clearbit函数中的最后一个statement中“array[elementIndex] & flag;”也是起到相应的作用。 * 4、Bitmap类型来表示的?为啥要用这个类型呢？ 讲师回复： 这涉及到 Redis 底层的设计了，至于使用 Strings 类型的原因，建议看看 Redis 官方文档里 Bitmaps 的介绍：https://redis.io/topics/data-types-intro?from=singlemessage&isappinstalled=0&scene=1&clicktime=1578364401&enterid=1578364401#bitmaps 简单理解为：可以复用最简单的 Strings 类型而不用再重新设计一个数据结构出来了。