基數估計算法就是使用準確性換取空間。 為了說明這一點，我們用三種不同的計算方法統計所有莎士比亞作品中不同單詞的數量。請注意，我們的輸入數據集增加了額外的數據以致比問題的參考基數更高。 這三種技術是：Java HashSet、Linear Probabilistic Counter以及一個Hyper LogLog Counter。結果如下：

?

?

該表顯示，我們統計這些單詞只用了512 bytes，而誤差在3%以內。相比之下，HashMap的計數準確度最高，但需要近10MB的空間，你可以很容易地看到為什么基數估計是有用的。在實際應用中準確性并不是很重要的，這是事實，在大多數網絡規模和網絡計算的情況下，用概率計數器會節省巨大的空間。

再者，如果我們要實現記錄網站每天訪問的獨立IP數量這樣的一個功能：

集合實現：

使用集合來儲存每個訪客的 IP ，通過集合性質（集合中的每個元素都各不相同）來得到多個獨立 IP，然后通過調用 SCARD 命令來得出獨立 IP 的數量。

舉個例子，程序可以使用以下代碼來記錄 2017 年 12 月 5 日，每個網站訪客的 IP ：

ip = get_vistor_ip() SADD'2017.12.5::unique::ip'ip

然后使用以下代碼來獲得當天的唯一 IP 數量：

SCARD'2017.12.5::unique::ip'

集合實現的問題

使用字符串來儲存每個IPv4 地址最多需要耗費15 字節（格式為 ‘XXX.XXX.XXX.XXX’，比如’202.189.128.186’）。

下表給出了使用集合記錄不同數量的獨立 IP 時，需要耗費的內存數量：

獨立IP數量 一天 一個月 一年
一百萬?15 MB?450 MB?5.4 GB?
一千萬?150 MB?4.5 GB?54 GB?
一億?1.5 GB?45 GB?540 GB?

隨著集合記錄的 IP 越來越多，消耗的內存也會越來越多。另外如果要儲存 IPv6 地址的話，需要的內存還會更多一些。為了更好地解決像獨立 IP 地址計算這種問題，Redis 在 2.8.9 版本添加了 HyperLogLog 結構。

Redis數據結構HyperLogLog

Redis HyperLogLog 是用來做基數統計的算法，HyperLogLog 的優點是，在輸入元素的數量或者體積非常非常大時，計算基數所需的空間總是固定的、并且是很小的。在Redis 里面，每個 HyperLogLog 鍵只需要花費 12 KB 內存，就可以計算接近 2^64 個不同元素的基數。這和使用集合計算基數時，元素越多耗費內存就越多的集合形成鮮明對比。但是，因為 HyperLogLog 只會根據輸入元素來計算基數，而不會儲存輸入元素本身，所以 HyperLogLog 不能像集合那樣，返回輸入的各個元素。

什么是基數?

比如數據集 {1, 3, 5, 7, 5, 7, 8}， 那么這個數據集的基數集為 {1, 3, 5 ,7, 8}, 基數(不重復元素)為5。 基數估計就是在誤差可接受的范圍內，快速計算基數。

估算值：算法給出的基數并不是精確的，可能會比實際稍微多一些或者稍微少一些，但會控制在合理的范圍之內。

幾個命令

將元素添加至 HyperLogLog

1、PFADD key element [element …]

將任意數量的元素添加到指定的 HyperLogLog 里面。

這個命令可能會對 HyperLogLog 進行修，以便反映新的基數估算值，如果 HyperLogLog 的基數估算值在命令執行之后出現了變化，那么命令返回1，否則返回0。

命令的復雜度為 O(N) ，N 為被添加元素的數量。

2、PFCOUNT key [key …]

返回給定 HyperLogLog 的基數估算值。

當只給定一個 HyperLogLog 時，命令返回給定 HyperLogLog 的基數估算值。

當給定多個 HyperLogLog 時，命令會先對給定的 HyperLogLog 進行并集計算，得出一個合并后的HyperLogLog ，然后返回這個合并 HyperLogLog 的基數估算值作為命令的結果（合并得出的HyperLogLog 不會被儲存，使用之后就會被刪掉）。

當命令作用于單個 HyperLogLog 時， 復雜度為 O(1) ， 并且具有非常低的平均常數時間。

當命令作用于多個 HyperLogLog 時， 復雜度為 O(N) ，并且常數時間也比處理單個 HyperLogLog 時要大得多。