BitMap 和 HyperLogLog

目录

BitMap

常用命令

应用场景

日活统计

用户签到

HyperLogLog

什么是基数?

常用命令

应用场景

---

BitMap

问: "有10亿个不重复的无序的正数，如果快速排序？"

这看上去很简单，就是一个排序而已，但是大部分排序算法都需要把数据放到内存里面操作，这10亿个数字得占用多少内存？

在大部分编程语言里面，int类型一般的都是占4个byte，也是32位，不管这个数字是1 或者是 21亿都得占32位，所以如果现在有10亿数字需要存放在内存里面，需要多少内存呢？

以Java为例，1000000000 * 4 / 1024 / 1024 = 3814.69MB，大概需要3814.69MB内存！

假如有 1，3，7，2，5 这5个数字需要存放，正常情况下你需要5*4=20byte，但bitmap只需要1byte，即桶排的思想。

setbit的大小在0到2的32次方（最大使用512M内存）之间，即0~4294967296（42亿）之间。

常用命令

bitmap主要就三个操作命令：

• setbit（设置标记）
• getbit（即 getbit key index ，如果返回1，表示存在否则不存在）
• bitcount（即 bitcount key ，统计和）

应用场景

日活统计

统计应用或网站的日活，这个属于比较常见的case了，如果是用redis来做这个事情，首先我们最容易想到的是Hash结构，存储如下：

• 日期（key，如“2024-03-17”）userId（field，如“134”）true（value）
• 判断日活则是统计map的元素个数

以上设计其实没什么问题，但如果日活量很高的话，会造成大Key问题（这里Value会很大），我们看一下bitmap可以怎么做

• setbit 日期 uesrId 1
• bitcount 日期

简单对比一下上面两种方案

当数据量小时，且userid分布不均匀，小的为个位数，大的几千万，上亿这种，使用bitmap就有点亏了，因为userId作为index，那么bitmap的长度就需要能容纳最大的userId，但是实际日活又很小，说明bitmap中间有大量的空白数据。

反之当数据量很大时，比如百万/千万，userId是连续递增的场景下，bitmap的优势有两点：

1. 存储开销小
2. 统计总数快

用户签到

• setbit 用户id+年月 dayofmonth 1
• bitcount 用户id+年月

HyperLogLog

• HyperLogLog是用来做基数统计的算法，不是集合，不会保存元数据，只记录数量而不是数值。
• HyperLogLog的优点是，在输入元素的数量或者体积非常非常大时，计算基数所需的空间总是固定的、并且是很小的。
• 在 Redis 里面，每个 HyperLogLog 键只需要花费 12 KB 内存，就可以计算接近 2^64 个不同元素的基数。这和计算基数时，元素越多耗费内存就越多的集合形成鲜明对比。
• 基数估计的结果是一个带有 0.81% 标准错误（standard error）的近似值。是可接受的范围。

什么是基数?

比如数据集(1，3，5，7，5，7，8}， 那么这个数据集的基数集为{1，3，5 ，7，8}，基数(不重复元素)为5。基数估计就是在误差可接受的范围内，快速计算基数。

常用命令

• PFADD key element [element ...]：添加指定元素到 HyperLogLog 中
• PFCOUNT key [key ...]：返回给定 HyperLogLog 的基数估算值
• PFMERGE destkey sourcekey [sourcekey ...〕：将多个 HyperLogLog 合并为一个 HyperLogLog

应用场景

说明：有局限性，就是只能统计基数数量，而没办法去知道具体的内容是什么

一般使用：

• 统计注册 IP 数
• 统计每日访问 IP 数
• 统计页面实时 UV 数
• 统计在线用户数
• 统计用户每天搜索不同词条的个数