[[203755]]

hello哈，大家是不是好久沒(méi)見(jiàn)到我啦?我也是一直在摸索小伙伴們喜歡看到什么東西，不喜歡看什么東西，還請(qǐng)大家多多支持。為了表示感謝。小蕉在這給你們一鞠躬，二鞠躬，三。事不過(guò)三~

1+0=1你都不會(huì)談什么大數(shù)據(jù)?

這篇呢，又是開(kāi)坑之作，這是一個(gè)系列，主要會(huì)將大數(shù)據(jù)下的計(jì)數(shù)原理。說(shuō)到計(jì)數(shù)，不知道大家會(huì)***印象想到什么，我估計(jì)會(huì)是。。數(shù)手指。。沒(méi)錯(cuò)，小蕉從小學(xué)開(kāi)始就開(kāi)始數(shù)手指，所有20以內(nèi)的加減法很早就掌握了。研表究明，這估計(jì)也是我們現(xiàn)在使用十進(jìn)制的原因，如果我們每個(gè)人每只手都有6只手指，那我們可能就用十二進(jìn)制了。

好了不扯了，那用程序怎么計(jì)數(shù)呢?要去重那種。按照我拍腦袋設(shè)想呢，***印象，嗯用HastSet準(zhǔn)沒(méi)錯(cuò)，但是HashSet占用的內(nèi)存有多少你們知道嗎?可以裝下我一年的米飯。內(nèi)存占用太大，所以就有了后面的B-tree，Bitmap，Bloom Filter，Linear Counting，LogLog Counting，Adaptive Counting，HyperLogLog Counting，HyperLogLog++ Counting。

如果現(xiàn)在你們一個(gè)都聽(tīng)不懂的話，那就對(duì)了，但那也木有關(guān)系，我會(huì)一個(gè)一個(gè)跟你們講清楚噠。(如果我不斷更的話，嗯)

那***篇就開(kāi)始講HashSet是怎么進(jìn)行計(jì)數(shù)的吧。首先我們看一下HashSet的底層結(jié)構(gòu)是什么。

from HashSet 
private transient HashMap<E,Object> map; 
public HashSet() { 
    map = new HashMap<E,Object>(); 
} 

唔，咩你甘噶。想不到你是這樣的HashSet，底層居然是一個(gè)私有的無(wú)法序列化的HashMap，黑人問(wèn)號(hào)臉。計(jì)數(shù)嘛，我們就會(huì)想知道，集合中有沒(méi)有存在過(guò)這個(gè)數(shù)字，那HashSet是怎么知道它自己的集合中有沒(méi)有存在某個(gè)值的呢?

from HashSet 
public boolean contains(Object o) { 
    return map.containsKey(o); 
} 

oh，原來(lái)是直接調(diào)用了HashMap的containsKey這個(gè)方法，那HashMap又是怎么找的呢?

from HashMap 
final Entry<K,V> getEntry(Object key) { 
    int hash = (key == null) ? 0 : hash(key.hashCode()); 
    for (Entry<K,V> e = table[indexFor(hash, table.length)]; 
         e != null; 
         e = e.next) { 
        Object k; 
        if (e.hash == hash && 
            ((k = e.key) == key || (key != null && key.equals(k)))) 
            return e; 
    } 
    return null; 
} 

看不懂也沒(méi)關(guān)系我講給你聽(tīng)。首先算一下key的hash值，然后在自己的HashEntry的數(shù)組里面(其實(shí)就是一個(gè)元素都是鏈表的數(shù)組，哎呀好拗口)，找到對(duì)應(yīng)的HashEntry，找到之后呢，再根據(jù)鏈表一個(gè)一個(gè)找，如果發(fā)現(xiàn)key的hash值，引用，或者equals完全相等，嗯沒(méi)錯(cuò)，那這個(gè)key就已經(jīng)存在在HashSet中啦。這時(shí)候計(jì)數(shù)就不用+1了。

那如果一個(gè)值不存在呢?那就計(jì)數(shù)+1，順便把自己放到集合里邊嘛~怎么放呢?程序員有一句黑話叫，"don't bb，show me the code"。

from HashSet 
private static final Object PRESENT = new Object(); 
public boolean add(E e) { 
    return map.put(e, PRESENT)==null; 
} 

由此可見(jiàn)，也只是調(diào)用了HashMap的put方法，還特么把一個(gè)叫PRESENT的不知道什么鬼的靜態(tài)的私有的無(wú)法修改的Object當(dāng)成value值了。oh好像這樣也可以理解，我們只是需要借助HashMap的key就知道重不重復(fù)了。至于HashMap是怎么put一個(gè)值得呢?

from HashMap 
public V put(K key, V value) { 
    if (key == null) 
        return putForNullKey(value); 
    int hash = hash(key.hashCode()); 
    int i = indexFor(hash, table.length); 
    for (Entry<K,V> e = table[i]; e != null; e = e.next) { 
        Object k; 
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { 
            V oldValue = e.value; 
            e.value = value; 
            e.recordAccess(this); 
            return oldValue; 
        } 
    } 
    modCount++; 
    addEntry(hash, key, value, i); 
    return null; 
} 

好這一堆基本都不用看，就看那個(gè)addEntry就夠了，上面一大坨大概的意思就是，如果key已經(jīng)存在了，那就覆蓋原有的value值，然后就啥也不干，這不是我們本次的重點(diǎn)(modCount跟線程安全有關(guān)感興趣同學(xué)自省度娘)。

from HashMap 
  void addEntry(int hash, K key, V value, int bucketIndex) { 
        Entry<K,V> e = table[bucketIndex]; 
               table[bucketIndex] = new Entry<K,V>(hash, key, value, e); 
               if (size++ >= threshold) 
                   resize(2 * table.length); 
 } 

這一小段大概的意思呢，就是，把原來(lái)HashEntry的數(shù)組對(duì)應(yīng)hash位置的值拿出來(lái)，然后把現(xiàn)在的值接到最前面去。然后非常關(guān)鍵的代碼出現(xiàn)了。

size++

哇哇哇，size++，嗯，計(jì)數(shù)靠譜了，可以計(jì)數(shù)了。

from HashSet 
public int size() { 
    return map.size(); 
} 
from HashMap 
public int size() { 
    return size; 
} 

嗯我們可以看到，就是直接把size返回了。

到這里我們已經(jīng)說(shuō)完了HashSet的計(jì)數(shù)原理啦。那么如果有N個(gè)值，這個(gè)HashSet需要多少空間呢?假設(shè)整個(gè)HashMap都放滿了。

至少需要N*8+PRESENT，還要加上HashEntry的開(kāi)銷，只能說(shuō)是吃內(nèi)存大戶。

下一次，我們繼續(xù)聊聊，稍微不太那么占內(nèi)存的計(jì)數(shù)方法。

【本文為51CTO專欄作者“大蕉”的原創(chuàng)稿件，轉(zhuǎn)載請(qǐng)通過(guò)作者微信公眾號(hào)“一名叫大蕉的程序員”獲取授權(quán)】

戳這里，看該作者更多好文