526互联

Java TreeMap 介绍与使用

发布时间 2023-07-12 20:29:06作者: 白露~

介绍

TreeMap 是 Java 集合框架中的一个类，它实现了 SortedMap 接口，可以存储键值对，并按照键的自然顺序或者指定的比较器进行排序。TreeMap 的底层是一棵红黑树，这是一种自平衡的二叉搜索树，可以保证在插入，删除，查找等操作中的时间复杂度为 O(log n)。

使用

要使用 TreeMap，我们需要导入 java.util 包，并创建一个 TreeMap 对象。我们可以指定键和值的类型，也可以使用泛型。例如：

import java.util.*;

// 创建一个 TreeMap，键为 String 类型，值为 Integer 类型
TreeMap<String, Integer> map = new TreeMap<>();

// 创建一个 TreeMap，使用泛型
TreeMap<String, Integer> map = new TreeMap<>();

我们可以使用 put 方法向 TreeMap 中添加键值对，如果键已经存在，则会覆盖原来的值。我们可以使用 get 方法根据键获取对应的值，如果键不存在，则会返回 null。我们可以使用 remove 方法根据键删除对应的键值对，如果键不存在，则不会有任何影响。我们可以使用 size 方法获取 TreeMap 中的键值对的数量。我们可以使用 containsKey 方法判断 TreeMap 中是否包含某个键。我们可以使用 containsValue 方法判断 TreeMap 中是否包含某个值。我们可以使用 clear 方法清空 TreeMap 中的所有键值对。例如：

import java.util.*;

public class TreeMapDemo {
    public static void main(String[] args) {
        // 创建一个 TreeMap
        TreeMap<String, Integer> map = new TreeMap<>();

        // 向 TreeMap 中添加键值对
        map.put("Alice", 90);
        map.put("Bob", 80);
        map.put("Charlie", 70);
        map.put("David", 60);

        // 打印 TreeMap 的内容
        System.out.println(map); // {Alice=90, Bob=80, Charlie=70, David=60}

        // 根据键获取对应的值
        System.out.println(map.get("Alice")); // 90
        System.out.println(map.get("Eve")); // null

        // 根据键删除对应的键值对
        map.remove("Bob");
        System.out.println(map); // {Alice=90, Charlie=70, David=60}

        // 获取 TreeMap 中的键值对的数量
        System.out.println(map.size()); // 3

        // 判断 TreeMap 中是否包含某个键
        System.out.println(map.containsKey("Charlie")); // true
        System.out.println(map.containsKey("Eve")); // false

        // 判断 TreeMap 中是否包含某个值
        System.out.println(map.containsValue(70)); // true
        System.out.println(map.containsValue(50)); // false

        // 清空 TreeMap 中的所有键值对
        map.clear();
        System.out.println(map); // {}
    }
}

除了上述方法外，TreeMap 还提供了一些特有的方法，用于利用其排序特性进行操作。例如：

  • firstKey 和 lastKey：分别返回 TreeMap 中最小和最大的键。
  • lowerKey 和 higherKey：分别返回 TreeMap 中小于和大于给定键的最近的键。
  • floorKey 和 ceilingKey：分别返回 TreeMap 中小于等于和大于等于给定键的最近的键。
  • subMap：返回一个子映射，包含给定范围内的所有键值对。
  • headMap 和 tailMap：分别返回一个子映射，包含小于或等于给定键或大于或等于给定键的所有键值对。
  • firstEntry 和 lastEntry：分别返回 TreeMap 中最小和最大的键值对。
  • lowerEntry 和 higherEntry：分别返回 TreeMap 中小于和大于给定键的最近的键值对。
  • floorEntry 和 ceilingEntry：分别返回 TreeMap 中小于等于和大于等于给定键的最近的键值对。
  • pollFirstEntry 和 pollLastEntry：分别返回并删除 TreeMap 中最小和最大的键值对。

例如：

import java.util.*;

