当前位置：首页 > news >正文

网站一直维护意味着什么wordpress 建设论坛

news 2025/9/16 9:05:30

网站一直维护意味着什么,wordpress 建设论坛,校庆专题网站建设方案,手机建设网站目录 BitMap 常用命令应用场景日活统计用户签到 HyperLogLog 什么是基数? 常用命令应用场景 BitMap 问: "有10亿个不重复的无序的正数，如果快速排序？" 这看上去很简单，就是一个排序而已，但是大部分排序算…

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）的近似值。是可接受的范围。