深入了解HashMap的底層原理

各位java開發(fā)的同學(xué)肯定對HashMap并不陌生，它是一種非常常見的數(shù)據(jù)結(jié)構(gòu)，可是大家真的對它十分了解嗎？知道它底層設(shè)計的原型和思路嗎？

• 什么是HashMap
  HashMap是一個存儲K-V鍵值對的集合，每一個鍵值對叫做Entry。這些鍵值對存儲在一個數(shù)組當(dāng)中，這個數(shù)組就是HashMap的主要組成部分。
  使用HashMap主要的方法有兩個Put()和Get()。
  1.Put方法的原理
  當(dāng)調(diào)用Put方法時需要使用Hash函數(shù)來確定Entry在數(shù)組中的位置（index）
  index=Hash("XX")
  假設(shè)index是0，則把“XX”放到數(shù)組的第一個位置上。
  但是如果隨著數(shù)據(jù)的不斷增多，就很容易出現(xiàn)相同的index，這樣就需要通過使用鏈表來解決index沖突的問題。因此HashMap數(shù)組的每一個元素既是一個Entry對象也是鏈表的頭節(jié)點。每一個Entry對象通過Next指針指向它的下一個Entry節(jié)點。這樣如果index再沖突的時候，只需要插入到對應(yīng)的鏈表下即可。
  2.Get方法原理
  使用Get方法時傳入key來獲取value時，同樣會使用Hash函數(shù)對key做一次hash映射，得到對應(yīng)的index，通過index去數(shù)組對應(yīng)的位置上取第一個值和key做比較，如果不是想要的key則順著鏈表取下一個值，直到得到正確的結(jié)果。

• 為什么老是說HashMap是線程不安全的
  HashMap的容量是有限的，在經(jīng)過多次元素的插入后，key的hash映射發(fā)生沖突的幾率就逐漸提高。這個時候就需要擴展HashMap的長度，也就是進(jìn)行Resize。
  Resize的步驟
  1.擴容
  擴容就是創(chuàng)建一個新的Entry空數(shù)組，長度是原來數(shù)組的兩倍。
  2.ReHash
  ReHash的時候會首先遍歷原來的數(shù)組，把原來數(shù)組所有的Entry重新Hash到新的數(shù)組中。為啥需要把以前的Entry重新Hash一遍呢，因為在數(shù)組的長度增加后，Hash的規(guī)則也相應(yīng)發(fā)生變化。
  此時如果此HashMap達(dá)到了Resize的臨界值，而同時有多個線程在對此HashMap做插入操作時就有可能使HashMap的鏈表出現(xiàn)環(huán)形鏈表，程序就會進(jìn)入死循環(huán)（具體出現(xiàn)環(huán)形鏈表的條件比較苛刻，而且流程非常燒腦）。

• 線程安全的ConcurrentHashMap
  ConcurrentHashMap是HashMap的升級版，同時兼顧了線程安全和運行的效率。
  ConcurrentHashMap的設(shè)計包含了一個非常重要的數(shù)據(jù)結(jié)構(gòu)Segment
  1.什么是Segment
  Segment本身就是一個HashMap對象，Segment包含一個HashEntry數(shù)組，數(shù)組中的每一個HashEntry既是一個鍵值對，也是鏈表的頭結(jié)點。
  2.ConcurrentHashMap設(shè)計的好處
  每一個Segment都相當(dāng)于一個自治區(qū)，讀和寫高度自治，每一個Segment之間互不影響。每一個Segment的寫入是上鎖的，因此對同一個Segment的并發(fā)寫入會被阻塞。這樣既保證了線程安全又降低了鎖的粒度，使并發(fā)操作的效率更高。
  3.ConcurrentHashMap具體的讀寫流程
  Get()方法
  （1）：為輸入的Key做Hash運算，得到hash值。
  （2）：通過hash值，定位到對應(yīng)的Segment對象。
  （3）：再次通過hash值，定位到Segment當(dāng)中數(shù)組的具體位置。
  Put()方法
  （1）：為輸入的Key做Hash運算，得到hash值。
  （2）：通過hash值，定位到對應(yīng)的Segment對象
  （3）：再次通過hash值，定位到Segment當(dāng)中數(shù)組的具體位置。
  （4）：插入或覆蓋HashEntry對象。
  （5）：釋放鎖。