本文為原創(chuàng)博文，轉載請注明出處，侵權必究！

      每個java程序員都知道，HashMap是java中最重要的集合類之一，也是找工作面試中非常常見的考點，因為HashMap的實現(xiàn)本身確實蘊含了很多精妙的代碼設計。

　　對于普通的程序員，可能僅僅能說出HashMap線程不安全，允許key、value為null，以及不要求線程安全時，效率上比HashTable要快一些。稍微好一些的，會對具體實現(xiàn)有過大概了解，能說出HashMap由數(shù)組+鏈表+RBT實現(xiàn)，并了解HashMap的擴容機制。但如果你真的有一個刨根問題的熱情，那么你肯定會想知道具體是如何一步步實現(xiàn)的。HashMap的源碼一共2000多行，很難在這里每一句都說明，但這篇文章會讓你透徹的理解到我們平時常用的幾個操作下，HashMap是如何工作的。

 　 要先提一下的是，我看過很多講解HashMap原理的文章，有一些講的非常好，但這些文章習慣于把源代碼和邏輯分析分開，導致出現(xiàn)了大段的文字講解代碼，閱讀起來有些吃力和枯燥。所以我想嘗試另一種風格，將更多的內(nèi)容寫進注釋里，可能看起來有些啰嗦，但對于一些新手的理解，應該會有好的效果。

 

  • HashMap結構

　  首先是了解HashMap的幾個核心成員變量（以下均為jdk源碼）：

平面設計培訓,網(wǎng)頁設計培訓,美工培訓,游戲開發(fā),動畫培訓

 1 　　transient Node<K,V>[] table;　　　　　　　 //HashMap的哈希桶數(shù)組，非常重要的存儲結構，用于存放表示鍵值對數(shù)據(jù)的Node元素。 2  3 　　transient Set<Map.Entry<K,V>> entrySet;  //HashMap將數(shù)據(jù)轉換成set的另一種存儲形式，這個變量主要用于迭代功能。 4  5 　　transient int size;　　　　　　　　　　　　　//HashMap中實際存在的Node數(shù)量，注意這個數(shù)量不等于table的長度，甚至可能大于它，因為在table的每個節(jié)點上是一個鏈表（或RBT）結構，可能不止有一個Node元素存在。 6  7 　　transient int modCount;　　　　　　　　　　 //HashMap的數(shù)據(jù)被修改的次數(shù)，這個變量用于迭代過程中的Fail-Fast機制，其存在的意義在于保證發(fā)生了線程安全問題時，能及時的發(fā)現(xiàn)（操作前備份的count和當前modCount不相等）并拋出異常終止操作。 8  9 　　int threshold;　　　　　　　　　　　　　　　　//HashMap的擴容閾值，在HashMap中存儲的Node鍵值對超過這個數(shù)量時，自動擴容容量為原來的二倍。10 11 　　final float loadFactor;　　　　　　　　　　　//HashMap的負載因子，可計算出當前table長度下的擴容閾值：threshold = loadFactor * table.length。

平面設計培訓,網(wǎng)頁設計培訓,美工培訓,游戲開發(fā),動畫培訓

 

　　顯然，HashMap的底層實現(xiàn)是基于一個Node的數(shù)組，那么Node是什么呢？在HashMap的內(nèi)部可以看見定義了這樣一個內(nèi)部類：

平面設計培訓,網(wǎng)頁設計培訓,美工培訓,游戲開發(fā),動畫培訓

 1 static class Node<K,V> implements Map.Entry<K,V> { 2 　　final int hash; 3 　　final K key; 4     V value; 5     Node<K,V> next; 6  7     Node(int hash, K key, V value, Node<K,V> next) { 8         this.hash = hash; 9         this.key = key;10         this.value = value;11         this.next = next;12     }13 14     public final K getKey()        { return key; }15     public final V getValue()      { return value; }16     public final String toString() { return key + "=" + value; }17 18     public final int hashCode() {19         return Objects.hashCode(key) ^ Objects.hashCode(value);20     }21 22     public final V setValue(V newValue) {23         V oldValue = value;24         value = newValue;25         return oldValue;26     }27 28     public final boolean equals(Object o) {29         if (o == this)30             return true;31         if (o instanceof Map.Entry) {32             Map.Entry<?,?> e = (Map.Entry<?,?>)o;33             if (Objects.equals(key, e.getKey()) &&34                 Objects.equals(value, e.getValue()))35                 return true;36         }37         return false;38     }39 }

平面設計培訓,網(wǎng)頁設計培訓,美工培訓,游戲開發(fā),動畫培訓

 

　　我們大體看一下這個內(nèi)部類就可以知道，它實現(xiàn)了Map.Entry接口。其內(nèi)部的變量含義也很明確，hash值、key\value對和實現(xiàn)鏈表和紅黑樹所需要的指針索引。

