Java集合中設計了一個介面Java.util.Map，它實現類中hashMap、hashTable、TreeMap、ConcurrentHashMap、LinkedHashMap。 Map類型的集合用來做鍵值對存儲的，也就是key-value形式的。所以不允許鍵重覆，值是可以重覆的。 hashMa ...
- 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太嚴格，當樹的節點發生變化時會破壞平衡。
