redis hyperlogog likely bitset map

问题原形
如果要实现这么一个功能：

统计 APP或网页 的一个页面，每天有多少用户点击进入的次数。同一个用户的反复点击进入记为 1 次。

聪明的你可能会马上想到，用 HashMap 这种数据结构就可以了，也满足了去重。的确，这是一种解决方法，除此之外还有其它的解决方案。

问题虽不难，但当参与问题中的变量达到一定数量级的时候，再简单的问题都会变成一个难题。假设 APP 中日活用户达到百万或千万以上级别的话，我们采用 HashMap 的做法，就会导致程序中占用大量的内存。

我们下面尝试估算下 HashMap 的在应对上述问题时候的内存占用。假设定义HashMap 中 Key 为 string 类型，value 为 bool。key 对应用户的Id,value是是否点击进入。明显地，当百万不同用户访问的时候。此HashMap 的内存占用空间为：100万 * (string + bool)。

条件选择
可以说，在上述问题目前现有的解决方案中，HashMap 是内存占用量最多的一种。如果统计量不多，那么可以使用这种方法解决问题，实现起来也简单。

除此之外还有B+ 树，Bitmap 位图，以及该文章主要介绍的 HyperLogLog算法解决方案。

在一定条件允许下，如果允许统计在巨量数据面前的误差率在可接受的范围内，1000万浏览量允许最终统计出少了一两万这样子，那么就可以采用HyperLogLog算法来解决上面的计数类似问题。

HyperLogLog
HyperLogLog，下面简称为HLL，它是 LogLog 算法的升级版，作用是能够提供不精确的去重计数。存在以下的特点：

代码实现较难。
能够使用极少的内存来统计巨量的数据，在 Redis 中实现的 HyperLogLog，只需要12K内存就能统计2^64个数据。
计数存在一定的误差，误差率整体较低。标准误差为 0.81% 。
误差可以被设置辅助计算因子进行降低。
稍微对编程中的基础数据类型内存占用有了解的同学，应该会对其只需要12K内存就能统计2^64个数据而感到惊讶。为什么这样说呢，下面我们举下例子：

取 Java 语言来说，一般long占用8字节，而一字节有8位，即：1 byte = 8 bit，即long数据类型最大可以表示的数是：2^63-1。对应上面的2^64个数，假设此时有2^63-1这么多个数，从 0 ~ 2^63-1，按照long以及1k = 1024字节的规则来计算内存总数，就是：((2^63-1) * 8/1024)K，这是很庞大的一个数，存储空间远远超过12K。而 HyperLogLog 却可以用 12K 就能统计完。

https://www.cnblogs.com/linguanh/p/10460421.html