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接口：
Comparator
页:
[1]