TreeMap详解(作用原理及使用实例)

TreeMap详解(作用原理及使用实例)-mikechen

TreeMap是很常见的Java集合框架,下面详解TreeMap的原理与实现,以及TreeMap的使用示例@mikechen

TreeMap定义

TreeMap是常用到的Java集合,TreeMap 是基于红黑树实现的有序映射,它可以用于需要按照键的顺序进行排序和查找的场景。

 

TreeMap作用

TreeMap 适用于需要有序映射的场景,TreeMap 的主要作用有:

1.方便排序

由于 TreeMap 中的元素是有序的,可以方便地进行排序操作。

2.高效查找

由于 TreeMap 中的元素是基于红黑树实现的,因此可以在 O(log n) 时间复杂度内查找特定的元素,所以可以高效查找。

3.实现有序映射

TreeMap可以用于实现有序映射,其中每个键都与一个值相关联。

 

TreeMap方法

TreeMap 是一个实现了 SortedMap 接口的有序键值对集合,下面列举了一些常用的 TreeMap 方法:

  1. put(K key, V value):将指定的键值对插入到 TreeMap 中。
  2. get(Object key):获取指定键的对应值,如果键不存在则返回 null。
  3. containsKey(Object key):判断 TreeMap 中是否包含指定的键。
  4. remove(Object key):删除指定键对应的键值对。
  5. size():获取 TreeMap 中键值对的数量。
  6. clear():清空 TreeMap 中的所有键值对。
  7. firstKey():获取 TreeMap 中的第一个键。
  8. lastKey():获取 TreeMap 中的最后一个键。
  9. keySet():获取 TreeMap 中所有键的 Set 集合。
  10. values():获取 TreeMap 中所有值的集合。
  11. entrySet():获取 TreeMap 中所有键值对的 Set 集合。

 

TreeMap使用

下面是一个使用 TreeMap 的示例,演示了如何插入、查询、删除键值对,以及如何遍历 TreeMap 中的键值对。

示例如下:

import java.util.TreeMap;

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

        // 插入键值对
        map.put("apple", 10);
        map.put("banana", 20);
        map.put("orange", 30);

        // 查询键值对
        int appleCount = map.get("apple"); // 10
        int pearCount = map.getOrDefault("pear", 0); // 0

        // 删除键值对
        map.remove("banana");

        // 遍历键值对
        for (String key : map.keySet()) {
            int value = map.get(key);
            System.out.println(key + " - " + value);
        }
    }
}

在这个示例中:

  1. 首先创建了一个 TreeMap 对象;
  2. 然后使用 put() 方法插入了三个键值对,键为字符串,值为整数;
  3. 然后使用 get() 方法查询了键为 “apple” 的值;
  4. 并使用 getOrDefault() 方法查询了键为 “pear” 的值;
  5. 接下来使用 remove() 方法删除了键为 “banana” 的键值对;
  6. 然后使用 keySet() 方法获取 TreeMap 中所有的键,并遍历了 TreeMap 中的所有键值对。

 

TreeMap原理

TreeMap 的底层原理基于红黑树的平衡二叉搜索树,它的核心思想是将键值对按照键的大小关系存储在红黑树中,通过比较键的大小,实现有序的键值对映射,并且支持高效的排序、查找和子集操作等功能。

TreeMap的底层数据结构是一颗基于红黑树(Red-Black Tree)的平衡二叉搜索树。

如下图所示:

TreeMap详解(作用原理及使用实例)-mikechen

红黑树是一种二叉搜索树,它的每个节点都有一个颜色(红色或黑色)。

红黑树必须满足以下性质:

  1. 每个节点都是红色或黑色;
  2. 根节点是黑色的;
  3. 每个叶子节点(NIL节点,空节点)都是黑色的;
  4. 如果一个节点是红色的,则它的两个子节点都是黑色的;
  5. 对于每个节点,从该节点到其所有后代叶子节点的简单路径上,均包含相同数目的黑色节点;

然而,由于它是基于红黑树实现的,因此 TreeMap 在插入、删除元素时需要平衡树,这可能会导致较慢的性能。

在某些场景下,可能需要使用其他数据结构,例如 HashMap

以上就是TreeMap的详解,更多Java集合请查看:Java集合(万字图文全面详解)

以上

关注「mikechen」公众号,获取更多技术干货!

后台回复【面试】即可获取《史上最全阿里Java面试题总结》,后台回复【架构】,即可获取《阿里架构师进阶专题全部合集

评论交流
    说说你的看法