JDK容器學習之Map : HashMap,TreeMap,LinkedHashMap對比

​

​HashMap​

​​, ​

​TreeMap​

​​, ​

​LinkedHashMap​

​ 對比

1. 存儲結構

HashMap 存儲結構： 數組 + 連結清單 + 紅黑樹

LinkedHashMap 存儲結構 和HashMap 相同，差別是維護一個根據插入順序保持的雙向連結清單

TreeMap 存儲結構: 紅黑樹

2. 是否有序

HashMap 無序

LinkedHashMap 根據插入先後順序确定周遊順序

TreeMap 有序，根據Key進行比較擷取先後順序

3. 疊代

HashMap 疊代

• 從頭開始周遊數組
• 若數組中該索引處為null，或者Node的next指向null，則掃描數組的下一位
• 若數組中該索引處非null，切Node的next指向另一個Node，則依次掃描Node的next元素，直到為null

示意圖如下：

LinkedHashMap 疊代

• 掃描内部的雙向連結清單
• 從head指向的Node節點出發，依次掃描 after指向的下一個Node節點，直到最後一個

TreeMap 疊代

因為TreeMap是紅黑樹，左孩子 < 根 < 右孩子，

是以按照樹的中序周遊方式進行掃描，即先擷取樹的左孩子，然後是根，最後是右孩子

示意圖如下：

4. 應用場景&使用小建議

1. HashMap, LinkedHashMap, TreeMap 非線程安全，是以都不适用于多線程環境下
2. 希望有序的Map，考慮采用 LinkedHashMap, TreeMap

• 有自己的排序需求場景的，可以使用TreeMap
• 根據塞入Map的先後順序進行排序的，可以使用 LinkedHashMap

1. 其他普通kv接口存儲，盡量采用 ​

   ​HashMap​

   ​

• 若能确定Map的元素個數，在初始化時，顯示指定容量大小，避免頻繁的數組擴容
• key的hash盡量分散，避免出現大量的hash碰撞（一般不自己覆寫 key的 ​

  ​hashcode​

  ​ 方法，這個問題不太大）

1. 有自定義排序需求時，使用 ​

   ​TreeMap​

   ​

• 盡量保證結構的穩定，不會頻繁出現添加删除的情況（因為會導緻）
• Map中不存在兩個Key通過定義的比較器，傳回0，即不存在類似 ​

  ​HashMap​

  ​ 的碰撞情況

1. 根據進入Map的先後确定周遊順序，使用 ​

   ​LinkedHashMap​

   ​

• 遵從 ​

  ​HashMap​

  ​ 的使用規則

相關博文

• JDK容器學習之HashMap (一) ： 底層存儲結構分析
• JDK容器學習之HashMap (二) ： 讀寫邏輯詳解
• JDK容器學習之HashMap (三) : 疊代器實作
• JDK容器學習之TreeMap (一) : 底層資料結構
• JDK容器學習之TreeMap (二) : 使用說明
• JDK容器學習之LinkedHashMap（一）：底層存儲結構分析
• JDK容器學習之LinkedHashMap（二）：疊代周遊的實作方式

II. Java分享，關注小灰灰Blog