Java集合(一) —— Collection源码分析
Java集合(二) —— ArrayList源码分析
Java集合(三) —— LinkedList源码分析
Java集合(四) —— PriorityQueue源码分析
Java集合(五) —— HashSet源码分析
Java集合(六) —— LinkedHashSet源码分析
Java集合(七) —— TreeSet源码分析
Java集合(八) —— HashMap源码分析
Java集合(九) —— LinkedHashMap源码分析
Java集合(十) —— TreeMap源码分析
1.总结
1.TreeSet底层使用的是TreeMap保存数据的。
2.TreeMap的数据结构为红黑树(自平衡的二叉排序树(也叫二叉查找树或二叉搜索树))，即红黑树中序遍历是有序的，树的遍历方式都是相对根节点来说的，不懂的小朋友自行百度吧。
3.TreeSet是无序的，即数据插入的顺序和遍历得到的数据顺序可能是不一样的(不要将插入顺序与红黑树的可排序搞混了)。
2.TreeSet继承关系图
TreeSet.png
3.源码分析
3.1.成员变量分析
// 使用指定的Map保存数据
private transient NavigableMap<E,Object> m;
// Map中保存的value值
private static final Object PRESENT = new Object();
3.2.构造方法分析
/**
* 使用NavigableMap保存数据
*/
TreeSet(NavigableMap<E,Object> m) {
this.m = m;
}
/**
* 默认构造使用TreeMap保存数据
*/
public TreeSet() {
this(new TreeMap<E,Object>());
}
/**
* 指定使用的比较器
*/
public TreeSet(Comparator<? super E> comparator) {
this(new TreeMap<>(comparator));
}
public TreeSet(Collection<? extends E> c) {
this();
addAll(c);
}
public TreeSet(SortedSet<E> s) {
this(s.comparator());
addAll(s);
}
对于日常开发，基本上知道默认的构造方法就够了
3.3.常用方法
1.新增元素
/**
* 默认调用了TreeMap保存数据
*/
public boolean add(E e) {
return m.put(e, PRESENT)==null;
}
public boolean addAll(Collection<? extends E> c) {
// m即TreeMap的size等于0，c即集合的size大于0，m必须是TreeMap，c必须是SortedSet
// 基本上很少情况会同时满足上述四个条件
if (m.size()==0 && c.size() > 0 &&
c instanceof SortedSet &&
m instanceof TreeMap) {
SortedSet<? extends E> set = (SortedSet<? extends E>) c;
TreeMap<E,Object> map = (TreeMap<E, Object>) m;
Comparator<?> cc = set.comparator();
Comparator<? super E> mc = map.comparator();
if (cc==mc || (cc != null && cc.equals(mc))) {
// 新增数据的处理方法，这里就不再展开说明了
map.addAllForTreeSet(set, PRESENT);
return true;
}
}
// 调用父类的addAll方法，最终都循环调用add方法新增数据
return super.addAll(c);
}
2.删除元素
public boolean remove(Object o) {
return m.remove(o)==PRESENT;
}
/**
* 直接清空TreeMap
*/
public void clear() {
m.clear();
}
3.查找元素
/**
* 获取第一个元素
*/
public E first() {
return m.firstKey();
}
/**
* 获取最后一个元素
*/
public E last() {
return m.lastKey();
}
关于TreeSet的分析，基本上都是关于TreeMap的，所以TreeSet没必要过于深究，具体请看TreeMap的分析。
