《算法图解》11.6读书笔记
一.布隆过滤器
布隆过滤器主要是用于去重，解决一定不存在的问题。
考虑这么一个应用。统计某段时间点击链接的用户数。因为要做到去重，可以选择set。但是对于set而言，内部使用的可能是hash结构，以空间换时间，内存占用高，改用string+布隆过滤器，能够有效节省内存。redis提供了这么一个模块。
（1）部署方法
1、部署在数据中心，如果只有一个数据中心，部署在数据中心，可以减少网络交互。
2、部署在redis中，如果有多个数据中心，避免维护多个布隆过滤器数据，可直接部署到redis当中。
当然，布隆过滤器+string 存在误差，只不过这种误差是可控的，因为布隆过滤器本来不存在的可能判断为存在，但是判断为不存在肯定不存在。
使用布隆过滤器，还是需要额外开辟很大空间来保存位图，这里介绍一个占用空间更小的统计模块。
（2）超对数算法hyperloglog
在redis实现中，每个键只使用 12KB 进行计数，使用 16384 （ 2 14 2^{14} 214） 个桶子，标准误差为0.8125% ，并且对可以计数的项目数没有限制，除非接近 2 64 2^{64} 264个项目数（这似乎不太可能）。
空间复杂度： O ( M ∗ l o g ( l o g N ) ) O(M*log(logN)) O(M∗log(logN)) 。hyperloglog与布隆过滤器不同，不是专门用来判断一个元素是否存在的，本质上是利用少量内存下统计一个集合中唯一元素数量的近似值，也不能知道这个key里面的具体value值都是什么。
hyperloglog使用随机化（hash函数实现）来提供一个集合中唯一元素数量的近似值，仅使用少量的内存（只记录对数值）。
HLL 的误差率为 1.04 m \frac{1.04}{\sqrt{m}} m1.04 。m 是桶子的个数。
（3）算法原理
当一个元素到来时，它会先根据hash函数得到一个64为位的值，然后hyperloglog会根据这个值，分为前50位和后14位。其中后14 位用来索引桶子，前面 50位用来统计最大低位连续0的个数，保存为最大低位连续0的话最大值为 49，使用6位数据就可以存下这个值。这样一来，每个HLL的key占用的空间就是16384*6/8/1024=12KB。每一个数字都需要知道其含义。
这里注意，hash散列到一个桶中，以一定的概率影响这个桶的计数值，因为是概率算法，单个桶的计数值并不准确，但是将所有的桶计数值进行调和均值累加起来，结果就会非常接近真实的计数值。
D V H L L = C ∗ ( m 2 ∑ j = 1 m 1 2 R j ) DV_{HLL} = C * (\frac{m^{2}}{\sum_{j=1}^{m}\frac{1}{2^{R_j}}}) DVHLL=C∗(∑j=1m2Rj1m2)
1 2 R j \frac{1}{2^{R_j}} 2Rj1：每个桶的估计值
m ∑ j = 1 m 1 2 R j \frac{m}{\sum_{j=1}^{m}\frac{1}{2^{R_j}}} ∑j=1m2Rj1m：所有桶估计值的调和平均数
C C C：常数，会随着m变化而变化。
下面解释两个概念。
低位最长连续0
给定一系列的随机整数 N，记录低位连续零位的最大长度 K， K 与 N的对数之间存在显著的线性相关性。 N ≈ 2 K N\approx2^{K} N≈2K
数学规律：如果 N 介于 ( 2 K , 2 K + 1 ) (2^{K}, 2^{K + 1}) (2K,2K+1) ，用这种方式估计的值都等于 2 K 2^{K} 2K，这显然是不合理的，这里可以采用多个 test 来加权估计，就可以得到比较准确的值。
二.调和平均
将计算分布在不同的桶中，通过计算平均数的方式来进行修改偏差。HLL 采用的是调和平均数（倒数的平均）。调和平均可以有效平滑离散值的影响。
三.存储
redis 中 hyperloglog 的encoding方法与redis内存使用原则一致数据量少的时候以节约内存和准确率为主，数据量大的时候以保证性能为主。具体来说，存储分为稀疏存储和紧凑存储。当元素很少的时候，redis采用节约内存的策略，hyperloglog采用稀疏存储方案；当存储大小超过3000 （可设置）的时候，hyperloglog 会从稀疏存储方案转换为紧凑存储方案。紧凑存储不会转换为稀疏存储，因为hyperloglog数据只会增加不会减少（不存储具体元素，所以没法删除）。
