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

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

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

簡單來說，基數(shù)（cardinality，也譯作勢），是指一個(gè)集合（這里的集合允許存在重復(fù)元素）中不同元素的個(gè)數(shù)。例如看下面的集合：
{1,2,3,4,5,2,3,9,7}
這個(gè)集合有9個(gè)元素，但是2和3各出現(xiàn)了兩次，因此不重復(fù)的元素為1,2,3,4,5,9,7，所以這個(gè)集合的基數(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());
    }

設(shè)想成一次不斷投硬幣的過程，非正面即反面（每一面的概率為0.5）。 在這個(gè)過程中，投擲次數(shù)大于k的概率是0.5^k（連續(xù)投擲出k個(gè)反面），在一次過程中，投擲次數(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 

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

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

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

HyperLogLog的核心思想原理

Probabilistic data Structures – Bloom filter and HyperLogLog for Big Data

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