jdk1.8中hashmap源碼分析

本文以JDK 1.8.0_131源代碼為例進行分析：

• jdk1.6到1.8中hashmap的變化
• hashmap的實作原理
• 數組大小及相關參數規定
• Hashmap的put方法實作
• Hashmap的get方法實作

jdk1.6到1.8中hashmap的變化

• JDK1.6，JDK1.7中，HashMap采用位桶+連結清單實作，即使用連結清單處理沖突，同一hash值的連結清單都存儲在一個連結清單裡。

  

• JDK1.8中，HashMap采用位桶+連結清單+紅黑樹實作，當連結清單長度超過門檻值（8）時，将連結清單轉換為紅黑樹，這樣大大減少了查找時間。

  

hashmap的實作原理

：采用的是“桶位”，即一個Node數組實作

Node節點的實作：主要包括了key、value以及key的哈希值和next指向一個節點。

數組大小及相關參數規定規定：

• 所有的預設值：

  預設的數組初始容量：16

  

  預設的最大容量：2的30次方

  

  預設的負載因子：0.75

  

  預設的連結清單轉紅黑樹的節點數門檻值：8

  

  Hashmap擴容的節點數門檻值threshold=capacity*load factor：

  

• 注意Hashmap中數組容量capacity的值總是2的n次方：

  當不是2的n次方時，會用下面的函數進行調整。

  

  >>>表示無符号右移，無論是正數還是負數，高位通通補0。經過5次向右位移後，n一定會變成000..00111..11類型,即前部分均為0，後部分均為1.是以傳回的調整後的容量為n+1，一定是2的n次方。

Hashmap的put方法實作：

說明：

• 代碼塊1：如果Node數組為空，則通過resize()函數建立一個長度為capacity的數組，并指派給table。

• 代碼塊2：找到key的hash值在數組中的位置為i,即該hash表的尋址方法為i=(n-1)&hash。如果table[i]==null，則直接為該數組new一個Node，并存儲key,value。

  (注意：此處的尋址方法很巧妙，實質上相當于是求hash%(n-1),但是位運算的效率更高。因為n總是 2 的倍數，假設

  hash=5,n=16, 那麼hash&n-1将得到5；如果hash=6,n=16,那麼hash&n-1将得到6……如果hash=15,n=16,那麼hash&n-1将得到15；但是當hash=16,n=16時，那麼hash&n -1将得到0了；當hash=17,n=16時，那麼hash&n -1将得到1了……這樣保證計算得到的索引值總是位于table數組的索引之内。)

• 代碼塊3：如果table[i]!=null，并且table[i].key與要插入的key相等，則e=table[i]，并通過代碼塊6直接更新table[i]的value。
• 代碼塊4：如果table[i].next所連接配接的是紅黑樹，則将key,value插入後面的紅黑樹。
• 代碼塊5：如果table[i].next所連接配接的不是紅黑樹，則說明table[i].next連接配接的是普通連結清單，則通過e=p.next,p=e,一直到p.next==null.再把要插入的key,value插入到p.next。相當于新節點插入到了連結清單的最後。
• 代碼塊7：通過size記錄hashmap中元素的個數，如果size>threshold,則利用resize()對table數組進行擴容。

  

  即，擴容過程為直接将table的capacity容量乘以2，并且門檻值threshold也乘2。

Hashmap的get方法實作：

說明：

• 代碼塊1：如果table數組(也稱為bucket桶)為null，或者資料的長度小于0，或者當對key的hash值進行尋址時，即i=(n-1)&hash，first=table[i],如果table[i]==null。則直接return

  null。

• 代碼塊2：如果table[i]的key值與需要查詢的目标key相等，則傳回table[i]。注意：此處table[i].hash與key的hash值相同，是以必須通過key的equal方法來判斷兩個key是否相等，是以在當key應用于hashmap時必須同時實作hashcode和equal兩個方法。
• 代碼塊3：如果table[i].next後面連結的是紅黑樹，則在紅黑樹中進行查找。
• 代碼塊4：如果table[i].next後面連結的是普通連結清單，則在該連結清單中進行周遊，并通過key的equal方法查找key相同的節點，并傳回。