JAVA基礎之HashMap源碼（JDK 1.8）

這段時間一直想研究一下hashmap的源碼，由于實習生的筆試、面試這些事，感覺把自己所有的複習計劃都打亂了，最後的結果也很慘，是以決定好好地靜下來認真的把基礎鞏固好。

我電腦裡裝的是JDK1.8，JDK1.8相比于JDK1.6的版本在hashmap的實作上面做了一些比較大的改動。

1. JDK1.6實作hashmap的方式是采用位桶+連結清單的方式，即散列連結清單方式
2. JDK1.8則是采用位桶+連結清單/紅黑叔的方式，即當某個位桶的連結清單長度達到某個門檻值的時候，這個連結清單就轉化成紅黑樹。
   1. 當位桶采用散列連結清單存儲時：

      

JAVA代碼：

//位桶的聲明
    transient Node<K,V>[] table;

    /**
     * Holds cached entrySet(). Note that AbstractMap fields are used
     * for keySet() and values().
     */
    transient Set<Map.Entry<K,V>> entrySet;
    //連結清單以及數組裡存放的基本的資料結構
    static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;
        ...
    }
           

hashMap的get（Object key）方法

public V get(Object key) {
        Node<K,V> e;
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }

    static final int hash(Object key) {
        int h;
        //key.hashCode()如果沒有重寫則是獲得key的記憶體位址
        return (key == null) ?  : (h = key.hashCode()) ^ (h >>> );
    }

    final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        if ((tab = table) != null && (n = tab.length) >  &&
            (first = tab[(n - ) & hash]) != null) {//通過(n-1)&hash定位原因下面說明
            if (first.hash == hash && // 總是先檢查第一個元素
            //當hash值一樣之後，通過key.equals(k)來對連結清單進行搜尋，若沒有重寫k類的equals方法，則直接預設調用Object的方法，直接判斷兩個key的記憶體位址是否相等
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            if ((e = first.next) != null) {
                if (first instanceof TreeNode)//判斷這個位桶的連結清單已經轉化成紅黑樹，稍後再細講
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                do {//如果沒有，則周遊連結清單尋找key值相同的節點
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }
           

1. hash算法

   我們可以看到在hashmap中要找到某個元素，需要根據key的hash值來求得在數組中的位置，如何計算這個位置就是hash算法。前面說過hashmap的資料結構是數組和連結清單的結合，是以我們希望這個hashmap裡面的元素位置盡量分布的均勻些盡量使得每個位置上的元素隻有一個，那麼當我們用hash算法求得這個位置的時候，馬上就可以知道對應位置上的元素就是我們要的，而不用再去周遊連結清單。

   是以我們首先想到的是把hashcode對數組長度進行取模運算，這樣一來，元素的分布相對來說是比較均勻的。但是，取模運算的消耗還是比較大的，能不能找一種更快速，消耗更小的方式呢？JAVA中是這樣做的： (n - 1) & hash

   首先計算得key的hashcode值，然後和數組的長度-1做一次“與”運算（&）。看上去很簡單，其實比較有玄機，數組的長度一般為2的幂次方，然而，為什麼hashmap的容量為2的次方大小時，hashmap的效率最高，下面以2的4次方舉例，來解釋一下為什麼數組大小為2的幂次時性能最高。

   看下圖，左邊兩組是數組長度為16（2的4次方），右邊兩組是數組長度為15。兩組的hashcode均為8和9，但是很明顯，當它們和1110“與”的時候，産生了相同的結果，也就是說它們會定位到數組中的同一個位置上去，這就産生了碰撞，8和9會被放到同一個連結清單上，那麼查詢的時候就需要周遊這個連結清單，得到8或者9，這樣就降低了查詢的效率。同時，我們也可以發現，當數組長度為15的時候，hashcode的值會與14（1110）進行“與”，那麼最後一位永遠是0，而0001，0011，0101，1001，1011，0111，1101這幾個位置永遠都不能存放元素了，空間浪費相當大，更糟的是這種情況中，數組可以使用的位置比數組長度小了很多，這意味着進一步增加了碰撞的幾率，減慢了查詢的效率！

   

   是以說，當數組長度為2的n次幂的時候，不同的key算得得index相同的幾率較小，那麼資料在數組上分布就比較均勻，也就是說碰撞的幾率小，相對的，查詢的時候就不用周遊某個位置上的連結清單，這樣查詢效率也就較高了。

   說到這裡，我們再回頭看一下hashmap中預設的數組大小是多少，檢視源代碼可以得知是16，為什麼是16，而不是15，也不是20呢，看到上面annegu的解釋之後我們就清楚了吧，顯然是因為16是2的整數次幂的原因，在小資料量的情況下16比15和20更能減少key之間的碰撞，而加快查詢的效率。

   是以，在存儲大容量資料的時候，最好預先指定hashmap的size為2的整數次幂次方。就算不指定的話，也會以大于且最接近指定值大小的2次幂來初始化的

   1. hashmap的resize方法

      當hashmap中的元素越來越多的時候，碰撞的幾率也就越來越高（因為數組的長度是固定的），是以為了提高查詢的效率，就要對hashmap的數組進行擴容，數組擴容這個操作也會出現在ArrayList中，是以這是一個通用的操作，很多人對它的性能表示過懷疑，不過想想我們的“均攤”原理，就釋然了，而在hashmap數組擴容之後，最消耗性能的點就出現了：原數組中的資料必須重新計算其在新數組中的位置，并放進去，這就是resize。

      那麼hashmap什麼時候進行擴容呢？當hashmap中的元素個數超過數組大小*loadFactor時，就會進行數組擴容，loadFactor的預設值為0.75，也就是說，預設情況下，數組大小為16，那麼當hashmap中元素個數超過16*0.75=12的時候，就把數組的大小擴充為2*16=32，即擴大一倍，然後重新計算每個元素在數組中的位置，而這是一個非常消耗性能的操作，是以如果我們已經預知hashmap中元素的個數，那麼預設元素的個數能夠有效的提高hashmap的性能。

      比如說，我們有1000個元素new HashMap(1000), 但是理論上來講new HashMap(1024)更合适，不過上面已經說過，即使是1000，hashmap也自動會将其設定為1024。 但是new HashMap(1024)還不是更合适的，因為0.75*1000 < 1000, 也就是說為了讓0.75 * size > 1000, 我們必須這樣new HashMap(2048)才最合适，既考慮了&的問題，也避免了resize的問題。

   2. key的hashcode與equals方法改寫

      在第一部分hashmap的資料結構中，annegu就寫了get方法的過程：首先計算key的hashcode，找到數組中對應位置的某一進制素，然後通過key的equals方法在對應位置的連結清單中找到需要的元素。是以，hashcode與equals方法對于找到對應元素是兩個關鍵方法。

      Hashmap的key可以是任何類型的對象，例如User這種對象，為了保證兩個具有相同屬性的user的hashcode相同，我們就需要改寫hashcode方法，比方把hashcode值的計算與User對象的id關聯起來，那麼隻要user對象擁有相同id，那麼他們的hashcode也能保持一緻了，這樣就可以找到在hashmap數組中的位置了。如果這個位置上有多個元素，還需要用key的equals方法在對應位置的連結清單中找到需要的元素，是以隻改寫了hashcode方法是不夠的，equals方法也是需要改寫滴~當然啦，按正常思維邏輯，equals方法一般都會根據實際的業務内容來定義，例如根據user對象的id來判斷兩個user是否相等。

      在改寫equals方法的時候，需要滿足以下三點：

      (1) 自反性：就是說a.equals(a)必須為true。

      (2) 對稱性：就是說a.equals(b)=true的話，b.equals(a)也必須為true。

      (3) 傳遞性：就是說a.equals(b)=true，并且b.equals(c)=true的話，a.equals(c)也必須為true。

      通過改寫key對象的equals和hashcode方法，我們可以将任意的業務對象作為map的key(前提是你确實有這樣的需要)。

   本文主要描述了HashMap的結構，和hashmap中hash函數的實作，以及該實作的特性，同時描述了hashmap中resize帶來性能消耗的根本原因，以及将普通的域模型對象作為key的基本要求。尤其是hash函數的實作，可以說是整個HashMap的精髓所在，隻有真正了解了這個hash函數，才可以說對HashMap有了一定的了解。