Java常用数据结构之Set之TreeSet
上篇文章我们分析了HashSet,它是基于HashMap实现的,那TreeSet会是怎么实现的呢?没错!和大家想的一样,它是基于TreeMap实现的。所以,TreeSet的源码也很简单,主要还是理解TreeMap。 按照惯例,先来看TreeSet类的继承关系: extends AbstractSet
这里主要看NavigableSet接口类: extends SortedSet
熟悉的味道,继承SortedSet接口。SortedSet则提供了一个返回比较器的方法: comparator();
和SortedMap一样,支持自然排序和自定义排序。自然排序要求添加到Set中的元素实现Comparable接口,自定义排序要求实现一个Comparator比较器。 关键点自然是TreeSet如何保证元素不重复以及元素有序的,前面说了它是基于TreeMap实现的,那我们来看看吧。 m; // 保证有序
// Dummy value to associate with an Object in the backing Map 纵观TreeSet源码,发现只有这两个属性(还有个uid,这里就不算了)。很明显,
m 是用来保存元素的,但m 声明的是NavigableMap 而不是TreeMap 。可以猜测,TreeMap 应该是在构造方法里实例化的,这里使用NavigableMap 可以让TreeSet更加灵活。PRESENT 和HashSet中的PRESENT 作用一样,作为固定Value值进行占位的。再看 add 和remove 方法:public boolean remove(Object o) {
return m.remove(o)==PRESENT; } 和HashSet的实现一样,也是利用了Map保存的Key-Value键值对的Key不会重复的特点。 果然,TreeSet中的TreeMap是在构造函数中初始化的。 ()); // 默认自然排序的TreeMap
}
public TreeSet(Comparator<? super E> comparator) { public TreeSet(Collection<? extends E> c) { public TreeSet(SortedSet 默认实例化了一个自然排序的TreeMap,当然,我们可以自定义比较器。 c) {
// Use linear-time version if applicable
if (m.size()==0 && c.size() > 0 &&
c instanceof SortedSet &&
m instanceof TreeMap) {
SortedSet extends E> set = (SortedSet extends E>) c;
TreeMap
调用了TreeMap的 set,V defaultVal) {
try {
buildFromSorted(set.size(),set.iterator(),null,defaultVal);
} catch (java.io.IOException | ClassNotFoundException cannotHappen) {
}
}
看到 既然实现了 public E lower(E e) {
return m.lowerKey(e); // 返回小于e的第一个元素 } public NavigableSet public E pollFirst() { // 弹出第一个元素 public NavigableSet ...... 这里需要注意的是返回子集合的方法,例如: subSet = intSet.headSet(8); // 最大值7,超过7越界
for (Integer sub : subSet) {
System.out.println(sub);
}
// subSet.add(8); // 越界了 TreeSet也是支持逆序输出的,因为有 descendingIterator() {
return m.descendingKeySet().iterator();
}
SortedSet s = Collections.synchronizedSortedSet(new TreeSet(...)) ;(编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |