Java的集合類由Collection接口和Map接口派生，其中：
- List代表有序集合，元素有序且可重複
- Set代表無序集合，元素無序且不可重複
- Map集合存儲鍵值對
那麼本篇文章将從源碼角度讨論一下無序集合Set。
HashSet
HashSet實作 Set 接口，由哈希表（實際上是一個 HashMap 執行個體）支援。它不保證 set 的疊代順序；特别是它不保證該順序恒久不變。此類允許使用 null 元素。看下面的一個例子：
HashSet<String> hs = new HashSet<String>();
// 添加元素
hs.add("hello");
hs.add("world");
hs.add("java");
hs.add("world");
hs.add(null);
//周遊
for (String str : hs) {
System.out.println(str);
} 複制
執行結果：
null
world
java
hello 複制
由執行結果可知，它允許加入null，元素不可重複，且元素無序。
那我們想，它是如何保證元素不重複的呢？這就要來分析一下它的源碼。
首先是HashSet集合的add()方法：
public boolean add(E e) {
return map.put(e, PRESENT)==null;
} 複制
該方法中調用了map對象的put()方法，那麼map對象是什麼呢？
private transient HashMap<E,Object> map; 複制
可以看到，這個map對象就是HashMap，我們繼續檢視HashSet的構造方法：
public HashSet() {
map = new HashMap<>();
} 複制
到這裡，應該就能明白，HashSet的底層實作就是HashMap，是以調用的put()方法就是HashMap的put()方法，那我們繼續檢視put()方法：
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
} 複制
put()方法調用了putVal()方法，那麼重點就是這個putVal()方法了：
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//判斷hashmap對象中 tabel屬性是否為空--->為空---->resize()
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//發現tab[i] 沒有值，直接存入即可
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
//tab[i]有值，分情況讨論
Node<K,V> e; K k;
// 如果新插入的元素和table中p元素的hash值，key值相同的話
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 如果是紅黑樹結點的話，進行紅黑樹插入
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
// 代表這個單連結清單隻有一個頭部結點，則直接建立一個結點即可
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// 連結清單長度大于8時，将連結清單轉紅黑樹
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// 如果與單向連結清單上的某個結點key值相同，則跳出循環，此時e是需要修改的結點，p是e的前驅結點
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
//更新變量p
p = e;
}
}
//處理完畢，添加元素
if (e != null) { // existing mapping for key
V oldValue = e.value;
//判斷是否允許覆寫，并且value是否為空
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;// 更改操作次數
//如果大于臨界值
if (++size > threshold)
//将數組大小設定為原來的2倍，并将原先的數組中的元素放到新數組中
resize();
afterNodeInsertion(evict);
return null;
} 複制
我們一起分析一下這段源碼，首先它将table對象指派給tab，并判斷tab是否為空，這裡的table就是哈希表，因為HashMap是基于哈希表的Map接口的實作，如果哈希表為空則調用resize()方法開辟存儲空間并指派給tab，然後将tab的長度指派給n。接着根據 (n - 1) & hash 算法計算出i并擷取tab的第i個元素，如果沒有值，那麼可以直接存入，如果有值，那麼就存在兩種情況：
- hash值重複
- 位置沖突
也就是說，如果在添加過程中發現key值重複，那麼就把p複制給e，p為目前位置上的元素，e為需要被修改的元素。而位置沖突又分為幾種情況：
- 産生位置沖突時，table數組下面的結點以單連結清單的形式存在，插入結點時直接放在連結清單最末位
- 産生位置沖突時，key值和之前的結點一樣
- 産生位置沖突時，table數組下面的結點以紅黑樹的形式存在，插入結點時需要在樹中查找合适位置
那麼根據這三種情況，需要分别作出判斷：如果p是TreeNode的執行個體(p instanceof TreeNode)，說明p下面挂着紅黑樹，需要在樹中找到一個合适的位置e插入。如果p下面的結果數沒有超過8，則p就是以單向連結清單的形式存在，然後在連結清單中逐個往下找到空位置；如果超過了8，就要将p轉換為紅黑樹；如果與單向連結清單上的某個結點key值相同，則跳出循環，此時e是需要修改的結點，p是e的前驅結點。最後就是判斷插入後的大小，如果大于threshold，則繼續申請空間。
那麼這是jdk1.8之後的關于HashMap的存儲方式，也就是數組 + 連結清單 + 紅黑樹的結構，而在1.8之前，HashMap是由數組 + 連結清單的結構作為存儲方式的。
是以HashSet如何保證元素是唯一的呢？關鍵就在于這一句判斷：
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) 複制
它先看hashCode()值是否相同，如果相同，則繼續看equals()方法，如果也相同，則證明元素重複，break跳出循環，元素不添加，如果不相同則進行添加。是以當一個自定義的類想要正确存入HashSet集合，就應該去重寫equals()方法和hashCode()方法，而String類已經重寫了這兩個方法，是以它就可以把相同的字元串去掉，隻保留其中一個。
那我們繼續看下面的一個例子：
自定義學生類
public class Student {
private String name;
private int age;
public Student(String name, int age) {
this.name = name;
this.age = age;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getAge() {
return age;
}
public void setAge(int age) {
this.age = age;
}
@Override
public String toString() {
return "Student [name=" + name + ", age=" + age + "]";
}
} 複制
然後編寫測試代碼：
HashSet<Student> hs = new HashSet<Student>();
//添加元素
Student s = new Student("劉德華",30);
Student s2 = new Student("陳奕迅",31);
Student s3 = new Student("周星馳",32);
Student s4 = new Student("劉德華",30);
hs.add(s);
hs.add(s2);
hs.add(s3);
hs.add(s4);
//周遊
for (Student student : hs) {
System.out.println(student);
} 複制
在上述代碼中，s4和s對象的姓名和年齡都相同，按理說這是兩個相同的對象，是不能同時在HashSet集合中存在的，然而我們看運作結果：
Student [name=周星馳, age=32]
Student [name=劉德華, age=30]
Student [name=陳奕迅, age=31]
Student [name=劉德華, age=30] 複制
如果前面的源碼分析大家都了解了的話，這個相信大家就能明白，這是因為我們沒有去重寫hashCode()方法和equals()方法，而它預設就會去調用Object的方法，是以它會認為每個學生對象都是不相同的。那我們現在來重寫一下這兩個方法：
@Override
public int hashCode() {
return 0;
}
@Override
public boolean equals(Object obj) {
//添加了一條輸出語句，用于顯示比較次數
System.out.println(this + "---" + obj);
if (this == obj) {
return true;
}
if (!(obj instanceof Student)) {
return false;
}
Student s = (Student) obj;
return this.name.equals(s.name) && this.age == s.age;
} 複制
然後我們運作程式：
Student [name=陳奕迅, age=31]---Student [name=劉德華, age=30]
Student [name=周星馳, age=32]---Student [name=劉德華, age=30]
Student [name=周星馳, age=32]---Student [name=陳奕迅, age=31]
Student [name=劉德華, age=30]---Student [name=劉德華, age=30]
Student [name=劉德華, age=30]
Student [name=陳奕迅, age=31]
Student [name=周星馳, age=32] 複制
可以看到，雖然去除了重複元素，但是比較的次數未免過多，因為hashCode()方法傳回的是一個固定值0，是以在進行判斷的時候hashCode值永遠相同進而多次調用equals()進行判斷，那麼我們就可以盡可能地使hashCode值不相同，那麼哈希值和哪些内容相關呢？
因為它和對象的成員變量值相關，是以我們可以進行如下措施：
如果是基本類型變量，直接加值；
如果是引用類型變量，加哈希值。
是以對hashCode()作如下修改：
@Override
public int hashCode() {
//為了避免某種巧合導緻兩個不相同的對象其計算後傳回的hashCode值相同，這裡對基本類型age進行一個乘積的運算
return this.name.hashCode() + this.age * 15;
} 複制
現在運作看效果：
Student [name=劉德華, age=30]---Student [name=劉德華, age=30]
Student [name=周星馳, age=32]
Student [name=劉德華, age=30]
Student [name=陳奕迅, age=31] 複制
重複元素成功被去除，而比較次數縮減為了一次，大大提升了程式運作效率。
LinkedHashSet
它是具有可預知疊代順序的 Set 接口的哈希表和連結清單實作，該集合方法全部繼承自父類HashSet，但它與HashSet的唯一差別就是它具有可預知疊代順序，它遵從存儲和取出順序是一緻的。直接舉例說明：
LinkedHashSet<String> linkedHashSet = new LinkedHashSet<String>();
//添加元素
linkedHashSet.add("hello");
linkedHashSet.add("world");
linkedHashSet.add("java");
//周遊
for (String str : linkedHashSet) {
System.out.println(str);
} 複制
運作結果：
hello
world
java 複制
TreeSet
它是基于 TreeMap 的 NavigableSet 實作。使用元素的自然順序對元素進行排序，或者根據建立 set 時提供的 Comparator 進行排序，具體取決于使用的構造方法。
舉例說明：
TreeSet<Integer> treeSet = new TreeSet<Integer>();
//添加元素
treeSet.add(10);
treeSet.add(26);
treeSet.add(20);
treeSet.add(13);
treeSet.add(3);
//周遊
for(Integer i : treeSet) {
System.out.println(i);
} 複制
運作結果：
3
10
13
20
26 複制
由此可見，TreeSet是具有排序功能的。但請注意，如果使用無參構造建立TreeSet集合，它将預設使用元素的自然排序；當然你也可以傳入比較器來構造出TreeSet。
那麼它是如何實作元素的自然排序的呢？我們通過源碼來分析一下：
首先看它的add()方法
public boolean add(E e) {
return m.put(e, PRESENT)==null;
} 複制
方法内部調用了m對象的put()方法，而這個m是一個NavigableMap對象：
private transient NavigableMap<E,Object> m; 複制
當我們繼續跟進put()方法的時候，發現它是一個抽象方法：
V put(K key, V value); 複制
該方法處于Map接口中，那麼我們就要去找Map接口的實作類，我們知道，TreeSet是基于TreeMap實作的，是以我們認為它調用的其實是TreeMap的put()方法，查閱TreeMap的繼承結構也可以證明這一點：
java.util
類 TreeMap<K,V>
java.lang.Object
繼承者 java.util.AbstractMap<K,V>
繼承者 java.util.TreeMap<K,V>
類型參數：
K - 此映射維護的鍵的類型
V - 映射值的類型
所有已實作的接口：
Serializable, Cloneable, Map<K,V>, NavigableMap<K,V>, SortedMap<K,V> 複制
TreeMap确實也實作了NavigableMap接口，那我們就來看一看TreeMap的put()方法：
public V put(K key, V value) {
Entry<K,V> t = root;
//建立樹的根結點
if (t == null) {
compare(key, key); // type (and possibly null) check
root = new Entry<>(key, value, null);
size = 1;
modCount++;
return null;
}
int cmp;
Entry<K,V> parent;
// split comparator and comparable paths
Comparator<? super K> cpr = comparator;
//判斷是否擁有比較器
if (cpr != null) {
//比較器排序
do {
parent = t;
cmp = cpr.compare(key, t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value);
} while (t != null);
}
else {
//判斷元素是否為空
if (key == null)
//抛出異常
throw new NullPointerException();
@SuppressWarnings("unchecked")
//将元素強轉為Comparable類型
do {
parent = t;
cmp = k.compareTo(t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value);
} while (t != null);
}
Entry<K,V> e = new Entry<>(key, value, parent);
if (cmp < 0)
parent.left = e;
else
parent.right = e;
fixAfterInsertion(e);
size++;
modCount++;
return null;
} 複制
我們來分析一下。
首先它會判斷Entry類型的變量t是否為空，那麼一開始該變量肯定為空，是以它會去建立Entry對象，我們知道， TreeMap是基于紅黑樹的實作，是以它其實是在建立樹的根結點。接着它會去判斷是否擁有比較器，因為我們使用的是無參構造建立的TreeSet，是以在這裡肯定是沒有比較器的，那麼他就執行else語句塊，我們可以看到這一句代碼：
Comparable<? super K> k = (Comparable<? super K>) key; 複制
根據我們剛才的程式分析，這裡的key就是我們傳入的Integer對象，那麼它是怎麼能夠将Integer對象強轉為Comparable對象的呢？查詢Comparable類的文檔後，我們知道，這是一個接口，此接口強行對實作它的每個類的對象進行整體排序。這種排序被稱為類的自然排序，類的 compareTo 方法被稱為它的自然比較方法。而Integer類實作了Comparable接口，是以可以将Integer向上轉型為Comparable對象。接着該對象調用了compareTo()方法，該方法傳回一個int類型值，作用是：如果該 Integer 等于 Integer 參數，則傳回 0 值；如果該 Integer 在數字上小于 Integer 參數，則傳回小于 0 的值；如果 Integer 在數字上大于 Integer 參數，則傳回大于 0 的值（有符号的比較）。是以它通過該方法的傳回值即可判斷出兩個數字的大小。如果小于0，則放在左邊(t.left)；如果大于0，則放在右邊(t.right)。這樣說可能過于抽象，我們可以通過畫圖來進一步了解：
這是二叉樹的存儲規則，第一個元素作為根結點，然後接下來的每個元素都先與根結點比較，大于根結點則作為右孩子，小于根結點則作為左孩子；如果位置上已經有元素了，則要繼續與該元素比較，比它大作為右孩子，比它小作為左孩子，以此類推。(若元素相等，則不存儲)
那麼元素是如何取出來的呢？學過資料結構的同學都知道，二叉樹有三種周遊方式：
- 前序周遊
- 中序周遊
- 後序周遊
那我們以前序周遊為例進行元素提取(按照左、中、右的原則)：
首先從根結點開始，根結點為10，然後看它的左孩子，左孩子為3，此時3已經沒有孩子，是以3第一個取出；這樣左邊就都取完了，我們取中間，也就是10；然後取右邊26，因為26還有孩子，是以取26的左邊20，因為20還有左孩子，是以13第三個取出；這樣20已經沒有孩子，我們取中間，也就是20，最後取出26。最終，元素的取出順序為：3，10，13，20，26；這樣就完成了元素的排序。
那麼以上是元素的自然排序，接下來介紹比較器排序。
還是之前的Student類，我們編寫測試代碼：
TreeSet<Student> treeSet = new TreeSet<Student>();
// 添加元素
Student s = new Student("liudehua", 30);
Student s2 = new Student("chenyixun", 32);
Student s3 = new Student("zhourunfa", 20);
Student s4 = new Student("gutianle", 40);
Student s5 = new Student("zhouxingchi", 29);
treeSet.add(s);
treeSet.add(s2);
treeSet.add(s3);
treeSet.add(s4);
treeSet.add(s5);
// 周遊
for (Student student : treeSet) {
System.out.println(student);
} 複制
此時運作程式會報錯，因為Student類沒有實作Comparable接口。
因為在TreeSet的構造方法中需要傳入一個Comparator的對象，而這是一個接口，是以我們自定義一個類實作該接口，那麼我們來實作一個需求，根據姓名長度進行排序：
public class MyComparator implements Comparator<Student> {
@Override
public int compare(Student o1, Student o2) {
//根據姓名長度
int num = o1.getName().length() - o2.getName().length();
//根據姓名内容
int num2 = num == 0 ? o1.getName().compareTo(o2.getName()) : num;
//根據年齡
int num3 = num2 == 0 ? o1.getAge() - o2.getAge() : num2;
return num3;
}
} 複制
編寫測試代碼：
TreeSet<Student> treeSet = new TreeSet<Student>(new MyComparator());
// 添加元素
Student s = new Student("liudehua", 30);
Student s2 = new Student("chenyixun", 32);
Student s3 = new Student("zhourunfa", 20);
Student s4 = new Student("gutianle", 40);
Student s5 = new Student("zhouxingchi", 29);
treeSet.add(s);
treeSet.add(s2);
treeSet.add(s3);
treeSet.add(s4);
treeSet.add(s5);
// 周遊
for (Student student : treeSet) {
System.out.println(student);
} 複制
運作結果：
Student [name=gutianle, age=40]
Student [name=liudehua, age=30]
Student [name=chenyixun, age=32]
Student [name=zhourunfa, age=20]
Student [name=zhouxingchi, age=29] 複制
也可以通過匿名内部類的方式實作。
希望這篇文章能夠使你更加深入地了解Set集合。