關(guān)于HashMap的源碼解讀一

基于JDK1.8的HashMap源碼中的一些比較有意思的點(diǎn)的解析。

1厢岂、為什么Hash的加載因子是0.75光督？

其實(shí)這一點(diǎn)在源碼的注釋上有說明阳距；其本質(zhì)就是就是空間利用率與查找時(shí)間的一個(gè)折中。
其中涉及到了泊松分布的問題结借，這里就不做過多的解釋（畢竟概率論的東西我也忘得差不多了）筐摘。
如果這個(gè)加載因子太小的話。則空間利用率很低，還沒put幾個(gè)元素就觸發(fā)擴(kuò)容了（擴(kuò)容就會涉及到rehash操作咖熟，開銷比較大）圃酵。
如果加載銀子太大，則hash碰撞的概率很高了馍管。且這時(shí)候郭赐，可能已經(jīng)形成了鏈表了。甚至?xí)|發(fā)鏈表轉(zhuǎn)為樹的操作（在具有良好分布的用戶hashCode的用法中确沸，很少使用樹）捌锭。對查詢效率不利。
而源碼中解釋了為什么0.75最好罗捎。這里貼一部分源碼的說明：
     * Because TreeNodes are about twice the size of regular nodes, we
     * use them only when bins contain enough nodes to warrant use
     * (see TREEIFY_THRESHOLD). And when they become too small (due to
     * removal or resizing) they are converted back to plain bins.  In
     * usages with well-distributed user hashCodes, tree bins are
     * rarely used.  Ideally, under random hashCodes, the frequency of
     * nodes in bins follows a Poisson distribution
     * (http://en.wikipedia.org/wiki/Poisson_distribution) with a
     * parameter of about 0.5 on average for the default resizing
     * threshold of 0.75, although with a large variance because of
     * resizing granularity. Ignoring variance, the expected
     * occurrences of list size k are (exp(-0.5) * pow(0.5, k) /
     * factorial(k)). The first values are:
     *
     * 0:    0.60653066
     * 1:    0.30326533
     * 2:    0.07581633
     * 3:    0.01263606
     * 4:    0.00157952
     * 5:    0.00015795
     * 6:    0.00001316
     * 7:    0.00000094
     * 8:    0.00000006
     * more: less than 1 in ten million
大概翻譯一下：
因?yàn)門reeNode的大小約為常規(guī)節(jié)點(diǎn)的兩倍观谦，所以我們僅在桶（bins）包含足以保證使用的節(jié)點(diǎn)時(shí)才使用它們。-- 反正就是盡量不用到樹桨菜，當(dāng)鏈表長度達(dá)到8的時(shí)候會轉(zhuǎn)換為樹結(jié)構(gòu)）
并且當(dāng)它們變得太谢碜础（由于移除或調(diào)整大小）時(shí)倒得，它們會轉(zhuǎn)換回普通bins（鏈表結(jié)構(gòu)）泻红。-- 當(dāng)長度又降到6的時(shí)候，就會從樹變成鏈表屎暇，為什么不是小于8就變呢承桥，這里涉及到一個(gè)臨近問題，假設(shè)頻繁的在7個(gè)8之間切換根悼，這會頻繁的鏈轉(zhuǎn)樹凶异，樹轉(zhuǎn)鏈，這樣很不好挤巡。 
在具有良好分布的用戶hashCode的用法中剩彬，很少使用樹。理想情況下矿卑，在隨機(jī)hashCodes下喉恋，bin中節(jié)點(diǎn)的頻率遵循Poisson分布，默認(rèn)調(diào)整大小的參數(shù)平均閾值為0.75 母廷，盡管由于調(diào)整粒度而差異很大轻黑。忽略方差，列表大小k的預(yù)期出現(xiàn)次數(shù)是（exp（-0.5）* pow（0.5琴昆，k）/ * factorial（k））氓鄙。第一個(gè)值是：
     * 0:    0.60653066
     * 1:    0.30326533
     * 2:    0.07581633
     * 3:    0.01263606
     * 4:    0.00157952
     * 5:    0.00015795
     * 6:    0.00001316
     * 7:    0.00000094
     * 8:    0.00000006
     * more: less than 1 in ten million
最后這段話我沒太懂，我的理解是业舍，當(dāng)加載因子是0.75的時(shí)候抖拦，由于hash碰撞而產(chǎn)生的鏈表長度達(dá)到8的概率已經(jīng)很低了升酣。

