[[203755]]

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

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

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

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

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

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

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

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

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

oh，原來是直接調(diào)用了HashMap的containsKey這個方法，那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; 
} 

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

那如果一個值不存在呢?那就計數(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; 
} 

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

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; 
} 

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

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); 
 } 

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

size++

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

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

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

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

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

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

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

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