开发学院软件开发Java 通过分析 JDK 源代码研究 TreeMap 红黑树算法实现... 阅读

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

 2010-05-31 00:00:00 来源:WEB开发网   
核心提示:TreeMap 的实现就是红黑树数据结构,也就说是一棵自平衡的排序二叉树,通过分析 JDK 源代码研究 TreeMap 红黑树算法实现,这样就可以保证当需要快速检索指定节点,TreeSet 和 TreeMap 的关系为了让大家了解 TreeMap 和 TreeSet 之间的关系,//根据该TreeSet创建一个Tree

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); 
  } 
  ... 
 } 

1 2 3 4 5 6  下一页

Tags:通过 分析 JDK

编辑录入:爽爽 [复制链接] [打 印]
[]
  • 好
  • 好的评价 如果觉得好,就请您
      0%(0)
  • 差
  • 差的评价 如果觉得差,就请您
      0%(0)
赞助商链接