认真写文章，用心做分享。
个人网站：yasinshaw.com
公众号：xy的技术圈
前面的文章介绍了Redis的五种最常用的对象及其底层的数据结构。这篇文章主要介绍一下一个不那么常用，却非常适用于一些特殊场景的对象：bitmaps。
面临的问题
先考虑几个常见的场景：
- 查询今天登陆的用户数量
- 查询今天有哪些用户登录了
- 查询某个用户是否点赞过某篇文章
- 查询某个用户是否连续两天都登陆
- 查询点赞过文章A且点赞过文章B的用户
这些需求可以使用数据库来实现，使用一些日志表，再通过SQL查询出来。但这样会浪费大量的磁盘空间，而且性能还很低。在数据量比较大的情况下，使用数据库来查询分析会非常慢。
这里要感谢我们计算机的科学家大佬们，发明了一种数据结构可以用来解决这类问题。它就是BitMap。也就是这篇文章主要介绍的Redis bitmaps底层使用的数据结构。
《编程珠玑》中第一篇讲的就是使用BitMap来排序大文件里面的数据。在一些面试里也会有类似的题目。
面试题目：一个10G的文件，里面全部是自然数，一行一个，乱序排列，对其排序。在32位机器上面完成，内存限制为2G。
LeetCode上有一个算法题，也是可以使用BitMap来解决：
算法题目：从0到n之间取出n个不同的数，找出漏掉的那个。注意：你的算法应当具有线性的时间复杂度。你能实现只占用常数额外空间复杂度的算法吗？
BitMap原理
BitMap其实是一个数据结构，它是利用了位运算的高性能，来存储和计算一些信息。接下来我们来介绍一下BitMap的原理。
BitMap是基于bit位的位置来记录信息的。比如我们现在有一个8位的BitMap。最开始时，所有位上都是0。
0, 0, 0, 0, 0, 0, 0, 0
然后有这么一个需求：假设今天有id为1,2,4,7这四个用户登录了我们的系统，我们想要把这个登录信息记录下来，就只需要在相应的位置标记为1就行了：
1, 1, 0, 1, 0, 0, 1, 0
这个时候，你想知道id为7的用户今天是否登录过系统，就只需要去看这个BitMap里面第7位是不是1就可以了。
可以看到，如果你使用一个list或者set来存的话，如果一个id是一个byte，占8位（真实情况可能是long类型，占64位），那8个id就要占64位，而使用BitMap只需要占用8位。同理，如果我们的id字段占了64位，那就可以节省64倍的空间。而且，可以利用位运算的特性，来快速实现统计、并集、交集等操作。
看过文章A的人有：1, 2, 4, 7:
1, 1, 0, 1, 0, 0, 1, 0
看过文章B的人有：1, 3, 4, 8:
1, 0, 1, 1, 0, 0, 0, 1
看过文章A且看过文章B的人有：
1, 1, 0, 1, 0, 0, 1, 0
&
1, 0, 1, 1, 0, 0, 0, 1
=
1, 0, 0, 1, 0, 0, 0, 0
得到看过文章A且看过文章B的人有：1， 4
上面的例子只能放8位，如果我的id是9怎么办？
BitMap是一个一个上面这样的数据来组成的。你可以使用一个可以扩容的整数数组来做，比如long数组。所以可以无限扩展。
如果id比较稀疏怎么办？
比如我要存入的id可能是1,101,1001这种比较稀疏的，如果用BitMap就会浪费一些空间。虽然现在开源的一些实现可以通过记录偏移量来解决这个问题，但也会因为频繁的分裂影响性能。这种场景下，其实不建议使用BitMap。
有兴趣的同学可以了解一下谷歌开源的EWAHCompressedBitMap，它解决了输入稀疏的问题。
BitMap实现
因为笔者主要熟悉Java语言，所以介绍一下Java语言对BitMap的实现。
JDK提供了一个BitMap的实现，叫BitSet，位于java.util包下。其底层使用的是一个long类型的数组，一个long代表一个word。但BitSet没有解决上面提到的输入稀疏的问题。谷歌开源的EWAHCompressedBitMap解决了输入稀疏的问题。
Redis提供了bitmaps对象。其实是使用的string对象，底层使用了我们上篇文章提到的SDS。所以会有512M的最大限制，即最多能存2^32个数据。如果你的id是long类型的，占64位，那可以使用两个bitmaps来存。
由SDS的底层实现可知，它是可以扩容和缩容的，但是如果输入比较稀疏，仍然会浪费大量的内存。所以如果输入很稀疏，也不建议使用Redis的bitmaps。
Redis bitmaps基本操作
总结
Redis提供了bitmaps对象。它在某些场景下可以节省空间，并显著提升性能。但如果输入比较稀疏（比如网站注册用户有1亿，但每天只有10万用户登录），那还不如使用set。
另外一方面，输入只能是整形。如果是字符串类型的，就没法使用这个数据结构了。
关注公众号：xy的技术圈
