龙岗地区做网站公司北京seo网站优化培训
目录
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的优势有两点：
- 存储开销小
- 统计总数快
用户签到
- 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 数
- 统计在线用户数
- 统计用户每天搜索不同词条的个数