1 Set集合主要源码分析
上一篇，我们介绍了Java集合框架中的Set集合，主要讲了HashSet和TreeSet这两个实现类。本篇，依旧对这两个实现类进行学习，通过学习源码来深入地了解。
1.1 HashSet源码分析(基于JDK1.7.0_75)
HashSet基于HashMap，底层方法是通过调用HashMap的API来实现，因此HashSet源码结构比较简单，代码较少。
- 成员变量：
在HashSet中，有两个成员变量比较重要--map、PRESENT;
其中，map就是存储元素的地方，实际是一个HashMap。当有元素插入到HashSet中时，会被当做HashMap的key保存到map属性中去。
对于HashMap来说，光有key还不够，在HashSet的实现中，每个key对应的value都默认为PRESENT属性，也就是new了一个Object对象而已；
public class HashSet<E>
extends AbstractSet<E>
implements Set<E>, Cloneable, java.io.Serializable{
static final long serialVersionUID = -5024744406713321676L;
//HashSet通过HashMap保存集合元素的：
private transient HashMap<E,Object> map;
//HashSet底层由HashMap实现，新增的元素为map的key，而value则默认为PRESENT。
private static final Object PRESENT = new Object();
}
- 构造方法：
HashSet的构造方法很简单，主要是在方法内部初始化map属性，new了一个HashMap对象；
public class HashSet<E>
extends AbstractSet<E>
implements Set<E>, Cloneable, java.io.Serializable {
//无参构造方法：
public HashSet() {
//默认new一个HashMap
map = new HashMap<>();
}
// 带集合的构造函数
public HashSet(Collection<? extends E> c) {
// 进行初始化HashMap容量判断，
map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
addAll(c);
}
// 指定HashSet初始容量和加载因子的构造函数：主要用于Map内部的扩容机制
public HashSet(int initialCapacity, float loadFactor) {
map = new HashMap<>(initialCapacity, loadFactor);
}
// 指定HashSet初始容量的构造函数
public HashSet(int initialCapacity) {
map = new HashMap<>(initialCapacity);
}
//与前4个不同，此构造最终new了一个LinkedHashMap对象：
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<>(initialCapacity, loadFactor);
}
}
- add():
HashSet的add(E e)方法，主要是调用底层HashMap的put(K key, V value)方法。
其中key就是HashSet集合插入的元素，而value则是默认的PRESENT属性(一个new Object());
//调用HashMap中的put()方法:
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
- remove():
与add(E e)方法类似，HashSet的remove(Object o)也是调用了底层HashMap的(Object key)方法；
主要是计算出要删除元素的hash值，在HashMap找到对应的对象，然后从Entry<K,V>[]数组中删除；
//调用HashMap中的remove方法：
public boolean remove(Object o) {
return map.remove(o)==PRESENT;
}
1.2 TreeSet源码分析(基于JDK1.7.0_75)
上面说了HashSet，接下来说说TreeSet。
与HashSet类似，TreeSet底层也是采用了一个Map来保存集合元素，这个Map就是NavigableMap。
不过，NavigableMap仅仅是一个接口，具体的实现还是使用了TreeMap类；
- 成员变量
当你看到下面的代码之后，你就会明白我为什么一直在说TreeSet底层使用了Map集合了；成员变量m是一个NavigableMap类型的Map集合，常用实现是TreeMap对象；
在TreeMap中，key是我们TreeSet插入的元素，而value则是TreeSet中另一个成员变量PRESENT，一个普通的不能再普通的Object对象；
public class TreeSet<E> extends AbstractSet<E>
implements NavigableSet<E>, Cloneable, java.io.Serializable {
//TreeSet中保存元素的map对象：
private transient NavigableMap<E,Object> m;
//map对象中保存的value:
private static final Object PRESENT = new Object();
}
-
构造方法
public class TreeSet<E> extends AbstractSet<E>
implements NavigableSet<E>, Cloneable, java.io.Serializable {//最底层的构造方法，不对外。传入一个NavigableMap接口的实现类 TreeSet(NavigableMap<E,Object> m) { this.m = m; } //无参构造：向底层构造传入一个TreeMap对象： public TreeSet() { this(new TreeMap<E,Object>()); } //传入比较器的构造：通常传入一个自定义Comparator的实现类； public TreeSet(Comparator<? super E> comparator) { this(new TreeMap<>(comparator)); } //将集合Collection传入TreeSet中： public TreeSet(Collection<? extends E> c) { this(); addAll(c); } //将集合SortedSet传入TreeSet中： public TreeSet(SortedSet<E> s) { this(s.comparator()); addAll(s); }}
- add
向TreeSet中添加元素：
public boolean add(E e) {
return m.put(e, PRESENT)==null;
}
- remove
删除TreeSet中元素o:
public boolean remove(Object o) {
return m.remove(o)==PRESENT;
}
无论是HashSet，还是TreeSet，它们的API都是通过底层的Map来实现的。所以就源码来说，没有太多需要去理解地方。
在后面的Map讲解中，我会在详细进行说明。当你理解了Map之后，再回过头来看Set，就很容易去理解了；
1.3 SortedSet和NavigableSet到底是什么
本章节，是我在写的时候突然想起来的，觉得有必要加进来阐述下。
为什么觉得有必要呢？
主要是看了一些关于TreeSet讲解的文章，在介绍TreeSet的时候都会提到NavigableSet，接着会说下NavigableSet是个"导航Set集合"，提供了一系列"导航"方法。看到这，我不禁想吐槽下，什么是"导航"方法。
针对于这个疑问，我查了下相关的资料，对这个类有个初步的理解。下面，我就说一下！
通过接口的定义，我们可以看到NavigableSet继承了SortedSet接口(后面说)，实现了对其的扩展；
而通过下面的方法，我们得出NavigableSet实际提供了一系列的搜索匹配元素的功能，能获取到某一区间内的集合元素 ；
public interface NavigableSet<E> extends SortedSet<E> {
E lower(E e);//返回此set集合中小于e元素的最大元素
E floor(E e);//返回此set集合中小于等于e元素的最大元素
E ceiling(E e);//返回此set集合中大于等于e元素的最小元素
E higher(E e);//返回此set集合中大于e元素的最小元素
E pollFirst(); //获取并移除此set集合中的第一个元素
E pollLast();//获取并移除此set集合中的最后一个元素
Iterator<E> iterator();//返回此set集合的迭代器--升序
NavigableSet<E> descendingSet();//以倒序的顺序返回此set集合
Iterator<E> descendingIterator();//返回此set集合的迭代器--倒序
//返回此set集合的部分元素--从fromElement开始到toElement结束，其中fromInclusive、toInclusive意为返回的集合是否包含头尾元素
NavigableSet<E> subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive);
//返回此set集合的部分元素--小于toElement，inclusive意味返回的集合是否包含toElement
NavigableSet<E> headSet(E toElement, boolean inclusive);
//返回此set集合的部分元素--从fromElement开始到toElement结束，包含头不含为尾
SortedSet<E> subSet(E fromElement, E toElement);
//返回此set集合的部分元素--小于toElement
SortedSet<E> headSet(E toElement);
//返回此set集合的部分元素--大于等于toElement
SortedSet<E> tailSet(E fromElement);
}
说完了NavigableSet，我们在一起儿看下其父类SortedSet接口：
通过名字，我们可以得出此接口跟排序有关，会提供跟排序的方法；
public interface SortedSet<E> extends Set<E> {
//返回与排序有关的比较器
Comparator<? super E> comparator();
//返回从fromElement到toElement的元素集合：
SortedSet<E> subSet(E fromElement, E toElement);
//返回从第一个元素到toElement元素的集合：
SortedSet<E> headSet(E toElement);
//返回从fromElement开始到最后元素的集合：
SortedSet<E> tailSet(E fromElement);
//返回集合中的第一个元素：
E first();
//返回集合中的最后一个元素：
E last();
}
