前言

Java現(xiàn)在的市場占用率有目共睹愚隧，為(ying)了(fu)學(mian)好(shi)Java海蔽，Java的一些底層知識不得不了解锥咸，與其需要的時候東一錘撼嗓，西一刀到處找柬采，這里總結(jié)一下，以備不時之需且警。相關圖片和詳細資料都可以在參考文章下的源文章中找到粉捻。

HashMap

HashMap.png

HashMap是數(shù)組和鏈表的組合。HashMap的高性能依賴數(shù)組斑芜，鏈表是為了處理哈希沖突肩刃。HashMap通過對Key的hashCode()進行哈希擾亂(hash())，進一步與數(shù)組lenght-1進行&運算，最終通過indexFor()決定具體的地址盈包。

常規(guī)狀態(tài)下沸呐，HashMap的尋址時間復雜度為O(1)⌒铮可是哈希函數(shù)不能保證計算出來的地址是唯一的垂谢，也就是說，會存在多個不同的Key疮茄，指向同一個地址滥朱，這被成為哈希沖突(碰撞)。這時通過鏈表將指向同位置的數(shù)據(jù)鏈接力试，對于這個位置的數(shù)據(jù)徙邻，通過Key的equals()進行匹配，尋址時間復雜度可以認為為O(n)畸裳，n為該位置鏈表長度缰犁。所以，HashMap中鏈表越少越短怖糊，其性能越高帅容。

HashMap存在容量(Capacity，默認16)與負載因子(loadFactor伍伤，默認0.75)并徘，容量指數(shù)組的長度，也是HashMap中允許存放的數(shù)據(jù)量扰魂，負載因子指數(shù)據(jù)占比麦乞。負載因子的存在是為了減少哈希沖突，我們可以理解為劝评，數(shù)據(jù)量越接近最大負載姐直，越容易發(fā)生哈希碰撞。當數(shù)據(jù)占位比達到負載上限蒋畜，需要進行擴容声畏。每次擴容即將當前容量翻倍，這樣可以保證數(shù)據(jù)在搬運到數(shù)組中時姻成，hash與length-1進行與運算出來的下標保持不變插龄。所以，HashMap的容量永遠是2的指數(shù)冪佣渴。

線程不安全，在JDK1.7中初斑，多線程同時擴容時辛润，執(zhí)行到resize中的transfer方法重新散列table，散列元素為從頭插入(頭插法)，最終形成環(huán)形鏈表砂竖，下一次調(diào)用get方法或put方法遍歷這個Hash數(shù)組的位置的鏈表真椿，如果元素key不存在，就在這個循環(huán)鏈表中無限循環(huán)遍歷了乎澄，因為不存在尾結(jié)點的指針域為null停止循環(huán)遍歷了突硝。在JDK1.8中，通過尾插法置济，在resize時保持原來鏈表元素的順序解恰，避免循環(huán)鏈表的bug。HashMap線程不安全的問題還有很多浙于，比如多線程resize時护盈，put會出現(xiàn)原來數(shù)據(jù)節(jié)點的丟失；一個線程通過迭代器遍歷或刪除時羞酗，另一個線程修改了HashMap腐宋，則modCount++，造成迭代器中的expectedModCount與HashMap中的modCount不一樣檀轨，拋出ConcurrentModificationException異常等等原因胸竞。所以，HashMap就是設計給單線程作業(yè)的参萄，多線程要么二次通過并發(fā)封裝卫枝，要么使用HashTable或ConCurrentHashMap等線程安全的集合。

JDK1.8優(yōu)化HashMap拧揽，轉(zhuǎn)鏈表為紅黑樹剃盾。無論什么樣的哈希函數(shù)，都無法避免哈希碰撞的問題淤袜，為此JDK1.8在JDK1.7的基礎上對原來的鏈表結(jié)構(gòu)進行了優(yōu)化痒谴。當鏈表長度超過8時，將鏈表轉(zhuǎn)化為紅黑樹铡羡，紅黑樹的時間復雜度為O(lgn)积蔚，可以有效提升HashMap的查找性能。

HashMap put方法邏輯圖(JDK1.8).png

HashMap知識點：

• 數(shù)組鏈表組合；
• 容量總是2的指數(shù)冪夭委；
• 紅黑樹優(yōu)化幅狮；
• 非線程安全；
• 無序

note*:哈希沖突解決方案，開放定址法(發(fā)生沖突崇摄，繼續(xù)尋找下一塊未被占用的存儲地址)擎值、再散列函數(shù)法、鏈地址法(數(shù)組+鏈表)等逐抑。

TreeMap

TreeMap基于紅黑樹實現(xiàn)鸠儿，所以其增查改刪的復雜度也是O(lgn)。雖然比起HashMap來說厕氨，其性能有所缺憾进每，但是，在類結(jié)構(gòu)上腐巢，TreeMap實現(xiàn)了SortedMap接口品追，允許通過默認或者自定義的Comparator進行排序，實現(xiàn)有序的Map冯丙。默認的順序與常規(guī)的List不同肉瓦，不是添加順序，而是通過Key的排列順序排序的胃惜。TreeMap中也沒有對線程安全做相關的處理泞莉，也會出現(xiàn)數(shù)據(jù)丟失、數(shù)據(jù)同步異常等問題船殉，所以TreeMap也是線程不安全的鲫趁。

