Map圖

LinkedHashMap

HashMap 是 Java Collection Framework 的重要成員，也是Map族(如下圖所示)中
我們最為常用的一種。不過遺憾的是，HashMap是無序的，也就是說，迭代HashMap所得到的元素順序并不是它們最初放置到HashMap的順序。HashMap的這一
缺點往往會造成諸多不便，因為在有些場景中，我們確需要用到一個可以保持插入順序的Map。慶幸的是，JDK為我們解決了這個問題，它為HashMap提供了一個子類
—— LinkedHashMap。雖然LinkedHashMap增加了時間和空間上的開銷，但是它通過維護一個額外的雙向鏈表保證了迭代順序。特別地，該迭代順序可以是插入順序，
也可以是訪問順序。因此，根據鏈表中元素的順序可以將LinkedHashMap分為：保持插入順序的LinkedHashMap 和 保持訪問順序的LinkedHashMap，
其中LinkedHashMap的默認實現(xian)是按插入順(shun)序排序的。

• 更直觀地，下圖很好地還原了LinkedHashMap的原貌：HashMap和雙向鏈表的密切配合和分工合作造就了LinkedHashMap。特別需要注意的是，next用于
  維護HashMap各個桶中的Entry鏈，before、after用于維護LinkedHashMap的雙向鏈表，雖然它們的作用對象都是Entry，但是各自分離，是兩碼事兒。

• 其中，HashMap與LinkedHashMap的Entry結構示意圖如下圖所示：

SortedMap

SortedMap（java.util.SortedMap）接口(kou)是Map的子接口(kou)，SortedMap中增加了元(yuan)素的排(pai)序，這意味著可(ke)以給SortedMap中的元(yuan)素排(pai)序。

• NavigableMap
  • TreeMap
  • ConcurrentSkipListMap

NavigableMap

SortedMap的子接口，但是 NavigableMap接口中新加了幾個SortedSet接口中沒有的方法，使導航存儲在映射中的鍵和值成為可能，本文會講解。
既然是接口，那就必須用到它的實現，java.util包中只有一個實現 java.util.TreeMap ，另外java.util.concurrent包中也(ye)有實(shi)現，但是本文(wen)不(bu)講解

NavigableMap original = new TreeMap();
original.put("1", "1");
original.put("2", "2");
original.put("3", "3");

TreeMap

TreeMap的實現是紅黑樹(shu)算(suan)法的實現, 紅黑樹(shu)又稱紅-黑二叉樹(shu)，它(ta)首(shou)先(xian)是一顆二叉樹(shu)，它(ta)具體二叉樹(shu)所有的特性。同時紅黑樹(shu)更是一顆自平衡的排序(xu)二叉樹(shu)。

• 平衡二叉樹必須具備如下特性：它是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，并且左右兩個子樹都是一棵平衡二叉樹。也就是說該二叉樹的任何一個等等子節點，其左右子樹的高度都相近。
  
• 紅黑樹顧名思義就是節點是紅色或者黑色的平衡二叉樹，它通過顏色的約束來維持著二叉樹的平衡。對于一棵有效的紅黑樹二叉樹而言我們必須增加如下規則：

1. 每個節點都只能是紅色或者黑色
2. 根節點是黑色
3. 每個葉節點（NIL節點，空節點）是黑色的。
4. 如果一個結點是紅的，則它兩個子節點都是黑的。也就是說在一條路徑上不能出現相鄰的兩個紅色結點。
5. 從任一節點到其每個葉子的所有路徑都包含相同數目的黑色節點。

• 對(dui)于紅黑二叉樹(shu)而(er)言它主要包括三大(da)基本操作：左旋、右旋、著色。

• 左旋轉
  

• 右旋轉
  

SortedMap<String, String> list = new TreeMap<>(); //基于紅黑樹的實現，在單線程性能不錯.
list.put("a", "1");
list.put("b", "2");
list.put("c", "3");
list.put("d", "4");
SortedMap<String, String> tail = list.tailMap("c");//返回大于等于c的
Iterator<String> iterator = tail.values().iterator();
while (iterator.hasNext()) {
  System.out.println(iterator.next());
}

ConcurrentSkipListMap

多線程下使用，支持更高的并(bing)發，ConcurrentSkipListMap 的存取時間是(shi)log（N），和線程數幾乎(hu)無關，內部是(shi)SkipList（跳表）結構實(shi)現(xian)。

跳躍表（SkipList）

1. 多條鏈構成，是關鍵字升序排列的數據結構；
2. 包含多個級別，一個head引用指向最高的級別，最低（底部）的級別，包含所有的key；
3. 每一個級別都是其更低級別的子集，并且是有序的；
4. 如果關鍵字 key在 級別level=i中出現，則，level<=i的鏈表中都會包含該關鍵字key；

ConcurrentSkipListMap<String, String> concurrentSkipListMap = new ConcurrentSkipListMap<>();
String a1 = concurrentSkipListMap.put("zzl", "zhangzhanling");
String a2 = concurrentSkipListMap.put("zzl1", "zhan1");
String a3 = concurrentSkipListMap.put("zzl2", "zhan2");
String a4 = concurrentSkipListMap.put("china", "中國");
System.out.printf(concurrentSkipListMap.toString());