　　既然知道了HashMap的基本結構，那么這些變量的默認值都是多少呢？我們再看一下HashMap定義的一些常量：

平面設計培訓,網(wǎng)頁設計培訓,美工培訓,游戲開發(fā),動畫培訓

 　　　　           DEFAULT_INITIAL_CAPACITY = 1 << 4;                    MAXIMUM_CAPACITY = 1 << 30                    DEFAULT_LOAD_FACTOR = 0.75f                    TREEIFY_THRESHOLD = 8                    UNTREEIFY_THRESHOLD = 6                    MIN_TREEIFY_CAPACITY = 64;

平面設計培訓,網(wǎng)頁設計培訓,美工培訓,游戲開發(fā),動畫培訓

 

  • TIP : 在HashMap內(nèi)部定義的幾個變量，包括桶數(shù)組本身都是transient修飾的，這代表了他們無法被序列化，而HashMap本身是實現(xiàn)了Serializable接口的。這很容易產(chǎn)生疑惑：HashMap是如何序列化的呢？查了一下源碼發(fā)現(xiàn)，HashMap內(nèi)有兩個用于序列化的函數(shù) readObject(ObjectInputStream s) 和 writeObject（ObjectOutputStreams），通過這個函數(shù)將table序列化。

  •  HashMap 的 put 方法解析

　　以上就是我們對HashMap的初步認識，下面進入正題，看看HashMap是如何添加、查找與刪除數(shù)據(jù)的。

　　首先來看put方法，我盡量在每行都加注釋闡明這一行的含義，讓閱讀起來更容易理解。

