Java 程序通过键和值对 HashMap 进行排序

javaobject oriented programmingprogramming更新于 2024/9/24 11:56:17

HashMap 是 Java 编程语言中经常使用的数据结构,它使程序员能够存储键值对。此数据结构是一种非常有效的数据存储方法,并允许基于键快速检索值。但是,有时可能需要按其键或值排列 HashMap。在本文中,我们将深入研究在 Java 中按其键和值对 HashMap 进行排序的过程,并研究与每种技术相关的性能影响。

时间复杂度和 HashMap

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

对 HashMap 进行排序的不同方法

按键对 HashMap 进行排序

要在 Java 中根据其键排列 HashMap,可以使用 TreeMap 类。TreeMap 是一个排序映射,它根据其自然顺序或自定义的 Comparator 以排序模式组织其条目。随后的步骤涉及根据其键对 HashMap 进行排序

构造 TreeMap 实例并将 HashMap 提供给其构造函数。 TreeMap 将根据键自动对条目进行排序。

使用 for-each 循环遍历 TreeMap 的条目,并以排序后的模式显示它们。

示例 1

上述代码首先创建一个 HashMap 实例,并在其中添加键值对。随后,通过将上述 HashMap 馈送到其构造函数中来创建 TreeMap 实例。因此,TreeMap 将根据条目的键对条目进行排序。最后,我们使用 for-each 循环遍历 TreeMap 的条目,并以排序后的顺序显示它们。

必须指出的是,使用此技术对 HashMap 的键进行排序的时间复杂度为 O(n log n),其中 n 表示 Map 中的条目总数。这是因为创建 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 进行排序,我们首先生成一个 Map.Entry 对象列表,该列表反映了 HashMap 中的条目。然后,我们使用个性化的 Comparator 对列表进行排序,该 Comparator 评估 Map.Entry 对象的值。最后,我们将排序后的条目插入到一个全新的 TreeMap 中,该 TreeMap 将根据条目的值对条目进行排序。

示例 2

import java.util.*;

public class SortHashMapByValue {
   public static void main(String[] args) {
      // 创建一个按值排序的 HashMap
      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());

      // 使用比较器对列表进行排序
      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());
         }
      });

      // 将排序后的条目插入到 TreeMap 中
      Map<String, Integer> sortedMap = new TreeMap<>();
      for (Map.Entry<String, Integer> entry : entryList) {
         sortedMap.put(entry.getKey(), entry.getValue());
      }

      // 打印排序后的 Map
      System.out.println(sortedMap);
   }
}

输出

{D=1, B=3, A=5, C=7}

性能比较:按键排序与按值排序

确定按键还是按值对 HashMap 进行排序取决于具体情况。按键排序通常比按值排序更快,因为它可以使用内置的 TreeMap.sort() 方法实现,其时间复杂度为 O(n log n)。相比之下,按值排序需要自定义 Comparator 和 TreeMap,其时间复杂度更大,为 O(n log n)。

结论

在 Java 中,可以通过两种不同的方式对 HashMap 进行排序:按键排序或按值排序。当 HashMap 中的键已知且唯一,并且排序基于值的重要性时,按键排序更受青睐。另一方面,当排序主要基于值,而键的重要性是次要的时,则首选按值排序。

在 Java 的 HashMap 中,按键排序是一个相当简单的过程,可以使用内置的 TreeMap.sort() 方法完成。相比之下,按值排序需要自定义 Comparator 和 TreeMap。根据具体要求,可能两种方法都适用。


相关文章


有用资源