1 Set集合主要源碼分析
上一篇，我們介紹了Java集合框架中的Set集合怒竿，主要講了HashSet和TreeSet這兩個實現(xiàn)類荠雕。本篇稳其，依舊對這兩個實現(xiàn)類進行學習，通過學習源碼來深入地了解舞虱。
1.1 HashSet源碼分析(基于JDK1.7.0_75)
HashSet基于HashMap欢际，底層方法是通過調(diào)用HashMap的API來實現(xiàn)母市，因此HashSet源碼結構比較簡單矾兜，代碼較少。
- 成員變量：
在HashSet中患久，有兩個成員變量比較重要--map椅寺、PRESENT;
其中浑槽，map就是存儲元素的地方，實際是一個HashMap返帕。當有元素插入到HashSet中時桐玻，會被當做HashMap的key保存到map屬性中去。
對于HashMap來說荆萤，光有key還不夠镊靴，在HashSet的實現(xiàn)中，每個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實現(xiàn)，新增的元素為map的key敞峭，而value則默認為PRESENT踊谋。
private static final Object PRESENT = new Object();
}
- 構造方法：
HashSet的構造方法很簡單，主要是在方法內(nèi)部初始化map屬性旋讹，new了一個HashMap對象殖蚕；
public class HashSet<E>
extends AbstractSet<E>
implements Set<E>, Cloneable, java.io.Serializable {
//無參構造方法：
public HashSet() {
//默認new一個HashMap
map = new HashMap<>();
}
// 帶集合的構造函數(shù)
public HashSet(Collection<? extends E> c) {
// 進行初始化HashMap容量判斷，
map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
addAll(c);
}
// 指定HashSet初始容量和加載因子的構造函數(shù)：主要用于Map內(nèi)部的擴容機制
public HashSet(int initialCapacity, float loadFactor) {
map = new HashMap<>(initialCapacity, loadFactor);
}
// 指定HashSet初始容量的構造函數(shù)
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)方法睦疫，主要是調(diào)用底層HashMap的put(K key, V value)方法。
其中key就是HashSet集合插入的元素鞭呕，而value則是默認的PRESENT屬性(一個new Object());
//調(diào)用HashMap中的put()方法:
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
- remove():
與add(E e)方法類似笼痛，HashSet的remove(Object o)也是調(diào)用了底層HashMap的(Object key)方法；
主要是計算出要刪除元素的hash值琅拌，在HashMap找到對應的對象缨伊，然后從Entry<K,V>[]數(shù)組中刪除；
//調(diào)用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僅僅是一個接口未玻，具體的實現(xiàn)還是使用了TreeMap類灾而；
- 成員變量
當你看到下面的代碼之后，你就會明白我為什么一直在說TreeSet底層使用了Map集合了扳剿；成員變量m是一個NavigableMap類型的Map集合旁趟，常用實現(xiàn)是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接口的實現(xiàn)類 TreeSet(NavigableMap<E,Object> m) { this.m = m; } //無參構造：向底層構造傳入一個TreeMap對象： public TreeSet() { this(new TreeMap<E,Object>()); } //傳入比較器的構造：通常傳入一個自定義Comparator的實現(xiàn)類肠缔； 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來實現(xiàn)的明未。所以就源碼來說拓春，沒有太多需要去理解地方。
在后面的Map講解中亚隅，我會在詳細進行說明硼莽。當你理解了Map之后，再回過頭來看Set煮纵，就很容易去理解了懂鸵；
1.3 SortedSet和NavigableSet到底是什么
本章節(jié)，是我在寫的時候突然想起來的行疏，覺得有必要加進來闡述下匆光。
為什么覺得有必要呢？
主要是看了一些關于TreeSet講解的文章酿联，在介紹TreeSet的時候都會提到NavigableSet终息，接著會說下NavigableSet是個"導航Set集合"，提供了一系列"導航"方法贞让≈苷福看到這，我不禁想吐槽下喳张，什么是"導航"方法续镇。
針對于這個疑問，我查了下相關的資料销部，對這個類有個初步的理解摸航。下面，我就說一下舅桩！
通過接口的定義酱虎，我們可以看到NavigableSet繼承了SortedSet接口(后面說)，實現(xiàn)了對其的擴展擂涛；
而通過下面的方法读串，我們得出NavigableSet實際提供了一系列的搜索匹配元素的功能，能獲取到某一區(qū)間內(nèi)的集合元素 ；
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();
}
