java - 为什么以及何时使用 TreeMap

Question

有人可以告诉我何时以及为什么使用TREEMAP。我浏览了这个链接 ，但没有找到我的答案。

根据我的想法，我们使用树形图根据您的键获取数据排序，同样我们也可以通过其他方式实现。

Answer 1

假设您要实现一个字典并按字母顺序打印它，您可以使用 TreeMap 和 TreeSet 的组合：

public static void main(String args[]) {
    Map<String, Set<String>> dictionary = new TreeMap<>();
    Set<String> a = new TreeSet<>(Arrays.asList("Actual", "Arrival", "Actuary"));
    Set<String> b = new TreeSet<>(Arrays.asList("Bump", "Bravo", "Basic"));

    dictionary.put("B", b);
    dictionary.put("A", a);

    System.out.println(dictionary);
}

所有排序都是自动完成的，它会打印：

{A=[Actual, Actuary, Arrival], B=[Basic, Bravo, Bump]}

当然，您也可以手动对结构进行排序，但使用 TreeMap/Set 可以更有效，减少代码行数（= 错误数）并且更具可读性。

Answer 2

这是让对象按某个键排序的有效方法。如果随机访问对您也很重要，那么 TreeMap 就是答案。使用此数据结构，您可以按顺序迭代。

如果不需要随机访问，则使用排序集/包或列表。

为什么Java中没有SortedList？

Answer 3

您链接到的 javadoc 清楚地表明它是可导航和排序的地图接口的实现。当您需要此功能时，您会使用它。

Answer 4

树状图

基于红黑树的 NavigableMap 实现。地图根据其键的自然顺序排序，或者由地图创建时提供的比较器排序，具体取决于使用的构造函数。

此实现为 containsKey、get、put 和 remove 操作提供有保证的 log(n) 时间成本。算法是对 Cormen、Leiserson 和 Rivest 的算法简介中的那些算法的改编。

当您需要有序键时使用此数据结构，不仅可以升序，还可以传递comparator给构造函数TreeMap(Comparator<? super K> comparator) 来编写自己的排序逻辑。它也是一种自平衡二叉搜索树。