談談HashMap原始碼中的優雅設計

一、HashMap構造器
HashMap總共給我們提供了三個構造器來創建HashMap物件，
1.無參建構式public HashMap()：使用無參建構式創建的hashmap物件，其默認容量為16，默認的負載因子為0.75，
2.有參建構式public HashMap(int initialCapacity，float loadFactor)：使用該建構式，我們可以指定hashmap的初始化容量和負載因子，但是在hashmap底層不一定會初始化成我們傳入的容量，而是會初始化成大于等于傳入值的最小的2的冪次方，比如我們傳入的是17，那么hashmap會初始化成32（2^5），那么hashmap是如何高效計算大于等于一個數的最小2的冪次方數的呢，原始碼如下：

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

它的設計可以說很巧妙，其基本思想是如果一個二進制數低位全是1，那么這個數+1則肯定是一個2的冪次方數，舉個例子看一下：

可以看到，它的計算程序是：首先將我們指定的那個數cap減1（減1的原因是，如果cap正好是一個2的冪次方數，也可以正確計算），然后對cap-1分別無符號右移1位、2位，4位、8位、16位(加起來正好是31位)，并且每次移位后都與上一個數做按位或運算，通過這樣的運算，會使得最終的結果低位都是1，那么最終對結果加1，就會得到一個2的冪次方數，
3.另一個有參建構式就是有參建構式public HashMap(int initialCapacity),該建構式和上一個建構式唯一不同之處就是不能指定負載因子，

二、HashMap插入機制
1.插入方法原始碼

public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        // 初始化桶陣列 table， table 被延遲到插入新資料時再進行初始化
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        // 如果桶中不包含鍵值對節點參考，說明當前陣列下標下不存在任何資料，則將新鍵值對節點的參考存入桶中即可
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            //如果hash相等，并且equals方法回傳true，這說明key相同，此時直接替換value即可，并且回傳原值
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
             //如果第一個節點是樹節點，則呼叫putTreeVal方法，將當前值放入紅黑樹中
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
               //如果第一個節點不是樹節點，則說明還是鏈表節點，則開始遍歷鏈表，將值存盤到鏈表合適的位置
                for (int binCount = 0; ; ++binCount) {
                     //如果遍歷到了鏈接末尾，則創建鏈表節點，將資料存盤到鏈表結尾
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        //判斷鏈表中節點樹是否超多了閾值8，如果超過了則將鏈表轉換為紅黑樹（當然不一定會轉換，treeifyBin方法中還有判斷）
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    //如果在鏈表中找到，完全相同的key，則直接替換value
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            //e!=null說明只是遍歷到中間就break了，該種情況就是在鏈表中找到了完全相等的key,該if塊中就是對value的替換操作
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        //加入value之后，更新size，如果超過閾值，則進行擴容
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

2.插入流程圖

（1）在put一個k-v時，首先呼叫hash()方法來計算key的hashcode,而在hashmap中并不是簡單的呼叫key的hashcode求出一個哈希碼，還用到了擾動函式來降低哈希沖突，原始碼如下：

static final int hash(Object key) {
     int h;
     return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
 }

從原始碼中可以看到，最終的哈希值是將原哈希碼和原哈希碼右移16位得到的值進行異或運算的結果， 16正好是32的一半，因此hashmap是將hashcode的高位移動到了低位，再通過異或運算將高位散播的低位，從而降低哈希沖突，至于為什么能夠降低沖突呢，我們可以看看作者對hash方法的注釋：

Computes key.hashCode() and spreads (XORs) higher bits of hash to lower. Because the table uses power-of-two masking, sets of hashes that vary only in bits above the current mask will always collide. (Among known examples are sets of Float keys holding consecutive whole numbers in small tables.) So we apply a transform that spreads the impact of higher bits downward. There is a tradeoff between speed, utility, and quality of bit-spreading. Because many common sets of hashes are already reasonably distributed (so don’t benefit from spreading), and because we use trees to handle large sets of collisions in bins, we just XOR some shifted bits in the cheapest possible way to reduce systematic lossage, as well as to incorporate impact of the highest bits that would otherwise never be used in index calculations because of table bounds.

從注釋中我們可以得出，作者進行高位向低位散播的原因是：由于hashmap在計算bucket下標時，計算方法為hash&n-1,n是一個2的冪次方數，因此hash&n-1正好取出了hash的低位，比如n是16，那么hash&n-1取出的是hash的低四位，那么如果多個hash的低四位正好完全相等，這就導致了always collide（沖突），即使hash不同，因此將高位向低位散播，讓高位也參與到計算中，從而降低沖突，讓資料存盤的更加散列，

（2）在計算出hash之后之后，呼叫putVal方法進行key-value的存盤操作，在putVal方法中首先需要判斷table是否被初始化了（因為hashmap是延遲初始化的，并不會在創建物件的時候初始化table），如果table還沒有初始化，則通過resize方法進行擴容，

if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;

（3）通過(n-1)&hash計算出當前key所在的bucket下標，如果當前table中當前下標中還沒有存盤資料，則創建一個鏈表節點直接將當前k-v存盤在該下標的位置，

if ((p = tab[i = (n - 1) & hash]) == null)
     tab[i] = newNode(hash, key, value, null);

（4）如果table下標處已經存在資料，則首先判斷當前key是否和下標處存盤的key完全相等，如果相等則直接替換value，并將原有value回傳，否則繼續遍歷鏈表或者存盤到紅黑樹，

if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))
      e = p;

（5）當前下標處的節點是樹節點，則直接存盤到紅黑樹中

else if (p instanceof TreeNode)
         e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);

（6）如果不是紅黑樹，則遍歷鏈表，如果在遍歷鏈表的程序中，找到相等的key，則替換value，如果沒有相等的key，就將節點存盤到鏈表尾部（jdk8中采用的是尾插法），并檢查當前鏈表中的節點樹是否超過了閾值8，如果超過了8，則通過呼叫treeifyBin方法將鏈表轉化為紅黑樹，

              for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }

（7）將資料存盤完成之后，需要判斷當前hashmap的大小是否超過擴容閾值Cap*load_fact,如果大于閾值，則呼叫resize()方法進行擴容，

f (++size > threshold)
       resize();

HashMap在擴容后的容量為原容量的2倍，起基本機制是創建一個2倍容量的table，然后將資料轉存到新的散串列中，并回傳新的散串列，和jdk1.7中不同的是，jdk1.8中多轉存進行了優化，可以不再需要重新計算bucket下標，其實作原始碼如下：

從原始碼中我們可以看出，如果一個key hash和原容量oldCap按位與運算結果為0，則擴容前的bucket下標和擴容后的bucket下標相等，否則擴容后的bucket下標是原下標加上oldCap，使用的基本原理總結如下：

1、如果一個數m和一個2的冪次方數n進行按位與運算不等于0，則有：m&(n2-1)=m&(n-1)+n
理解：一個2的冪次方數n，在二進制中只有一位為1（假設第k位是1），其他位均為0，那個如果一個數m和n進行按位與運算結果為0的話，則說明m的二進制第k位肯定為0，那么m的前n位和前n-1位所表示的值肯定是相等的，
2、如果一個數m和一個2的冪次方數n進行按位與運算等于0，則有：m&(n2-1)=m&(n-1)
理解：一個2的冪次方數n，在二進制中只有一位為1（假設第k位是1），其他位均為0，那個如果一個數m和n進行按位與運算結果不為0的話，則說明m的二進制第k位肯定為1，那么m的前n位和前n-1位所表示的值的差恰好是第k位上的1所表示的數，二這個數正好是n，

原理圖：