通过分析JDK源代码研究TreeMap红黑树算法实现

通过分析JDK源代码研究TreeMap红黑树算法实现2011-09-30 IBM 李刚简介：TreeMap 和 TreeSet 是 Java Collection Framework 的两个重要成员，其中 TreeMap 是 Map 接口的常用实现类，而 TreeSet 是 Set 接口的常用实现类。虽然 HashMap 和 HashSet 实现的接口规范不同，但 TreeSet 底层是通过 TreeMap 来实现的，因此二者的实现方式完全一样。而 TreeMap 的实现就是红黑树算法。

TreeMap 的实现就是红黑树数据结构，也就说是一棵自平衡的排序二叉树，这样就可以保证当需要快速检索指定节点。

TreeSet 和 TreeMap 的关系

为了让大家了解 TreeMap 和 TreeSet 之间的关系，下面先看 TreeSet 类的部分源代码：

public class TreeSet<E> extends AbstractSet<E>
   implements NavigableSet<E>, Cloneable, java.io.Serializable
  {
   // 使用 NavigableMap 的 key 来保存 Set 集合的元素
   private transient NavigableMap<E,Object> m;
   // 使用一个 PRESENT 作为 Map 集合的所有 value。
   private static final Object PRESENT = new Object（）;
   // 包访问权限的构造器，以指定的 NavigableMap 对象创建 Set 集合
   TreeSet（NavigableMap<E,Object> m）
   {
     this.m = m;
   }
   public TreeSet（）                   // ①
   {
     // 以自然排序方式创建一个新的 TreeMap，
     // 根据该 TreeSet 创建一个 TreeSet，
     // 使用该 TreeMap 的 key 来保存 Set 集合的元素
     this（new TreeMap<E,Object>（））;
   }
   public TreeSet（Comparator<？ super E> comparator）   // ②
   {
     // 以定制排序方式创建一个新的 TreeMap，
     // 根据该 TreeSet 创建一个 TreeSet，
     // 使用该 TreeMap 的 key 来保存 Set 集合的元素
     this（new TreeMap<E,Object>（comparator））;
   }
   public TreeSet（Collection<？ extends E> c）
   {
     // 调用①号构造器创建一个 TreeSet，底层以 TreeMap 保存集合元素
     this（）;
     // 向 TreeSet 中添加 Collection 集合 c 里的所有元素
     addAll（c）;
   }
   public TreeSet（SortedSet<E> s）
   {
     // 调用②号构造器创建一个 TreeSet，底层以 TreeMap 保存集合元素
     this（s.comparator（））;
     // 向 TreeSet 中添加 SortedSet 集合 s 里的所有元素
     addAll（s）;
   }
   //TreeSet 的其他方法都只是直接调用 TreeMap 的方法来提供实现
   ...
   public boolean addAll（Collection<？ extends E> c）
   {
     if （m.size（） == 0 && c.size（） > 0 &&
       c instanceof SortedSet &&
       m instanceof TreeMap）
     {
       // 把 c 集合强制转换为 SortedSet 集合
       SortedSet<？ extends E> set = （SortedSet<？ extends E>）  c;
       // 把 m 集合强制转换为 TreeMap 集合
       TreeMap<E,Object> map = （TreeMap<E, Object>） m;
       Comparator<？ super E> cc = （Comparator<？ super E>）  set.comparator（）;
       Comparator<？ super E> mc = map.comparator（）;
       // 如果 cc 和 mc 两个 Comparator 相等 
       if （cc == mc || （cc ！= null && cc.equals（mc）））
       {
         // 把 Collection 中所有元素添加成 TreeMap 集合的 key
         map.addAllForTreeSet（set, PRESENT）;
         return true;
       }
     }
     // 直接调用父类的 addAll（） 方法来实现
     return super.addAll（c）;
   }
   ...
  }