public class TreeMapDemo2 {
    public static void main(String[] args) {
        // 创建一个 TreeMap
        TreeMap<String, Integer> map = new TreeMap<>();

        // 向 TreeMap 中添加键值对
        map.put("Alice", 90);
        map.put("Bob", 80);
        map.put("Charlie", 70);
        map.put("David", 60);

        // 打印 TreeMap 的内容
        System.out.println(map); // {Alice=90, Bob=80, Charlie=70, David=60}

        // 返回 TreeMap 中最小和最大的键
        System.out.println(map.firstKey()); // Alice
        System.out.println(map.lastKey()); // David

        // 返回 TreeMap 中小于和大于给定键的最近的键
        System.out.println(map.lowerKey("Bob")); // Alice
        System.out.println(map.higherKey("Bob")); // Charlie

        // 返回 TreeMap 中小于等于和大于等于给定键的最近的键
        System.out.println(map.floorKey("Bob")); // Bob
        System.out.println(map.ceilingKey("Bob")); // Bob

        // 返回一个子映射，包含给定范围内的所有键值对
        System.out.println(map.subMap("Alice", true, "Charlie", true)); // {Alice=90, Bob=80, Charlie=70}

        // 返回一个子映射，包含小于或等于给定键或大于或等于给定键的所有键值对
        System.out.println(map.headMap("Charlie", true)); // {Alice=90, Bob=80, Charlie=70}
        System.out.println(map.tailMap("Charlie", true)); // {Charlie=70, David=60}

        // 返回 TreeMap 中最小和最大的键值对
        System.out.println(map.firstEntry()); // Alice=90
        System.out.println(map.lastEntry()); // David=60

        // 返回 TreeMap 中小于和大于给定键的最近的键值对
        System.out.println(map.lowerEntry("Bob")); // Alice=90
        System.out.println(map.higherEntry("Bob")); // Charlie=70

        // 返回 TreeMap 中小于等于和大于等于给定键的最近的键值对
        System.out.println(map.floorEntry("Bob")); // Bob=80
        System.out.println(map.ceilingEntry("Bob")); // Bob=80

        // 返回并删除 TreeMap 中最小和最大的键值对
        System.out.println(map.pollFirstEntry()); // Alice=90
        System.out.println(map.pollLastEntry()); // David=60

    }
}

适用场景

TreeMap 是一种有序的映射，它可以在保证高效性的同时，提供一些基于排序的操作。因此，TreeMap 适用于以下场景：

  • 需要按照键的自然顺序或者指定的比较器进行排序的场景，例如字典，排行榜，日程安排等。
  • 需要快速找到映射中最小或者最大的键或者值的场景，例如优先队列，堆，区间查询等。
  • 需要快速找到映射中某个范围内的所有键或者值的场景，例如范围搜索，前缀匹配，区间统计等。

底层原理

TreeMap 的底层是一棵红黑树，这是一种自平衡的二叉搜索树，它满足以下性质：

  • 每个节点要么是红色，要么是黑色。
  • 根节点是黑色。
  • 每个叶子节点（空节点）是黑色。
  • 如果一个节点是红色，那么它的两个子节点都是黑色。
  • 从任意一个节点到其每个叶子节点的所有路径都包含相同数目的黑色节点。

这些性质保证了红黑树在插入，删除，查找等操作中都能保持平衡

源码分析

我们来看一下 TreeMap 的源码，主要关注它的内部类，构造方法，和一些重要的方法。

内部类

TreeMap 的内部类有以下几个：

  • Entry：表示树中的一个节点，包含键，值，颜色，左子节点，右子节点，父节点等属性。
  • KeySet：表示键的集合，实现了 NavigableSet 接口，提供了一些基于排序的操作。
  • Values：表示值的集合，实现了 Collection 接口，提供了一些基本的操作。
  • EntrySet：表示键值对的集合，实现了 Set 接口，提供了一些基本的操作。
  • PrivateEntryIterator：表示树中节点的迭代器，实现了 Iterator 接口，提供了 next 和 remove 方法。
  • KeyIterator：继承自 PrivateEntryIterator，用于遍历键。
  • ValueIterator：继承自 PrivateEntryIterator，用于遍历值。
  • EntryIterator：继承自 PrivateEntryIterator，用于遍历键值对。
  • AscendingSubMap：表示一个升序的子映射，实现了 NavigableMap 接口，提供了一些基于排序的操作。
  • DescendingSubMap：表示一个降序的子映射，实现了 NavigableMap 接口，提供了一些基于排序的操作。
  • AscendingKeySetIterator：用于遍历升序子映射中的键。
  • DescendingKeySetIterator：用于遍历降序子映射中的键。

构造方法

TreeMap 的构造方法有以下几个：

  • TreeMap()：创建一个空的 TreeMap，按照键的自然顺序进行排序。
  • TreeMap(Comparator<? super K> comparator)：创建一个空的 TreeMap，并指定一个比较器来对键进行排序。
  • TreeMap(Map<? extends K,? extends V> m)：创建一个 TreeMap，并将给定映射中的所有键值对添加到 TreeMap 中，并按照键的自然顺序进行排序。
  • TreeMap(SortedMap<K,? extends V> m)：创建一个 TreeMap，并将给定有序映射中的所有键值对添加到 TreeMap 中，并按照给定有序映射中的比较器或者自然顺序进行排序。

