Redis上层数据结构6-7：BitMap、HyperLogLog

BitMap

BitMap 即位图，是一串连续的二进制(0或1)数组，通过偏移量(offset)定位元素，时间复杂度 O(1)。

BitMap 本身使用 String 实现(sdshdr8)。

Redis 将String的 buf 数组每个 bit 位都利用起来，表示一个 BitMap。

需要注意 offset 从 0 开始。

> SETBIT me 10 1
0
> GETBIT me 10
1
> GETBIT me 1
0
> GETBIT me 11
0
# 获取1到11之间有几个1
> BITCOUNT me 1 11
1

特别适合一些数据量大且使用布尔值统计的场景。

签到中只有两种情况：签到 / 未签到，用 0 代表签到，1 代表未签到，则只需要使用很小的内存便可以表示大量用户。

只需要使用 12 MB 内存即可表示 1 亿数据。

同时，还可以用 BITCOUNT 统计该用户的签到情况，使用 BITPOS 统计首次签到时间段。

HyperLogLog(以下简称HLL) 是一种算法，并非 Redis 独有，由 Philippe Flajolet 教授提出，所以命令前缀使用 PF。

HLL 主要用来基数统计，所以它不是集合，不保存源数据，只保存数值。

一句话来说， HLL 提供不精确的去重计数。

在 Redis 里面，每个 HyperLogLog 键只需要花费 12 KB 内存，就可以计算接近 2^64 个不同元素的基数。

相比之下，相同数量的 8 字节 long 类型整数则需要 8388 TB 空间。

同时，HLL 的统计并不是完全准确，它的提出伊始即为了大数据量而精度要求低的统计工作，HLL 的标准误差为 0.81%。

HLL 的主要命令就三个：

# 将elements添加到key
PFADD key element [element ...]
# 统计基数
PFCOUNT key [key ...]
# 合并两个HLL
PFMERGE destkey sourcekey [sourcekey ...]

前文提到：HLL 的提出就是为了大数据量而精度要求低的统计工作。

根据此特性，一般情况有以下应用场景：

用一个 HLL 统计网页访问。用 PFCOUNT 统计访问数量。

正如前面提到的，HLL 是有误差的。

如果需要精确计算，还是需要使用 Set 或 Hash 类型。