TreeSet源码解析

TreeSet源码解析来源:Java编程的逻辑1实现原理1.1构造方法TreeSet的基本构造方法有两个:publicTreeSet(){this(newTreeMap<E,Object>());}publicTreeSet(Comparator<?superE>comparator){this(newTreeMap<>(co…

来源:
Java编程的逻辑

1 实现原理

1.1 构造方法

TreeSet的基本构造方法有两个:

public TreeSet() { 
   
    this(new TreeMap<E,Object>());
}

public TreeSet(Comparator<? super E> comparator) { 
   
    this(new TreeMap<>(comparator));
}

默认构造方法假定元素实现了Comparable接口,第二个使用传入的比较器,不要求元素实现Comparable。

TreeSet的其他构造方法为:

public TreeSet(Collection<? extends E> c) { 
   
    this();
    addAll(c);
}

public TreeSet(SortedSet<E> s) { 
   
    this(s.comparator());
    addAll(s);
}

TreeSet(NavigableMap<E,Object> m) { 
   
    this.m = m;
}

前两个都是以一个已有的集合为参数,将其中的所有元素添加到当前TreeSet,区别在于,在第一个中,比较器为null,假定元素实现了Comparable接口,而第二个中,比较器设为和参数SortedSet中的一样。

第三个不是public的,是内部用的。

1.2 SortedSet接口

public interface SortedSet<E> extends Set<E> { 
   
    Comparator<? super E> comparator();
    SortedSet<E> subSet(E fromElement, E toElement);
    SortedSet<E> headSet(E toElement);
    SortedSet<E> tailSet(E fromElement);
    E first();
    E last();
}

1.3 NavigableSet

扩展了SortedSet,主要增加了一些查找邻近元素的方法,比如:

E floor(E e); //返回小于等于e的最大元素
E lower(E e); // 返回小于e的最大元素
E ceiling(E e); //返回大于等于e的最小元素
E higher(E e); //返回大于e的最小元素

1.4 内部组成

TreeSet的内部有如下成员:

private transient NavigableMap<E,Object> m;
private static final Object PRESENT = new Object();

m就是背后的那个TreeMap,这里用的是更为通用的接口类型NavigableMap,PRESENT就是那个固定的共享值。

TreeSet的方法实现主要就是调用m的方法

1.5 add

public boolean add(E e) { 
   
    return m.put(e, PRESENT)==null;
}

就是调用map的put方法,元素e用作键,值就是固定值PRESENT,put返回null表示原来没有对应的键,添加成功了。

1.6 contains

public boolean contains(Object o) { 
   
    return m.containsKey(o);
}

检查map中是否包含对应的键。

1.7 remove

public boolean remove(Object o) { 
   
    return m.remove(o)==PRESENT;
}

调用map的remove方法,返回值为PRESENT表示原来有对应的键且删除成功了。

1.8 子集视图

subSet方法的代码:

public NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
                              E toElement,   boolean toInclusive) { 
   
    return new TreeSet<>(m.subMap(fromElement, fromInclusive,
                                   toElement,   toInclusive));
}

先调用subMap方法获取NavigatebleMap的子集,然后调用内部的TreeSet构造方法。

1.9 头尾操作

public E first() { 
   
    return m.firstKey();
}

public E last() { 
   
    return m.lastKey();
}

public E pollFirst() { 
   
    Map.Entry<E,?> e = m.pollFirstEntry();
    return (e == null) ? null : e.getKey();
}

public E pollLast() { 
   
    Map.Entry<E,?> e = m.pollLastEntry();
    return (e == null) ? null : e.getKey();
}

1.10 逆序遍历

public Iterator<E> descendingIterator() { 
   
    return m.descendingKeySet().iterator();
}

public NavigableSet<E> descendingSet() { 
   
    return new TreeSet<>(m.descendingMap());
}

2 特点分析

与HashSet相比,TreeSet同样实现了Set接口,但内部基于TreeMap实现,而TreeMap基于大致平衡的排序二叉树 – 红黑树,这决定了它有如下特点:

  • 没有重复元素
  • 添加、删除元素、判断元素是否存在,效率比较高,为O(log2(N)),N为元素个数。
  • 有序,TreeSet同样实现了SortedSet和NavigatableSet接口,可以方便的根据顺序进行查找和操作,如第一个、最后一个、某一取值范围、某一值的邻近元素等。
  • 为了有序,TreeSet要求元素实现Comparable接口或通过构造方法提供一个Comparator对象。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/35297.html

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注