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既不能保证存储顺序，也不能保证从映射中获取元素的顺序。