SortedMap

排序圖

在本課中，我們將學習SortedMap接口。我們將探討出現在該接口中的新方法，以及SortedMap的一種實現的特性——TreeMap——以及實現之間的差異，以及它們與HashMap相比的優勢。

讓我們看看地圖的層次結構是什麼樣的。特別注意SortedMap接口及其TreeMap實現——它們是我們今天的重點：

SortedMap接口擴展了Map接口。在許多方面，它類似於SortedSet（後者又擴展了Set），因為它們都描述了類似的存儲和使用排序值的功能。

SortedSet使用並存儲<TValue>對象，但 SortedMap 存儲<TKey, TValue>對。它是一個映射，按鍵的升序存儲其所有元素。

SortedMap接口擴展了Map。它添加了以下方法：

樹圖類

TreeMap類是SortedMap接口的一個實現。也就是說，TreeMap實現了SortedMap添加的所有方法以及Map接口中的標準方法。

您可以使用如下構造函數創建TreeMap對象：

• TreeMap()：創建一個實現為樹的空地圖；

• TreeMap(Map<? extends TKey, ? extends TValue> map)：創建一棵樹並添加來自輸入映射的所有元素；

• TreeMap(SortedMap<TKey, ? extends TValue> smap)：創建樹並添加來自輸入排序映射的所有元素；

• TreeMap(Comparator<? super TKey> comparator)：創建一個空樹——比較器將用於對隨後添加的所有元素進行排序。

這裡TKey是存儲對中鍵的類型，TValue是存儲在TreeMap中的對中值的類型。

Comparator對於SortedMap / TreeMap非常重要。它建立了對我們的地圖進行排序或排序的規則。如果我們不提供比較器，那麼在創建SortedMap時將使用鍵的自然排序。

向 TreeMap 添加元素

使用put()方法將元素成對添加到地圖中。鍵作為第一個參數傳遞，值作為第二個參數傳遞。例如，假設我們要創建一個學生列表和他們的成績。

SortedMap<String, Integer> map =new TreeMap <String,Integer>();

map.put("Anthony", 5);
map.put("Sara", 5);
map.put("Roxy", 5);
map.put("Jeff", 4);
map.put("Nick", 4);
map.put("Oliver", 3);
map.put("Oliver", 5);

System.out.println(map);

結果：

當我們添加一個鍵值對時，如果鍵已經存在於集合中，那麼舊值將被新值替換。在我們的示例中，使用具有相同密鑰的兩對 — ("Oliver", 3)和("Oliver", 5) 來說明此行為。

讓我們看一個帶有我們創建的比較器的示例。假設我們要存儲按鍵字符串長度排序的元素。如果鍵的長度相等，那麼我們將按字母順序排序（字符串的自然順序）：

class LengthComparator implements Comparator<String> {
  public int compare(String o1, String o2) {
    Integer lenghComparedResult = Integer.compare(o1.length(), o2.length());
    return lenghComparedResult != 0 ? lenghComparedResult : o1.compareTo(o2);
  }
}

SortedMap<String, Integer> lengthComparedMap = new TreeMap<String, Integer>(new LengthComparator());

lengthComparedMap.put("Jeff", 4);
lengthComparedMap.put("Oliver", 5);
lengthComparedMap.put("Roxy", 4);
lengthComaredMap.put("Jan", 4);

這是結果序列：

此行為使TreeMap類似於排序的數組或列表，其索引是單詞 ( String ) 而不是數字。

TreeMap 類中的 SortedMap 方法

1. 如果需要獲取第一個學生的鑰匙，可以使用firstKey ()方法：

   
   String firstKey = map.firstKey();
   	System.out.println("First key → " + firstKey);
   

   結果：第一把鑰匙 → Anthony

2. 如果需要獲取最後一個學生的key，可以使用lastKey()方法：

   
   String lastKey = map.lastKey();
   System.out.println("Last key → " + lastKey);
   

   結果：最後一把鑰匙 → Jeff

3. 獲取鍵為“ Sara ”的對象之後的所有對象：

   
   Map<String, Integer> tailMap = map.tailMap("Sara");
            	System.out.println("tailMap: " + tailMap);
   

   結果：tailMap: {Sara=5, Jeff=4}

4. 獲取鍵為“ Nick ”的對象之前的所有對象：

   
   System.out.println("headMap: " + headMap);
    Map<String, Integer> headMap = map.headMap("Nick");
   

   結果：headMap：{Anthony=5}

5. 獲取鍵為“ Oliver ”的對象之後和鍵為“ Sara ”的對象之前的所有對象：

   
   Map<String, Integer> subMap = map.subMap("Oliver", "Sara");	
   System.out.println("subMap: " + subMap);
   

   結果：subMap: {Oliver=5, Roxy=5}

HashMap與SortedMap/TreeMap的比較

下面說一下元素是如何排序和存儲的：

• 由於HashMap在迭代時沒有給我們任何關於順序的保證，所以當添加新元素時，順序可能會完全改變。

• 在TreeMap中，順序基於鍵的“自然排序”，根據它們的compareTo()方法（或我們提供的Comparator ）。另外，不要忘記TreeMap實現了SortedMap接口，該接口包含依賴於此排序順序的方法。

現在我們轉向性能和速度的考慮：

• HashMap是基於散列鍵的映射。它可以在O(1)中插入和獲取元素，恆定時間。為了支持這一點，鍵必須實現hashCode()和equals()。

• TreeMap是一個基於樹的地圖。它的插入和獲取操作需要對數時間，即O(log n)，這取決於地圖中元素的數量。這是必要的，以便元素具有由我們的鍵或外部比較器提供的某種比較機制。這種機制決定了迭代順序。

這些因素幫助我們決定使用哪些集合以及何時使用。

如果我們需要以特定順序存儲值，選擇是顯而易見的——我們需要一個SortedMap。雖然它比HashMap慢一點，但它為我們執行了重要的任務。

如前所述，SortedMap可以為我們提供映射中的第一個（或最後一個）鍵、值或鍵值對，而不管該值是何時添加的。HashMap實現無法做到這一點。

例如，考慮一個帶有鍵（學生姓名）和值（他們的成績）的映射。比方說，我們想要以逆字母順序處理一個列表。

1.

SortedMap<String, Integer> sorted = new TreeMap<String,Integer>(Comparator.reverseOrder());
sorted.put("Anthony", 5);
sorted.put("Sara", 5);
sorted.put("Jeff", 4);

String firstKeyFromSortedMapVariant = sorted.firstKey();

Integer markFromSortedMap = sorted.get(firstKeyFromSortedMapVariant);
System.out.println(firstKeyFromSortedMapVariant + " - " + markFromSortedMap);

2.

HashMap<String, Integer> hash = new HashMap<String,Integer>();
hash.put("Anthony", 5);
hash.put("Sara", 5);
hash.put("Jeff", 4);

SortedSet<String> keySetOfHashMap = new TreeSet<String>(Comparator.reverseOrder());
// Or sort manually, storing elements in an array or list (preserving the insertion order)
keySetOfHashMap.addAll(hash.keySet());
String firstKeyFromHashMapVariant = keySetOfHashMap.first();


Integer markFromHashMap = hash.get(firstKeyFromHashMapVariant);
System.out.println(firstKeyFromHashMapVariant + " - " + markFromHashMap);

該示例表明，使用HashMap會使任務變得更加複雜，因為HashMap既不能保證存儲順序，也不能保證從映射中獲取元素的順序。