深入Java源碼剖析之Set集合
- 2020 年 2 月 14 日
- 筆記
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集合。
