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

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

HyperLogLog一個常用的場景就是統(tǒng)計網(wǎng)站的UV。

簡單來說，基數(shù)（cardinality，也譯作勢），是指一個集合（這里的集合允許存在重復元素）中不同元素的個數(shù)。例如看下面的集合：
{1,2,3,4,5,2,3,9,7}
這個集合有9個元素，但是2和3各出現(xiàn)了兩次，因此不重復的元素為1,2,3,4,5,9,7，所以這個集合的基數(shù)是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）。 在這個過程中，投擲次數(shù)大于k的概率是0.5^k（連續(xù)投擲出k個反面），在一次過程中，投擲次數(shù)小于k的概率是(1-0.5)^k。
因此，在n次投擲過程中，投擲次數(shù)均小于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時，沒有一次投擲次數(shù)大于k的概率幾乎為0。

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

再通俗點說明： 假設我們?yōu)橐粋€數(shù)據(jù)集合生成一個8位的哈希串，那么我們得到00000111的概率是很低的，也就是說，我們生成大量連續(xù)的0的概率是很低的。生成連續(xù)5個0的概率是1/32，那么我們得到這個串時，可以估算，這個數(shù)據(jù)集的基數(shù)是32。

HyperLogLog的核心思想原理

Probabilistic data Structures – Bloom filter and HyperLogLog for Big Data

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