redis位图-bitmap

定义

见名知义，位映射，其实就是string类型的bit数组，并不是redis的基本数据类型，而是在string的基础上做的扩展，支持对位进行操作。

作用

精准的基数计数，既可以不保存统计对象，也可以只保存统计对象的integer类型的id。一个bit就可以做一次计数或表示一个对象，比set更节省空间。

如：统计一段时间内的用户行为，如签到、访问、点赞等；或者对大量数据作去重处理，如40亿个QQ号去重。使用bitmap时不再把redis用作缓存，而是用作db。效率高尤其是数据量大时节省空间。

基本操作

1. setbit： 设置位的值为0或1，格式是：setbit key offset bit。设置成功后，返回offset上原来的值。 直接操作相应offset，所以时间复杂度是O(1)。
2. getbit： 获取位的值，在key不存在、位不在key的内存空间或位上的值是0时，都返回0。 格式是：getbit key offset。 直接操作相应offset，所以时间复杂度是O(1)。
3. bitcount： 计算汉明重量。统计指定范围内的值是1的位数，默认统计整个key。如果key不存在，返回0。主要用于统计触发相应事件的次数。 格式是：bitcount key [start,[end]]。start，end用作闭区间，且指的是字节而不是位，1byte=8bit。可以是负数，-1是最后一个字节，-2是倒数第二个字节，以此类推。 要依次查看区间内的每个位置，所以时间复杂度是O(n)。
4. bitpos： 在key中查找第一次出现指定bit的偏移量。一般情况下，找到就返回对应的offset，如果没找到或key不存在，返回-1。但有特殊情况！ 格式是：bitpos key bit [start,[end]]。区间的使用同bitcount。 如果bit是0，查找行为会有点特殊：如果未指定区间，或只指定了start，如果找不到0，会最最后一位补0，然后返回该位置对应的offset。即，在未指定闭区间的情况下，如果找不到0，会出现补0的情况。 要依次查看区间内的每个位置，所以时间复杂度是O(n)。
5. bitop：略
6. string的所有指令：因为bitmap不是基本数据类型，底层是string。

内存分配

1. 以字节为最小单位进行分配
2. 使用setbit时，如果key不存在，会分配一个长度包含offset的内存空间。
3. 使用setbit时，如果offset超出当前内存空间，进行扩容。
4. 因为bitmap底层使用string实现，其最大内存和string相同，都是512M。也就是最大只能分配512M的内存，对应的offset是(2^32)-1。

大内存分配会造成redis的卡顿！！

使用strlen查看bitmap的内存空间长度，返回的单位是字节。

初始化

填充0的初始化：

1. 使用setbit时，如果key不存在，会初始化一个长度是n字节且包含offset的内存空间，所有bit位使用0填充。
2. 使用setbit时，如果offset超出现有内存空间的长度，会以字节基本长度扩容空间保证包含offset，新扩容的空间使用0填充。

填充1的初始化：

使用string来初始化bitmap，关键环节就是把需要的字节序列通过ascii转换成对应的字符串，然后使用set指令把key的值设置为该字符串即可。

步骤如下：

1. 把需要的bitmap需要以8位为一组进行划分，即按字节划分。
2. 把每组转换为十进制，查看该十进制对应的ascii字符
3. 从左到右拼接每组的字符为字符串，使用set指令把key的值设置为该字符串
4. 使用getbit对设置后的key进行验证。

对于ascii码小于32或大于126的分组，可以尝试合并3个分组为一组，使用utf8码表。查utf8码表时，需要把二进制转换为十六进制。

set bt1 '18'
# 得到的bitmap就是：00110001 00111000
set bt2 "你"
# 得到的bitmap就是：11100100 10111101 10100000
# 十六进制是：e4bda0

bitmap和string的异同

1. bitmap不是基本的数据类型，是基于string实现的。
2. 两者的指令是互相通用的，即可以使用string的指令set/get操作bitmap数据，也可以使用bitmap的指令getbit/setbit操作string数据。
3. 可以使用string来初始化bitmap。

注意事项

1. 偏移量计算是从左到右，而不是按照二进制的右为低位左为高位的方式。
2. 内存的分配以字节位最小单位，即每次最少分配8位，内存空间的位数始终是8的倍数。
3. bitmap和string的指令是互通的。
4. offset的取值范围是[0,2^32)。
5. bit只能是0或1，否则会报错。
6. 如果key存在且不是string，报错。

使用场景

1. n亿用户7天签到
2. n亿用户年度在线状态
3. 40亿QQ去重

参考推荐

http://redisdoc.com/bitmap/index.html

https://zhuanlan.zhihu.com/p/401726844

https://juejin.cn/post/7074747080492711943