摘要：使用原理設想成一次不斷投硬幣的過程，非正面即反面每一面的概率為。而當時，的概率接近為。所以，當時，沒有一次投擲次數大于的概率幾乎為。生成連續個的概率是，那么我們得到這個串時，可以估算，這個數據集的基數是。

對于海量數據來說，數據內存占用會變得很高. Probabilistic數據結構犧牲了一下準確率去換取更低內存占用。比如一個HyperLogLog的數據結構只需要花費12KB內存，就可以計算接近2^64個不同元素的基數，而錯誤率在1.625%.

HyperLogLog一個常用的場景就是統計網站的UV。

簡單來說，基數（cardinality，也譯作勢），是指一個集合（這里的集合允許存在重復元素）中不同元素的個數。例如看下面的集合：
{1,2,3,4,5,2,3,9,7}
這個集合有9個元素，但是2和3各出現了兩次，因此不重復的元素為1,2,3,4,5,9,7，所以這個集合的基數是7。

        
            net.agkn
            hll
            1.6.0
        

使用

    @Test
    public void testSimpleUse(){
        final int seed = 123456;
        HashFunction hash = Hashing.murmur3_128(seed);
        // data on which to calculate distinct count
        final Integer[] data = new Integer[]{1, 1, 2, 3, 4, 5, 6, 6,
                6, 7, 7, 7, 7, 8, 10};
        final HLL hll = new HLL(13, 5); //number of bucket and bits per bucket
        for (int item : data) {
            final long value = hash.newHasher().putInt(item).hash().asLong();
            hll.addRaw(value);
        }
        System.out.println("Distinct count="+ hll.cardinality());
    }

設想成一次不斷投硬幣的過程，非正面即反面（每一面的概率為0.5）。 在這個過程中，投擲次數大于k的概率是0.5^k（連續投擲出k個反面），在一次過程中，投擲次數小于k的概率是(1-0.5)^k。
因此，在n次投擲過程中，投擲次數均小于k的概率是

P(x<=k)=(1-0.5^k)^n  
P(x>=k)=1-(1-0.5^k)^n 

從以上公式，可以看出，當n<=k)的概率，接近為0。而當n>>k時，P(x<=k)的概率接近為0。所以，當n>>k時，沒有一次投擲次數大于k的概率幾乎為0。

將一次過程，理解成一個比特子串，反面為0，正面為1， 投擲次數k對應第一個1出現的位置，當統計子串足夠多時，其最大的第一個1的位置為j，那么當n>>2^j時，P(x<=k)接近為0，當n<<2^j時，P(x>=0)也趨向為0。也就是說，在得到x=k的前提下，我們可以認為n=2^j。

再通俗點說明： 假設我們為一個數據集合生成一個8位的哈希串，那么我們得到00000111的概率是很低的，也就是說，我們生成大量連續的0的概率是很低的。生成連續5個0的概率是1/32，那么我們得到這個串時，可以估算，這個數據集的基數是32。

HyperLogLog的核心思想原理

Probabilistic data Structures – Bloom filter and HyperLogLog for Big Data

HyperLogLog: 解讀Cardinality Estimation算法（第一部分：基本概念）