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。
  

底层实现

继续接口的关键方法

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

复制代码

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