重要方法

TreeMap 的重要方法有以下几个：

  • put(K key, V value)：向 TreeMap 中添加一个键值对，如果键已经存在，则覆盖原来的值，并返回原来的值。如果键不存在，则返回 null。该方法会调用 putVal 方法来实现插入操作。putVal 方法会先判断树是否为空，如果为空，则直接创建一个黑色的根节点。如果不为空，则从根节点开始遍历树，根据比较器或者自然顺序来比较给定键和当前节点的键。如果相等，则覆盖当前节点的值。如果小于，则向左子树遍历。如果大于，则向右子树遍历。如果遇到空节点，则在该位置创建一个红色的新节点，并将其连接到父节点上。然后调用 fixAfterInsertion 方法来修复插入后可能导致红黑树性质被破坏的情况。fixAfterInsertion 方法会根据不同的情况进行不同的旋转和变色操作，以保证红黑树性质得到恢复。

  • get(Object key)：根据给定键获取对应的值，如果键不存在，则返回 null。该方法会调用 getEntry 方法来实现查找操作。getEntry 方法会从根节点开始遍历树，根据比较器或者自然顺序来比较给定键和当前节点的键。如果相等，则返回当前节点。如果小于，则向左子树遍历。如果大于，则向右子树遍历。如果遇到空节点，则返回 null。

  • remove(Object key)：根据给定键删除对应的键值对，如果键不存在，则不会有任何影响，并返回 null。如果键存在，则返回被删除的值。该方法会调用 getEntry 方法来找到要删除的节点，然后调用 deleteEntry 方法来实现删除操作。deleteEntry 方法会先判断要删除的节点是否有两个非空的子节点，如果有，则找到它的后继节点（右子树中最小的节点），并将后继节点的键值复制到要删除的节点上，然后将后继节点作为要删除的节点。然后判断要删除的节点是否有一个非空的子节点，如果有，则将该子节点替换要删除的节点，并将其连接到父节点上。如果没有，则直接断开要删除的节点和父节点的连接。然后判断要删除的节点是否是黑色，如果是，则调用 fixAfterDeletion 方法来修复删除后可能导致红黑树性质被破坏的情况。fixAfterDeletion 方法会根据不同的情况进行不同的旋转和变色操作，以保证红黑树性质得到恢复。

  • firstKey()：返回 TreeMap 中最小的键，如果 TreeMap 为空，则抛出 NoSuchElementException 异常。该方法会调用 getFirstEntry 方法来实现查找操作。getFirstEntry 方法会从根节点开始，沿着左子树一直向下遍历，直到遇到空节点，然后返回其父节点。

  • lastKey()：返回 TreeMap 中最大的键，如果 TreeMap 为空，则抛出 NoSuchElementException 异常。该方法会调用 getLastEntry 方法来实现查找操作。getLastEntry 方法会从根节点开始，沿着右子树一直向下遍历，直到遇到空节点，然后返回其父节点。

  • lowerKey(K key)：返回 TreeMap 中小于给定键的最近的键，如果没有这样的键，则返回 null。该方法会调用 getLowerEntry 方法来实现查找操作。getLowerEntry 方法会从根节点开始遍历树，根据比较器或者自然顺序来比较给定键和当前节点的键。如果小于等于，则向左子树遍历，并记录当前节点为候选结果。如果大于，则向右子树遍历，并不更新候选结果。如果遇到空节点，则返回候选结果。

  • higherKey(K key)：返回 TreeMap 中大于给定键的最近的键，如果没有这样的键，则返回 null。该方法会调用 getHigherEntry 方法来实现查找操作。getHigherEntry 方法会从根节点开始遍历树，根据比较器或者自然顺序来比较给定键和当前节点的键。如果小于，则向左子树遍历，并不更新候选结果。如果大于等于，则向右子树遍历，并记录当前节点为候选结果。如果遇到空节点，则返回候选结果。

  • floorKey(K key)：返回 TreeMap 中小于等于给定键的最近的键，如果没有这样的键，则返回 null。该方法会调用 getFloorEntry 方法来实现查找操作。getFloorEntry 方法会从根节点开始遍历树，根据比较器或者自然顺序来比较给定键和当前节点的键。如果小于，则向左子树遍历，并不更新候选结果。如果等于，则直接返回当前节点。如果大于，则向右子树遍历，并记录当前节点为候选结果。如果遇到空节点，则返回候选结果。

  • ceilingKey(K key)：返回 TreeMap 中大于等于给定键的最近的键，如果没有这样的键，则返回 null。该方法会调用 getCeilingEntry 方法来实现查找操作。getCeilingEntry 方法会从根节点开始遍历树

  • 根据比较器或者自然顺序来比较给定键和当前节点的键。如果小于，则向左子树遍历，并记录当前节点为候选结果。如果等于，则直接返回当前节点。如果大于，则向右子树遍历，并不更新候选结果。如果遇到空节点，则返回候选结果。

    • subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive)：返回一个子映射，包含给定范围内的所有键值对，根据 fromInclusive 和 toInclusive 参数来决定是否包含边界值。如果 fromKey 大于 toKey，则抛出 IllegalArgumentException 异常。该方法会创建一个 AscendingSubMap 对象，并将给定的参数传递给它的构造方法。

    • headMap(K toKey, boolean inclusive)：返回一个子映射，包含小于或等于给定键的所有键值对，根据 inclusive 参数来决定是否包含边界值。该方法会创建一个 AscendingSubMap 对象，并将 null，false，toKey，inclusive 作为参数传递给它的构造方法。

    • tailMap(K fromKey, boolean inclusive)：返回一个子映射，包含大于或等于给定键的所有键值对，根据 inclusive 参数来决定是否包含边界值。该方法会创建一个 AscendingSubMap 对象，并将 fromKey，inclusive，null，false 作为参数传递给它的构造方法。

    • firstEntry()：返回 TreeMap 中最小的键值对，如果 TreeMap 为空，则返回 null。该方法会调用 getFirstEntry 方法来实现查找操作。

    • lastEntry()：返回 TreeMap 中最大的键值对，如果 TreeMap 为空，则返回 null。该方法会调用 getLastEntry 方法来实现查找操作。

    • lowerEntry(K key)：返回 TreeMap 中小于给定键的最近的键值对，如果没有这样的键值对，则返回 null。该方法会调用 getLowerEntry 方法来实现查找操作。

    • higherEntry(K key)：返回 TreeMap 中大于给定键的最近的键值对，如果没有这样的键值对，则返回 null。该方法会调用 getHigherEntry 方法来实现查找操作。

    • floorEntry(K key)：返回 TreeMap 中小于等于给定键的最近的键值对，如果没有这样的键值对，则返回 null。该方法会调用 getFloorEntry 方法来实现查找操作。

    • ceilingEntry(K key)：返回 TreeMap 中大于等于给定键的最近的键值对，如果没有这样的键值对，则返回 null。该方法会调用 getCeilingEntry 方法来实现查找操作。

    • pollFirstEntry()：返回并删除 TreeMap 中最小的键值对，如果 TreeMap 为空，则返回 null。该方法会调用 getFirstEntry 方法来找到要删除的节点，然后调用 deleteEntry 方法来实现删除操作。

    • pollLastEntry()：返回并删除 TreeMap 中最大的键值对，如果 TreeMap 为空，则返回 null。该方法会调用 getLastEntry 方法来找到要删除的节点，然后调用 deleteEntry 方法来实现删除操作。

    注意事项

    使用 TreeMap 时，需要注意以下几点：

    • 如果使用自然顺序进行排序，则需要保证键是可比较的（实现了 Comparable 接口），否则会抛出 ClassCastException 异常。
    • 如果使用指定的比较器进行排序，则需要保证比较器是一致的（满足自反性，对称性，传递性），否则可能导致排序结果不正确或者抛出 ClassCastException 异常。
    • 如果在遍历 TreeMap 的过程中修改了其结构（添加或删除了元素），则可能导致 ConcurrentModificationException 异常或者不确定的行为。
    • 如果在遍历 TreeMap 的过程中修改了其元素（改变了键或者值），则可能导致排序结果不正确或者不确定的行为。
    • TreeMap 不是线程安全的，如果多个线程同时访问或修改 TreeMap，则需要进行同步处理。

    总结

    TreeMap 是一种有序的映射，它可以存储键值对，并按照键的自然顺序或者指定的比较器进行排序。TreeMap 的底层是一棵红黑树，这是一种自平衡的二叉搜索树，可以保证在插入，删除，查找等操作中的时间复杂度为 O(log n)。TreeMap 还提供了一些特有的方法，用于利用其排序特性进行操作。使用 TreeMap 时，需要注意一些细节，以避免出现异常或者不确定的行为。TreeMap 是 Java 集合框架中的一个重要的类，它在很多场景中都有着广泛的应用。