Java集合之TreeMap总结

时间:2021-07-15 17:18:08

一、TreeMap 概述

        摘自JDKAPI1.6版本部分解释:TreeMap 是基于红黑树的实现,是有序的,它根据 key 的自然顺序排序,或者根据指定的比较器(comparetor)进行排序,具体取决于构造方法。 TreeMap 不是同步的,因为排序调用比较方法,所以不支持 null 键,但是可以 null 值。


二、总结 TreeMap 的关键点


        1、TreeMap 是有序的,按照自然排序或者指定比较器排序,不允许 null 键,允许 null 值,是不同步。

        2、TreeMap 是基于红黑树实现的最大的好处就是可以按照业务场景得到已排序的结果。

三、结论分析


        1、为什么 TreeMap 用红黑树实现?红黑树是什么?

                TreeMap 保证了 Map 容器的有序性,而红黑树是为了保证插入和删除的性能。当我们在开发中需要用到有序的且按大小排列顺序的、不重复的、有映射关系的业务场景时,Java 提供了 TreeMap 这个容器用于方便开发者使用。

                红黑树是一种自平衡的二叉树,这种数据结构有五个性质:
                        a、节点只有红色和黑色,
                        b、根节点是黑色,
                        c、每个叶子节点是黑色(叶子节点就是null节点),
                        d、每个红色节点下一定是两个黑色节点,
                        e、从任意一个节点到它的叶子节点的所有路径上的黑色节点数相同,
                其中最重要的是第五点,第四点决定了第五点的成立,而第五点决定了整个树的平衡性。TreeMap 的新增和删除方法中对上面的五种情况进行了实现。

四、总结


        TreeMap 的总结写的比较简单,关于红黑树是可以写很长的篇幅的。但是这篇博客只是描述 TreeMap 的特性和使用场景,它就是红黑树实现的,要了解实现原理只有先去百度了解红黑树是什么,结合 TreeMap 的源码看是怎么实现的,才能理解。