Java 对HashMap按键和值进行排序

HashMap是Java编程语言中经常使用的数据结构，它可以让程序员存储键值对。这种数据结构非常高效，可以通过键快速检索值。然而，在某些情况下，有必要按照键或值的顺序对HashMap进行排序。在本文中，我们将探讨在Java中按键和值对HashMap进行排序的操作，并检查与每种技术相关的性能影响。

时间复杂度和HashMap

上述按值对HashMap进行排序的技术的时间复杂度为O(n log n)，其中n表示HashMap中的条目数。这是因为该过程涉及生成一个Map.Entry对象的List，这需要O(n)的时间，然后使用Comparator对List进行排序，这需要O(n log n)的时间。最后，将排序后的条目插入到TreeMap中需要O(n log n)的时间。因此，该方法的总体时间复杂度为O(n log n)。

对HashMap的不同排序方法

按键排序HashMap

要根据键对Java中的HashMap进行排序，可以使用TreeMap类。TreeMap是一个按照键的自然排序或自定义比较器来组织其条目的有序映射。按键对HashMap进行排序的步骤如下：

构造一个TreeMap实例，并将HashMap传入其构造函数。TreeMap将根据其键自动对条目排序。

通过使用for-each循环遍历TreeMap的条目，并按照排序顺序显示它们。

示例1

上述代码首先创建一个HashMap实例，然后添加键值对。然后，创建一个TreeMap实例，并将前面提到的HashMap传入其构造函数。结果，TreeMap将根据其键对条目进行排序。最后，我们使用for-each循环遍历TreeMap的条目，并以排序顺序展示它们。

需要注意的是，使用这种方法按键对HashMap进行排序的时间复杂度为O(n log n)，其中n表示映射中的条目总数。这是因为创建TreeMap实例需要O(n log n)的时间，与对数组进行排序相同。因此，对于大型映射来说，使用这种方法按键对HashMap进行排序可能非常昂贵。

import java.util.*;

public class SortHashMapByKey {
   public static void main(String[] args) {
      HashMap<String, Integer> map = new HashMap<>();
      map.put("John", 80);
      map.put("Alice", 70);
      map.put("Bob", 90);
      map.put("David", 75);

      System.out.println("HashMap before sorting: " + map);

      TreeMap<String, Integer> sortedMap = new TreeMap<>(map);
      System.out.println("HashMap after sorting by keys: " + sortedMap);

      for(Map.Entry<String, Integer> entry : sortedMap.entrySet()) {
         System.out.println(entry.getKey() + ": " + entry.getValue());
      }
   }
}

输出

HashMap before sorting: {Alice=70, Bob=90, David=75, John=80}
HashMap after sorting by keys: {Alice=70, Bob=90, David=75, John=80}
Alice: 70
Bob: 90
David: 75
John: 80

按值对HashMap进行排序

按值对HashMap进行排序比按键排序要复杂一些。这是因为Java中没有内置的技术可以按值对HashMap进行排序。然而，我们可以使用Comparator和TreeMap来实现这一点。

要按值对HashMap进行排序，我们首先生成一个与HashMap中条目相对应的Map.Entry对象列表。然后，我们使用自定义的Comparator来对列表进行排序，该Comparator评估Map.Entry对象的值。最后，我们将排序后的条目插入一个全新的TreeMap中，该TreeMap将根据它们的值对条目进行排序。

示例2

import java.util.*;

public class SortHashMapByValue {
   public static void main(String[] args) {
      // create a HashMap to be sorted by values
      Map<String, Integer> unsortedMap = new HashMap<>();
      unsortedMap.put("A", 5);
      unsortedMap.put("B", 3);
      unsortedMap.put("C", 7);
      unsortedMap.put("D", 1);

      // create a List of Map Entries
      List<Map.Entry<String, Integer>> entryList = new ArrayList<>(unsortedMap.entrySet());

      // sort the List using a Comparator
      Collections.sort(entryList, new Comparator<Map.Entry<String, Integer>>() {
         @Override
         public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
         return o1.getValue().compareTo(o2.getValue());
         }
      });

      // insert the sorted entries into a TreeMap
      Map<String, Integer> sortedMap = new TreeMap<>();
      for (Map.Entry<String, Integer> entry : entryList) {
         sortedMap.put(entry.getKey(), entry.getValue());
      }

      // print the sorted Map
      System.out.println(sortedMap);
   }
}