TreeMap知識點：

• 紅黑樹；
• 非線程安全利虫；
• 有序

HashTable

HashTable是比較老的Hash集合挨厚，現(xiàn)在基本不用了。基本實現(xiàn)與HashMap相同糠惫，由于保障線程安全的原因疫剃，為一些特別的方法加上了synchronized(函數(shù)級synchronized)，在多進程的情況下硼讽，同時只允許一個進程訪問該方法巢价，所以性能上稍差。由于synchronized的原因固阁，HashTable的操作在多線程下會變成串行壤躲，數(shù)量多了就會造成阻塞，因此备燃，由于其是直接在方法上加入synchronized控制并發(fā)碉克，所以阻塞的概率還是比較大的。但是并齐，因為這種大段串行競爭鎖的機制漏麦，每次都是鎖住整個表法瑟，HashMap能反映最近的數(shù)據(jù)更新，更保險唁奢。當前，一般是通過HashMap并發(fā)包裝窝剖，或者ConcurrentHashMap在多線程下保證線程安全麻掸。
HashTable知識點：

• 線程安全；
• 串行赐纱；
• 阻塞脊奋；

ConcurrentHashMap

ConcurrentHashMap是為了兼顧性能和線程安全而存在的。ConcurrentHashMap也有HashMap疙描，因為在數(shù)據(jù)處理上使用了相同的方法诚隙，數(shù)組-鏈表-[紅黑樹]，所以保證了效率起胰。但是它又是線程安全的久又，因為它在處理的通過synchronized來保障數(shù)據(jù)同步。但是它的效率又高于HashTable效五，因為使用了分段鎖技術地消，對HashMap的數(shù)據(jù)單元Node的數(shù)據(jù)結(jié)構(gòu)進行了調(diào)整，并將鎖細粒度化畏妖，從而實線分段鎖脉执，提升了線程安全下的性能。

JDK1.7中戒劫，通過Segment實現(xiàn)分段鎖半夷。ConcurrentHashMap由多個Segment組成，每個Segment下維護一個HashEntry數(shù)組迅细，這個數(shù)組的結(jié)構(gòu)就和HashMap一樣了巫橄，每次操作時，鎖住數(shù)據(jù)對應的Segment疯攒，實現(xiàn)數(shù)據(jù)安全嗦随，比起HashTable鎖住整個表，效率提升了很多敬尺。

JDK1.8中枚尼，通過CAS+Synchronized來保證并發(fā)更新的安全。CAS是樂觀鎖的一種實現(xiàn)砂吞，讀取無所謂署恍，在數(shù)據(jù)更新時，通過compareAndSwap蜻直，保障數(shù)據(jù)安全盯质。1.8中舍棄了Segment袁串，數(shù)據(jù)結(jié)構(gòu)與1.8的HashMap差不多，將鎖的粒度從之前的Segment呼巷，細粒度到Node囱修。如果當前操作的Node為NULL，CAS保證原子性王悍，非空破镰，synchronized上鎖當前位置鏈表頭或紅黑樹根節(jié)點，這樣的結(jié)合方式可以有效提升并發(fā)操作效率压储。

ConcurrentHashMap的數(shù)據(jù)的弱一致鲜漩。ConcurrentHashMap通過volatile保證Node數(shù)組對多線程的可見性，這樣get時集惋，就總能得到真實的數(shù)據(jù)孕似。當?shù)鱥terator創(chuàng)建后，數(shù)據(jù)再發(fā)生改變刮刑，不會將操作直接作用到原始數(shù)據(jù)上喉祭，而是new新的數(shù)據(jù)，當iterator完成后再將修改作用到原始數(shù)據(jù)上雷绢，所以CocurrentHashMap不能及時的反應數(shù)據(jù)的更新臂拓。這保證了多個線程并發(fā)執(zhí)行的連續(xù)性和擴展性，是性能提升的關鍵习寸，是一致性與效率之間的一種權(quán)衡胶惰。

ConcurrentHashMap知識點：

• 線程安全；
• 分段鎖霞溪；
• CAS+Synchronized

參考文章

深入淺出學Java——HashMap
java遍歷TreeMap元素順序不是添加的順序問題
JAVA學習-紅黑樹詳解
JDK1.8 HashMap和TreeMap區(qū)別,讀懂這一篇就夠了
紅黑樹時間復雜度證明(O(lgn))
Java 集合系列12之 TreeMap詳細介紹(源碼解析)和使用示例
HashMap 和 HashTable 區(qū)別
Java基礎之ConcurrentHashMap
JAVA7與JAVA8中的HASHMAP和CONCURRENTHASHMAP知識點總結(jié)