平面設計培訓,網(wǎng)頁設計培訓,美工培訓,游戲開發(fā),動畫培訓

 1     public V put(K key, V value) { 2         return putVal(hash(key), key, value, false, true); 
 3     } 4  5 　　final V putVal(int hash, K key, V value, boolean onlyIfAbsent,  　　　　　　　　//這里onlyIfAbsent表示只有在該key對應原來的value為null的時候才插入，也就是說如果value之前存在了，就不會被新put的元素覆蓋。 6                    boolean evict) {                                              //evict參數(shù)用于LinkedHashMap中的尾部操作，這里沒有實際意義。 7         Node<K,V>[] tab; Node<K,V> p; int n, i;　　　　　　　　　　　　　　　　　　　　//定義變量tab是將要操作的Node數(shù)組引用，p表示tab上的某Node節(jié)點，n為tab的長度，i為tab的下標。 8         if ((tab = table) == null || (n = tab.length) == 0)　　　                 //判斷當table為null或者tab的長度為0時，即table尚未初始化，此時通過resize()方法得到初始化的table。             　　　　　　　　　　　 9             n = (tab = resize()).length;　　　　　　　　　　　　　　　　　　　　　　　　//這種情況是可能發(fā)生的，HashMap的注釋中提到：The table, initialized on first use, and resized as necessary。10         if ((p = tab[i = (n - 1) & hash]) == null)                               //此處通過（n - 1） & hash 計算出的值作為tab的下標i，并另p表示tab[i]，也就是該鏈表第一個節(jié)點的位置。并判斷p是否為null。11             tab[i] = newNode(hash, key, value, null);　　　　　　　　　　　　　　　　 //當p為null時，表明tab[i]上沒有任何元素，那么接下來就new第一個Node節(jié)點，調(diào)用newNode方法返回新節(jié)點賦值給tab[i]。12         else {　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　                //下面進入p不為null的情況，有三種情況：p為鏈表節(jié)點；p為紅黑樹節(jié)點；p是鏈表節(jié)點但長度為臨界長度TREEIFY_THRESHOLD，再插入任何元素就要變成紅黑樹了。13             Node<K,V> e; K k;　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 //定義e引用即將插入的Node節(jié)點，并且下文可以看出 k = p.key。14             if (p.hash == hash &&　　　　　　　　　　　　　　　　　　　　　　　　　　　　 //HashMap中判斷key相同的條件是key的hash相同，并且符合equals方法。這里判斷了p.key是否和插入的key相等，如果相等，則將p的引用賦給e。15                 ((k = p.key) == key || (key != null && key.equals(k))))           //這一步的判斷其實是屬于一種特殊情況，即HashMap中已經(jīng)存在了key，于是插入操作就不需要了，只要把原來的value覆蓋就可以了。16                 e = p;　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　  //這里為什么要把p賦值給e，而不是直接覆蓋原值呢？答案很簡單，現(xiàn)在我們只判斷了第一個節(jié)點，后面還可能出現(xiàn)key相同，所以需要在最后一并處理。17             else if (p instanceof TreeNode)                                       //現(xiàn)在開始了第一種情況，p是紅黑樹節(jié)點，那么肯定插入后仍然是紅黑樹節(jié)點，所以我們直接強制轉型p后調(diào)用TreeNode.putTreeVal方法，返回的引用賦給e。18                 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);   //你可能好奇，這里怎么不遍歷tree看看有沒有key相同的節(jié)點呢？其實，putTreeVal內(nèi)部進行了遍歷，存在相同hash時返回被覆蓋的TreeNode，否則返回null。19             else {　　　　　　　　　　　　       　　　　　　　　                       //接下里就是p為鏈表節(jié)點的情形，也就是上述說的另外兩類情況：插入后還是鏈表/插入后轉紅黑樹。另外，上行轉型代碼也說明了TreeNode是Node的一個子類。20                 for (int binCount = 0; ; ++binCount) {　　　　　　　　　　　　　　　　 //我們需要一個計數(shù)器來計算當前鏈表的元素個數(shù)，并遍歷鏈表，binCount就是這個計數(shù)器。21                     if ((e = p.next) == null) {　　　　　　　　　　　　　　　　　　　　 //遍歷過程中當發(fā)現(xiàn)p.next為null時，說明鏈表到頭了，直接在p的后面插入新的鏈表節(jié)點，即把新節(jié)點的引用賦給p.next，插入操作就完成了。注意此時e賦給p。22                         p.next = newNode(hash, key, value, null);　　　　　　　　　　//最后一個參數(shù)為新節(jié)點的next，這里傳入null，保證了新節(jié)點繼續(xù)為該鏈表的末端。23                         if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st 　　  //插入成功后，要判斷是否需要轉換為紅黑樹，因為插入后鏈表長度加1，而binCount并不包含新節(jié)點，所以判斷時要將臨界閾值減1。24                             treeifyBin(tab, hash);　　　　　　　　　　　　　　　　     //當新長度滿足轉換條件時，調(diào)用treeifyBin方法，將該鏈表轉換為紅黑樹。25                         break;　　　　　　　　　　　　　　　　　　　　　　　　　　　　　   //當然如果不滿足轉換條件，那么插入數(shù)據(jù)后結構也無需變動，所有插入操作也到此結束了，break退出即可。26                     }27                     if (e.hash == hash &&　　　　　　　　　　　　　　　　　　　　　　　　 //在遍歷鏈表的過程中，我之前提到了，有可能遍歷到與插入的key相同的節(jié)點，此時只要將這個節(jié)點引用賦值給e，最后通過e去把新的value覆蓋掉就可以了。28                         ((k = e.key) == key || (key != null && key.equals(k))))　　 //老樣子判斷當前遍歷的節(jié)點的key是否相同。29                         break;　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　  //找到了相同key的節(jié)點，那么插入操作也不需要了，直接break退出循環(huán)進行最后的value覆蓋操作。30                     p = e;　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 //在第21行我提到過，e是當前遍歷的節(jié)點p的下一個節(jié)點，p = e 就是依次遍歷鏈表的核心語句。每次循環(huán)時p都是下一個node節(jié)點。31                 }32             }33             if (e != null) { // existing mapping for key　　　　　　　　　　　　　　　　//左邊注釋為jdk自帶注釋，說的很明白了，針對已經(jīng)存在key的情況做處理。34                 V oldValue = e.value;　　　　　　　　　　　　　　　　　　　　　　　　　　　//定義oldValue，即原存在的節(jié)點e的value值。35                 if (!onlyIfAbsent || oldValue == null)　　　　　　　　　　　　　　　　　//前面提到，onlyIfAbsent表示存在key相同時不做覆蓋處理，這里作為判斷條件，可以看出當onlyIfAbsent為false或者oldValue為null時，進行覆蓋操作。36                     e.value = value;　　　　　　　　　　　　　　　　　　　　　　　　      //覆蓋操作，將原節(jié)點e上的value設置為插入的新value。37                 afterNodeAccess(e);　　　　　　　　　　　　　　　　　　　　　　　　　　　　//這個函數(shù)在hashmap中沒有任何操作，是個空函數(shù)，他存在主要是為了linkedHashMap的一些后續(xù)處理工作。38                 return oldValue;　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　//這里很有意思，他返回的是被覆蓋的oldValue。我們在使用put方法時很少用他的返回值，甚至忘了它的存在，這里我們知道，他返回的是被覆蓋的oldValue。39             }40         }　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 
41         ++modCount;　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 //收尾工作，值得一提的是，對key相同而覆蓋oldValue的情況，在前面已經(jīng)return，不會執(zhí)行這里，所以那一類情況不算數(shù)據(jù)結構變化，并不改變modCount值。42         if (++size > threshold)　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 //同理，覆蓋oldValue時顯然沒有新元素添加，除此之外都新增　

　　以上便是HashMap最常用API的源碼分析，除此之外，HashMap還有一些知識需要重點學習：擴容機制、并發(fā)安全問題、內(nèi)部紅黑樹的實現(xiàn)。這些內(nèi)容我也會在之后陸續(xù)發(fā)文分析，希望可以幫讀者徹底理解HashMap的原理。

http://www.cnblogs.com/jzb-blog/p/6637823.html