ToB企服应用市场:ToB评测及商务社交产业平台

标题: TreeMap源码详解—彻底搞懂红黑树的平衡操作 [打印本页]

作者: 八卦阵 时间: 2024-9-11 19:01
标题: TreeMap源码详解—彻底搞懂红黑树的平衡操作
先容

TreeSet和TreeMap在Java里有着雷同的实现，前者仅仅是对后者做了一层包装，也就是说TreeSet里面有一个TreeMap(适配器模式)。
Java TreeMap实现了SortedMap接口，也就是说会按照key的大小顺序对Map中的元素进行排序，key大小的评判可以通过其本身的自然顺序(natural ordering)，也可以通过构造时传入的比较器(Comparator)。
TreeMap底层通过红黑树(Red-Black tree)实现，也就意味着containsKey(), get(), put(), remove()都有着log(n)的时间复杂度。

TreeMap存储 Key-Value 对时，需要根据 key-value 对进行排序。TreeMap 可以包管所有的 Key-Value 对处于有序状态。
- 正常环境下TreeMap是不能存入值为null的键的。
- 但通过自定义比较器能让TreeMap存入一个值为null的键。
- 存入的值为null键对应的值不能通过通过它来获取，只能通过直接遍历Values。
TreeSet底层利用红黑树结构存储数据
TreeMap 的 Key 的排序：
- 自然排序：TreeMap 的所有的 Key 必须实现 Comparable 接口，而且所有的 Key 应该是同一个类的对象，否则将会抛出 ClasssCastException
- 定制排序：创建 TreeMap 时，传入一个 Comparator 对象，该对象负责对TreeMap 中的所有 key 进行排序。此时不需要 Map 的 Key 实现Comparable 接口
TreeMap判断两个key 相等的标准：两个key通过compareTo()方法大概compare()方法返回0。

底层实现

继续接口的关键方法

public class TreeMap<K,V>
extends AbstractMap<K,V>
implements NavigableMap<K,V>, Cloneable, java.io.Serializable

复制代码

返回用于排序此映射中的键的比较器，如果此映射利用其键的自然排序，则返回null。
SortedMap接口：
[code]Comparator

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)