Java 程序通过键和值对 HashMap 进行排序
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。根据具体要求,可能两种方法都适用。
相关文章
有用资源
java 参考教程 - 该教程包含有关 java 的更多信息:https://www.cainiaomax.com/java/

