Java集合中設計了一個介面Java.util.Map，它實作類中hashMap、hashTable、TreeMap、ConcurrentHashMap、LinkedHashMap，
Map型別的集合用來做鍵值對存盤的，也就是key-value形式的，所以不允許鍵重復，值是可以重復的，

hashMap

hashMap 底層結構是：陣列+鏈表+紅黑樹（jdk1.8之前就是存盤的陣列+鏈表）

說明：

 陣列的特點：查詢效率高，插入，洗掉效率低，
 鏈表的特點：查詢效率低，插入洗掉效率高，
 在HashMap底層使用陣列加（鏈表+紅黑樹）的結構完美的解決了陣列和鏈表的問題，使得查詢和插入，洗掉的效率都很高，
 當鏈表的長度達到某個閥值（8）的時候，這個鏈表就將轉換成紅黑樹，
 洗掉的時候可能導致紅黑樹轉換為鏈表
 擴容也可能導致紅黑樹轉化為鏈表 擴容有可能導致紅黑樹拆成兩部分, 在這兩部分中, 任意部分, 如果元素數量是小于等于6的話, 會由紅黑樹轉化為鏈表，
 在jdk1.8中，如果鏈表長度大于8且節點陣列長度大于64的時候，就把鏈表下所有的節點轉為紅黑樹，樹形化還有一個要求就是陣列長度必須大于等于64，否則繼續采用擴容策略

默認初始容量16, 負載因子0.75,擴容機制是原容量的2倍，且要求容量一定為2的整數次冪

說明：用陣列容量大小乘以負載因子得到一個值，當陣列中存盤的元素個數超過該值就會呼叫rehash方法將陣列容量增加到原來的兩倍，在擴容的時候會生成一個新的陣列，原來的所有資料需要重新計算哈希碼值重新分配到新的陣列，所以擴容的操作非常消耗性能.
無序的，允許存null（鍵，值），執行緒不安全的，可以使用 Collections的synchronizedMap方法保證安全，
存盤程序
說明：存盤資料時計算Key的hashCode值再%陣列的長度得到對應的陣列下標，如果這個下標沒有值就直接存入，如果有值就會計算euqals()的值是不是相等，相等就覆寫，不相等就往下鏈，鏈的太多時會轉換為紅黑樹，

LinkedHashMap

LinkedHashMap是HashMap一個子類，基本完全復用和遵從HashMap的特點
LinkedHashMap在HashMap的基礎上維護了一個雙向鏈表，意味著他是有序的，

TreeMap

TreeMap它是基于紅黑樹的NavigableMap實作，（樹中的每個節點的值都會大于或等于它的左子樹中的所有節點的值，并且小于或等于它的右子樹中的所有節點的值），實作了SortMap介面，能夠對保存的記錄根據鍵進行排序，
不允許NULL（鍵，值），執行緒不安全的
在TreeMap中存盤資料時, key-value, 我們可以有兩種方式：一個就是讓key本身可以比較(繼承Comparable介面實作compareTo) 另一個就是可以在創建TreeMap的時候手動提供一個比較器

HashTable

無序，執行緒安全的(幾乎所有的方法都加鎖)，不能存盤null值，null鍵
底層結構是陣列+鏈表
默認初始容量11，擴容時2倍+1，且不要求底層陣列的容量一定要為2的整數次冪；

ConcurrentHashMap

ConcurrentHashMap 是執行緒安全的，相比較HashTable，jdk1.8之前ConcurrentHashMap是分段鎖（Segment），繼承了ReentrantLock，jdk1.8開始執行緒安全性由synchronized 和 CAS 來保證，
ConcurrentHashMap可以一邊更新、一邊遍歷，也就是說在遍歷的時候，ConcurrentHashMap也可以進行remove,put操作，且遍歷的資料會隨著remove,put操作產生變化，HashTable會拋例外，
get方法沒有加鎖，remove put是要加鎖的，
說明：jdk1.8之前是分段鎖，一般不會出現鎖的爭搶，jdk1.8開始分的更細了，使用cas機制添加到樹的頭節點，如果失敗了，說明有其他執行緒在操作，那就再次回圈上一步添加操作，如果頭節點已經存在了，通過synchronized獲得頭節點鎖，進行后續的操作，

總結

平常使用HashMap，訪問速度快，效率高，
有排序需求的，并且需要自定義排序規則的使用TreeMap，
有執行緒安全并發的需求時考慮使用ConcurrentHashMap，
需要快速增刪改查而且需要保證遍歷和插入順序一致的存盤功能 LinkedHashMap，

補充

二叉樹
特點：左子節點的值小于父節點，右子節點的值大于父子節點，當有序串列時，會變成鏈表結構
平衡二叉樹 AVL
特點：和二叉樹唯一不同的就是左子節點和右子節點的高度差最多等于1，
紅黑樹
特點：通過左旋或者右旋維持樹的平衡，因為AVL太嚴格，當樹的節點發生變化時會破壞平衡，

轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/461830.html

標籤：Java

上一篇：京東一面：子執行緒如何獲取父執行緒 ThreadLocal 的值？我蒙了。。。

下一篇：java學習之socket編程

hashMap、ConcurrentHashMap、hashTable、TreeMap、LinkedHashMap用法區別詳解

hashMap

LinkedHashMap

TreeMap

HashTable

ConcurrentHashMap

總結

補充