2、關(guān)于構(gòu)造函數(shù)中的tableSizeFor方法的分析态罪？

/**
     * Returns a power of two size for the given target capacity.
     */
    static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

 該方法到底在做什么呢噩茄？其實(shí)就是返回一個(gè)大于等于用戶指定的初始容量的2次冪數(shù)：用戶輸入7，就返回8复颈。用戶輸入10绩聘，就返回16.

 >>> 表示無符號右移，左邊補(bǔ)0耗啦；
 a |= b表示將a與b做或運(yùn)算再賦值給a君纫，比如：
                                    int a = 5; // 0000 0101
                                    int b = 3; // 0000 0011
                                    a |= b; // 0000 00111

接下來解釋一下這個(gè)方法具體怎么做：
int n = cap - 1   的作用是假如用戶傳入的就是一個(gè)2的n次冪的數(shù)。比如8.這里做減1操作芹彬，就是為了讓結(jié)果是8蓄髓，而不是16.先記住這個(gè)結(jié)論。
然后接下來是一堆的位運(yùn)算舒帮，這部分運(yùn)算就是為了得到一個(gè)最高位與用戶輸入的最高位的一致的2的n次冪-1的數(shù)会喝；
 eg： 假設(shè)用戶輸入的數(shù)為   
                            0001xxxx xxxxxxxx（不弄32位了，大概一下能看懂就行）
        temp = n >>> 1   ： 00001xxx xxxxxxxx
        n |= temp        ： 00011xxx xxxxxxxx
        temp n >>> 2     ： 0000011x xxxxxxxx
        n |= temp        ： 0001111x xxxxxxxx
        temp =n >>> 4    ： 00000001 111xxxxx
        n |= temp        ： 00011111 111xxxxx
        ...
        會得到一個(gè) 000111111 11111111這樣的數(shù)字玩郊。
        為什么最多要到 n |= n >>> 16;因?yàn)閕nt是32位的肢执，經(jīng)過1 2 4 8 16剛好就可以處理最多32位的數(shù)
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
        最后將剛才的結(jié)果+1后，就可以得到一個(gè)
        00100000 00000000 --> 2^13次方的數(shù)译红；
現(xiàn)在在回頭看看 int n = cap - 1预茄，就能知道它的用意了吧。

3侦厚、HashMap的容量為什么是2的n次方耻陕？

其實(shí)這個(gè)與HashMap的put方法有關(guān)。這里有必要先說下HashMap的存儲過程：
  1刨沦、計(jì)算出key的hash值诗宣，將該值進(jìn)一步散列一下（就算使得該值的二進(jìn)制中0101分布得更加均勻）
  2、將上述得到的值與HashMap的容量length-1做&運(yùn)算（因?yàn)槠淙萘渴?的n次方想诅，故length-1的二進(jìn)制一定是類似于 0111 1111 這樣的）召庞，&運(yùn)算的結(jié)果就是該key在table中的索引位置。
這里再補(bǔ)充一下来破，為什么不用取余操作來確定索引位置篮灼？
  --使用的位運(yùn)算，是非常高效的運(yùn)算徘禁。比取余快得多诅诱。且當(dāng)length為2^n時(shí)，hash & (length - 1) == hash % length晌坤。
至于是先有這樣的存儲過程的設(shè)計(jì)后決定容量是2的n次方逢艘，還是因?yàn)槿萘渴?的n次方而設(shè)計(jì)出了這種存儲方式。那就不得而知了骤菠。

4它改、關(guān)于HashMap中的hash()方法

static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
該處為什么要(h = key.hashCode()) ^ (h >>> 16)這么處理？
-- 因?yàn)檎Ｎ覀冊谑褂肏ashMap的時(shí)候商乎，map的容量其實(shí)不會太大央拖。正常都是小于2^16=65536的。
   這樣的話鹉戚，會導(dǎo)致一個(gè)問題鲜戒，就是每次key的hash值與map的容量在做&操作的時(shí)候（即上一個(gè)問題里說的存儲過程），
   基本都是hashcode的高16位都用不到抹凳，這樣可能會導(dǎo)致部分不夠均勻遏餐。
   于是，要合理的將高16位也參數(shù)計(jì)算赢底。故^ (h >>> 16)失都。
   這里之所以選擇異或操作，是因?yàn)楫惢虿僮鞯慕Y(jié)果是五五開的幸冻。而&跟|的話粹庞，會讓結(jié)果往1或者0偏。