假設你有一個很大的數據集，非常非常大，以至于不能全部存入內存。這個數據集中有重復的數據，你想找出有多少重復的數據，但數據并沒有排序，由于數據量太大所以排序是不切實際的。你如何來估計數據集中含有多少無重復的數據呢？這在許多應用中是很有用的，比如數據庫中的計劃查詢：最好的查詢計劃不僅僅取決于總共有多少數據，它也取決于它含有多少無重復的數據。

在你繼續讀下去之前，我會引導你思考很多，因為今天我們要討論的算法雖然很簡單，但極具創意，它不是這么容易就能想出來的。
一個簡單的樸素基數估計器

讓我們從一個簡單的例子開始吧。假定某人以下列方式來生成數據:

我們怎么估計結果數據集中有多少非重復的數字呢？了解到原來的數據集是隨機數,且充分分散，一個非常簡單的方法是：找出最小的數字。如果最大的可能的數值是 m，最小的值是 x，我們 可以估計大概有 m/x 個非重復的數字在數據集里面。舉個例子，如果我們掃描一個數字在 0 到 1 之間的數據集，發現最小的數字是 0.01。我們有理由猜想可能數據集里大概有 100 個非重復的數字。如果我們找到一個更小的最小值的話，可能包含的數據個數可能就更多了。請注意不管每個數字重復了多少次都沒關系，這是很自然的，因為重復多少次并不會影響?min?的輸出值.

這個過程的優點是非常直觀，但同時它也很不精確。不難舉出一個反例：一個只包含少數幾個非重復數字的數據集里面有一個很小的數。同樣的一個含有許多非重復數字的數據集含有一個比我們想像中更大的最小值，用這種估計方法也會很不精確。最后，很少有數據充分分散充分隨機的數據集。但是這個算法原型給了我們一些靈感使得我們有可能達到我們的目的，我們需要更精致一些的算法.
基于概率的計數

第一處改進來來自 Flajolet 和 Martin 的論文 Probabilistic Counting Algorithms for Data Base Applications。 進一步的改進來自 Durand-Flajolet 的論文 LogLog counting of large cardinalities 和 Flajolet et al 的論文 HyperLogLog：The analysis of a near-optimal cardinality estimation algorithm。從一篇論文到另一篇論文來觀察想法的產生和改進很有趣，但我的方法稍有不同，我會演示如何從頭開始構建并改善一個解決方法，省略了一些原始論文中的算法。有興趣的讀者可以讀一下那三篇論文，論文里面包含了大量的數學知識，我這里不會詳細探討.

首先，Flajolet 和 Martin 發現對于任意數據集，我們總可以給出一個好的哈希函數，使得哈希后的數據集可以是我們需要的任意一種排列。甚至充分分散的(偽)隨機數也是如此。通過這個簡單的靈感，我們可以把我們之前產生的數據集轉化為我們想要的數據集，但是這遠遠還不夠.