往期精選
原文:https://blog.csdn.net/learningcoding/article/details/79983248 作者:Yoda_wang
搞懂 HashSet & LinkedHashSet 源碼 以及集合常見面試題目
經(jīng)過上兩篇的 HashMap 和 LinkedHashMap 源碼分析以后，本文將繼續(xù)分析 JDK 集合之 Set 源碼，由于有了之前的 Map 源碼分析的鋪墊，Set 源碼就簡單很多了，本文的篇幅也將比之前短很多。查看 Set 源碼的構(gòu)造參數(shù)就可以知道，Set 內(nèi)部其實(shí)維護(hù)的就是一個(gè) Map，只是單單使用了 Entry 中的 key 。那么本文將不再贅述內(nèi)部數(shù)據(jù)結(jié)構(gòu)，而是通過部分的源碼，來說明兩個(gè) Set 集合與 Map 之間的關(guān)系。本文將從以下幾部分?jǐn)⑹觯?/p>
Set 集合概述 HashSet 源碼簡單分析 LinkedHashSet 源碼簡單分析 關(guān)于面試中的集合問題總結(jié)
Set 集合概述
圖片來自互聯(lián)網(wǎng)侵刪
由于本篇文章主要敘述 Set 容器以及和 Map 容器之間關(guān)系，我們只需要關(guān)注上述集合圖譜中 Set 部分?？梢钥闯?Set 主要的實(shí)現(xiàn)類有 HashSet 和 TreeSet 以及沒有畫出的 LinkedHashSet。其中 HashSet 的實(shí)現(xiàn)依賴于 HashMap， TreeSet 的實(shí)現(xiàn)依賴于 TreeMap，LinkedHashSet 的實(shí)現(xiàn)依賴于 LinkedHashMap。
從各個(gè)實(shí)現(xiàn)類的聲明也可以看出其繼承關(guān)系 public class HashSetE>
extends AbstractSetE>
implements SetE>, Cloneable, java.io.Serializable
public class LinkedHashSetE>
extends HashSetE>
implements SetE>, Cloneable, java.io.Serializable
public class TreeSetE> extends AbstractSetE>
implements NavigableSetE>, Cloneable, java.io.Serializable
在看 Set 的之前，我們先概括的說下 Set 集合的特點(diǎn) 1.HashSet 底層是數(shù)組 + 單鏈表 + 紅黑樹的數(shù)據(jù)結(jié)構(gòu) 2.LinkedHashSet 底層是 數(shù)組 + 單鏈表 + 紅黑樹 + 雙向鏈表的數(shù)據(jù)結(jié)構(gòu) 3.Set 不允許存儲(chǔ)重復(fù)元素，允許存儲(chǔ) null 4.HashSet 存儲(chǔ)元素是無序且不等于訪問順序 5.LinkedHashSet 存儲(chǔ)元素是無序的，但是由于雙向鏈表的存在，迭代時(shí)獲取元素的順序等于元素的添加順序，注意這里不是訪問順序 HashSet 的源碼分析HashSet 源碼只有短短的 300 行，上文也闡述了實(shí)現(xiàn)依賴于 HashMap，這一點(diǎn)充分體現(xiàn)在其構(gòu)造方法和成員變量上。我們來看下 HashSet 的構(gòu)造方法和成員變量： // HashSet 真實(shí)的存儲(chǔ)元素結(jié)構(gòu)
private transient HashMap map;
// 作為各個(gè)存儲(chǔ)在 HashMap 元素的鍵值對中的 Value
private static final Object PRESENT = new Object();
//空參數(shù)構(gòu)造方法 調(diào)用 HashMap 的空構(gòu)造參數(shù)
//初始化了 HashMap 中的加載因子 loadFactor = 0.75f
public HashSet() {
map = new HashMap<>();
}
//指定期望容量的構(gòu)造方法
public HashSet(int initialCapacity) {
map = new HashMap<>(initialCapacity);
}
//指定期望容量和加載因子
public HashSet(int initialCapacity, float loadFactor) {
map = new HashMap<>(initialCapacity, loadFactor);
}
//使用指定的集合填充Set
public HashSet(Collection c) {
//調(diào)用 new HashMap<>(initialCapacity) 其中初始期望容量為 16 和 c 容量 / 默認(rèn) load factor 后 + 1的較大值
map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
addAll(c);
}
// 該方法為 default 訪問權(quán)限，不允許使用者直接調(diào)用，目的是為了初始化 LinkedHashSet 時(shí)使用
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<>(initialCapacity, loadFactor);
}
通過 HashSet 的構(gòu)造參數(shù)我們可以看出每個(gè)構(gòu)造方法，都調(diào)用了對應(yīng)的 HashMap 的構(gòu)造方法用來初始化成員變量 map ，因此我們可以知道，HashSet 的初始容量也為 1<> 即16，加載因子默認(rèn)也是 0.75f。 我們都知道 Set 不允許存儲(chǔ)重復(fù)元素，又由構(gòu)造參數(shù)得出結(jié)論底層存儲(chǔ)結(jié)構(gòu)為 HashMap,那么這個(gè)不可重復(fù)的屬性必然是有 HashMap 中存儲(chǔ)鍵值對的 Key 來實(shí)現(xiàn)了。在分析 HashMap 的時(shí)候，提到過 HashMap 通過存儲(chǔ)鍵值對的 Key 的 hash 值（經(jīng)過擾動(dòng)函數(shù)hash()處理后）來決定鍵值對在哈希表中的位置，當(dāng) Key 的 hash 值相同時(shí)，再通過 equals 方法判讀是否是替換原來對應(yīng) key 的 Value 還是存儲(chǔ)新的鍵值對。那么我們在使用 Set 方法的時(shí)候也必須保證，存儲(chǔ)元素的 HashCode 方法以及 equals 方法被正確覆寫。 HashSet 中的添加元素的方法也很簡單，我們來看下實(shí)現(xiàn)： public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
可以看出 add 方法調(diào)用了 HashMap 的 put 方法，構(gòu)造的鍵值對的 key 為待添加的元素，而 Value 這時(shí)有全局變量 PRESENT來充當(dāng)，這個(gè)PRESENT只是一個(gè) Object 對象。 除了 add 方法外 HashSet 實(shí)現(xiàn)了 Set 接口中的其他方法這些方法有： public int size() {
return map.size();
}
public boolean isEmpty() {
return map.isEmpty();
}
public boolean contains(Object o) {
return map.containsKey(o);
}
//調(diào)用 remove(Object key) 方法去移除對應(yīng)的鍵值對
public boolean remove(Object o) {
return map.remove(o)==PRESENT;
}
public void clear() {
map.clear();
}
// 返回一個(gè) map.keySet 的 HashIterator 來作為 Set 的迭代器
public Iterator iterator() {
return map.keySet().iterator();
}
關(guān)于迭代器我們在講解 HashMap 中的時(shí)候沒有詳細(xì)列舉，其實(shí) HashMap 提供了多種迭代方法，每個(gè)方法對應(yīng)了一種迭代器，這些迭代器包括下述幾種，而 HashSet 由于只關(guān)注 Key 的內(nèi)容，所以使用 HashMap 的內(nèi)部類 KeySet 返回了一個(gè) KeyIterator ，這樣在調(diào)用 next 方法的時(shí)候就可以直接獲取下個(gè)節(jié)點(diǎn)的 key 了。
//HashMap 中的迭代器
final class KeyIterator extends HashIterator
implements IteratorK> {
public final K next() { return nextNode().key; }
}
final class ValueIterator extends HashIterator
implements IteratorV> {
public final V next() { return nextNode().value; }
}
final class EntryIterator extends HashIterator
implements IteratorMap.EntryK,V>> {
public final Map.Entry next() { return nextNode(); }
}
關(guān)于 HashSet 中的源碼分析就這些，其實(shí)除了一些序列化和克隆的方法以外，我們已經(jīng)列舉了所有的 HashSet 的源碼，有沒有感覺巨簡單，其實(shí)下面的 LinkedHashSet 由于繼承自 HashSet 使得其代碼更加簡單只有短短100多行不信繼續(xù)往下看。 
LinkedHashSet 源碼分析在上述分析 HashSet 構(gòu)造方法的時(shí)候，有一個(gè) default 權(quán)限的構(gòu)造方法沒有講，只說了其跟 LinkedHashSet 構(gòu)造有關(guān)系，該構(gòu)造方法內(nèi)部調(diào)用的是 LinkedHashMap 的構(gòu)造方法。 LinkedHashMap 較之 HashMap 內(nèi)部多維護(hù)了一個(gè)雙向鏈表用來維護(hù)元素的添加順序： // dummy 參數(shù)沒有作用這里可以忽略
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<>(initialCapacity, loadFactor);
}
//調(diào)用 LinkedHashMap 的構(gòu)造方法，該方法初始化了初始起始容量，以及加載因子，
//accessOrder = false 即迭代順序不等于訪問順序
public LinkedHashMap(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor);
accessOrder = false;
}
LinkedHashSet的構(gòu)造方法一共有四個(gè)，統(tǒng)一調(diào)用了父類的 HashSet(int initialCapacity, float loadFactor, boolean dummy)構(gòu)造方法。
//初始化 LinkedHashMap 的初始容量為誒 16 加載因子為 0.75f
public LinkedHashSet() {
super(16, .75f, true);
}
//初始化 LinkedHashMap 的初始容量為 Math.max(2*c.size(), 11) 加載因子為 0.75f
public LinkedHashSet(Collection c) {
super(Math.max(2*c.size(), 11), .75f, true);
addAll(c);
}
//初始化 LinkedHashMap 的初始容量為參數(shù)指定值 加載因子為 0.75f
public LinkedHashSet(int initialCapacity) {
super(initialCapacity, .75f, true);
}
//初始化 LinkedHashMap 的初始容量,加載因子為參數(shù)指定值
public LinkedHashSet(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor, true);
}
完了..沒錯(cuò)，LinkedHashSet 源碼就這幾行，所以可以看出其實(shí)現(xiàn)依賴于 LinkedHashMap 內(nèi)部的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)。 關(guān)于面試中的集合問題總結(jié)之前分析了多篇關(guān)于 JDK 集合源碼的文章，而這些集合源碼中的知識(shí)點(diǎn)都是面試的時(shí)候?？?，因此在本篇結(jié)尾作為 “充數(shù)” 的一節(jié)，我們來以面試題的形式總結(jié)一下之前所分過的源碼中的知識(shí)點(diǎn)，這些知識(shí)點(diǎn)在之前的文章中都有詳細(xì)的分析，如果有疑問可以回顧一下之前的源碼分析文章。 ArrayList 與 LinkedList 區(qū)別 ? 1.存儲(chǔ)結(jié)構(gòu)上 ArrayList 底層使用數(shù)組進(jìn)行元素的存儲(chǔ)，LinkedList 使用雙向鏈表作為存儲(chǔ)結(jié)構(gòu)。 2.兩者均與允許存儲(chǔ) null 也允許存儲(chǔ)重復(fù)元素。 3.在性能上 ArrayList 在存儲(chǔ)大量元素時(shí)候的增刪效率 平均低于 LinkedList，因?yàn)?ArrayList 在增刪的是需要拷貝元素到新的數(shù)組，而 LinkedList 只需要將節(jié)點(diǎn)前后指針指向改變。 4.在根據(jù)角標(biāo)獲取元素的時(shí)間效率上ArrayList優(yōu)于 LinkedList，因?yàn)閿?shù)組本身有存儲(chǔ)連續(xù)，有 index 角標(biāo)，而 LinkedList 存儲(chǔ)元素離散，需要遍歷鏈表。 5.不要使用 for 循環(huán)去遍歷 LinkedList 因?yàn)樾屎艿汀?/p> 6.兩者都是線程不安全的，都可以使用 Collections.synchronizedList(List list) 方法生成一個(gè)線程安全的 List。 ArrayList 與 Vector 區(qū)別（為什么要用Arraylist取代Vector呢？） 1.ArrayList 的擴(kuò)容機(jī)制由于 Vector ， ArrayList 每次 resize 增加 1.5 倍的容量，Vector 每次增加 2倍的容量，在存儲(chǔ)大量元素后擴(kuò)容的時(shí)候就能有很大的空間節(jié)省。 2.Vector 添加刪除方法以及迭代器遍歷的方法都是 synchronized 修飾的方法，在線程安全的情況下使用效率低于 ArrayList 3.ArrayList 和 LinkedList 通過Collections.synchronizedList(List list) 的線程同步的集合，迭代器并不同步，需要使用者去加鎖。 簡述 HashMap 的工作原理 JDK 1.8后做了哪些優(yōu)化 1.JDK 1.7 HashMap 底層采用單鏈表 + 數(shù)組的存儲(chǔ)結(jié)構(gòu)存儲(chǔ)元素（鍵值對）。JDK1.8之后 HashMap 在同一哈希桶中節(jié)點(diǎn)數(shù)量（單鏈表長度）超過 8之后會(huì)使用 紅黑樹替換單鏈表來提高效率 2.HashMap 通過鍵值對的 key 的 hashCode 值經(jīng)過擾動(dòng)函數(shù)處理后確定存儲(chǔ)的數(shù)組角標(biāo)位置，1.7 中擾動(dòng)函數(shù)使用了 4次位運(yùn)算 + 5次異或運(yùn)算，1.8 中降低到 1次位運(yùn)算 + 1次異或運(yùn)運(yùn)算 3.HashMap 擴(kuò)容的時(shí)候會(huì)增加原來數(shù)組長度兩倍，并對所存儲(chǔ)的元素節(jié)點(diǎn)hash 值的重新計(jì)算，1.7中 HashMap 會(huì)重新調(diào)用 hash 函數(shù)計(jì)算新的位置，而 1.8中對此進(jìn)行了優(yōu)化通過 (e.hash & oldCap) == 0 來確定節(jié)點(diǎn)新位置是位于擴(kuò)容前的角標(biāo)還是之前的 2倍角標(biāo)位置。 4.HashMap 在多線程使用前提下，擴(kuò)容的時(shí)候可能會(huì)導(dǎo)致循環(huán)鏈表的情況，當(dāng)然我們不應(yīng)在線程不安全的情況下使用 HashMap HashMap 和 HashTable 的區(qū)別 1.HashMap 是線程不安全的，HashTable是線程安全的。 2.HashMap 允許 key 和 Vale 是 null，但是只允許一個(gè) key 為 null,且這個(gè)元素存放在哈希表 0 角標(biāo)位置。 HashTable 不允許key、value 是 null 3.HashMap 內(nèi)部使用hash(Object key)擾動(dòng)函數(shù)對 key 的 hashCode 進(jìn)行擾動(dòng)后作為 hash 值。HashTable 是直接使用 key 的 hashCode() 返回值作為 hash 值。 4.HashMap默認(rèn)容量為 2^4 且容量一定是 2^n ; HashTable 默認(rèn)容量是11,不一定是 2^n 5.HashTable 取哈希桶下標(biāo)是直接用模運(yùn)算,擴(kuò)容時(shí)新容量是原來的2倍+1。HashMap 在擴(kuò)容的時(shí)候是原來的兩倍，且哈希桶的下標(biāo)使用 &運(yùn)算代替了取模。 HashMap 和 LinkedHashMap 的區(qū)別 1.LinkedHashMap 擁有與 HashMap 相同的底層哈希表結(jié)構(gòu)，即數(shù)組 + 單鏈表 + 紅黑樹，也擁有相同的擴(kuò)容機(jī)制。 2.LinkedHashMap 相比 HashMap 的拉鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，內(nèi)部額外通過 Entry 維護(hù)了一個(gè)雙向鏈表。 3.HashMap 元素的遍歷順序不一定與元素的插入順序相同，而 LinkedHashMap 則通過遍歷雙向鏈表來獲取元素，所以遍歷順序在一定條件下等于插入順序。 4.LinkedHashMap 可以通過構(gòu)造參數(shù) accessOrder 來指定雙向鏈表是否在元素被訪問后改變其在雙向鏈表中的位置。 HashSet 如何檢查重復(fù),與 HashMap 的關(guān)系？ 1.HashSet 內(nèi)部使用 HashMap 存儲(chǔ)元素，對應(yīng)的鍵值對的鍵為 Set 的存儲(chǔ)元素，值為一個(gè)默認(rèn)的 Object 對象。 2.HashSet 通過存儲(chǔ)元素的 hashCode 方法和 equals 方法來確定元素是否重復(fù)。 是否了解 fast-fail 規(guī)則 簡單說明一下 1.快速失?。╢ail—fast）在用迭代器遍歷一個(gè)集合對象時(shí)，如果遍歷過程中集合對象中的內(nèi)容發(fā)生了修改（增加、刪除、修改），則會(huì)拋出ConcurrentModificationException。 2.迭代器在遍歷時(shí)直接訪問集合中的內(nèi)容，并且在遍歷過程中使用一個(gè) modCount 變量。集合在被遍歷期間如果內(nèi)容發(fā)生變化，就會(huì)改變 modCount 的值。每當(dāng)?shù)魇褂?code>hasNext()/next() 遍歷下一個(gè)元素之前，都會(huì)檢測 modCount 變量是否為expectedmodCount 值，是的話就返回遍歷值；否則拋出異常，終止遍歷。 3.場景：java.util包下的集合類都是快速失敗的，不能在多線程下發(fā)生并發(fā)修改（迭代過程中被修改）。 集合在遍歷過程中是否可以刪除元素，為什么迭代器就可以安全刪除元素 1.集合在使用 for 循環(huán)或者高級(jí) for 循環(huán)迭代的過程中不允許使用，集合本身的 remove 方法刪除元素，如果進(jìn)行錯(cuò)誤操作將會(huì)導(dǎo)致 ConcurrentModificationException異常的發(fā)生 2.Iterator 可以刪除訪問的當(dāng)前元素(current)，一旦刪除的元素是Iterator 對象中 next 所正在引用的，在 Iterator 刪除元素通過 修改 modCount 與 expectedModCount 的值，可以使下次在調(diào)用 remove 的方法時(shí)候兩者仍然相同因此不會(huì)有異常產(chǎn)生。
總結(jié)本文分析了 JDK 中 HashSet 和 LinkedHashSet 的源碼實(shí)現(xiàn)，闡述了Set 與 Map 的關(guān)系，也通過最后一節(jié)的面試題總結(jié)復(fù)習(xí)了一下之前幾篇源碼分析文章的知識(shí)點(diǎn)。之后可能會(huì)繼續(xù)分析一下 Android 中特有的 ArrayMap 和 SparseArray 源碼分析。
|
