一、什么是 HyperLogLog ？什么用途？什么特點？
- HyperLogLog 本質(zhì)上是
一種算法，它提供了不精確（大概0.81%錯誤）的去重計數(shù)方法。 - 用途：
計數(shù)，比如統(tǒng)計網(wǎng)頁的UV (unique visitor)； - 特點：能夠在
不保存數(shù)據(jù)的情況下進(jìn)行去重計數(shù)，最多耗費12K的內(nèi)存便可以對大量數(shù)據(jù)進(jìn)行計數(shù)。
舉個例子來說明為什么要使用 HyperLogLog 算法進(jìn)行計數(shù)：
假如需要去統(tǒng)計某網(wǎng)頁的 UV:UV 的 全稱是unique visitor，指訪問用戶去重數(shù)，一天內(nèi)同一個用戶多次訪問只能算一次，通常和 PV (page view，頁面訪問次數(shù)) 一起來表示一個網(wǎng)站的日活程度。
傳統(tǒng)的解決方案：基于集合Set 不包含重復(fù)元素的特性，使用 Set 來保存用戶 id，然后統(tǒng)計 Set 中的元素數(shù)量來獲取頁面 UV。由于 Set 需要放在內(nèi)存中，因此這種方案只能承載少量用戶，一旦用戶數(shù)量大起來就需要消耗大量的內(nèi)存用來存儲用戶 id。但是實際上我們的目的是要統(tǒng)計用戶數(shù)量而不是保存用戶本身，因此這是個吃力不討好的方案！
HyperLogLog 方案：該方案最多需要 12K 的內(nèi)存就可以統(tǒng)計大量的用戶數(shù)，大概 0.81% 的錯誤率對于 UV 統(tǒng)計來說是可以忽略不計的。
因此 HyperLogLog 算法非常適合
二、HyperLogLog 原理
2.1 基數(shù)
基數(shù)是指不重復(fù)元素的個數(shù)，比如一個 列表 {1,2,3,4,5,6,7,6,8} 的基數(shù)是8。
2.2 HyperLogLog 原理
HyperLogLog 可以僅僅使用12K的內(nèi)存便可用來不精確（大概0.81%誤差）計算 2^64 個元素的基數(shù)，這個優(yōu)勢遠(yuǎn)勝于 Set 方法。
關(guān)于原理，可以參考博客：https://blog.csdn.net/tannuowaqin169/article/details/79732862。
2.3 HyperLogLog 算法與 Redis 去重計數(shù)的關(guān)聯(lián)
- 當(dāng)使用
PFADD命令添加一個計數(shù)元素后，該元素會被散列某個桶（bucket）中，就像是 HyperLogLog 中的隨機(jī)數(shù)，可以通過PFCOUNT命令去獲取基數(shù)； - HyperLogLog 分配12K內(nèi)存方式：算法實現(xiàn)過程中用到了
2^14 個桶，每個桶占6 bit，因此占據(jù)字節(jié)數(shù)為2^14*6/8=2^11*6=12K； - 事實上，HyperLogLog 算法并非時刻占據(jù)12K內(nèi)存，當(dāng)數(shù)據(jù)量較小時，為減少內(nèi)存占用采用稀疏矩陣，只有當(dāng)數(shù)據(jù)量到達(dá)閾值后變成 12K。
三、測試
啟動 redis-server 和 redis-client 進(jìn)程之后，使用命令添加計數(shù)元素，然后查詢計數(shù)情況。
- pfadd 命令： 添加計數(shù)元素；
- pfcount：獲取對所有元素的基數(shù)。
127.0.0.1:6379> pfadd pf1 redis
(integer) 1
127.0.0.1:6379> pfadd pf1 mongodb
(integer) 1
127.0.0.1:6379>
127.0.0.1:6379> pfadd pf1 oracle
(integer) 1
127.0.0.1:6379> pfcount pf1
(integer) 3
127.0.0.1:6379>
筆者水平有限，如有錯誤，敬請指正！
