1. 類的特性

LinkedHashSet的類注釋，提供了以下信息

• LinkedHashSet基于哈希表和鏈表實現(xiàn)了Set接口
  • 允許有且只有一個null值
  • 在所有的元素中維護了一個雙向鏈表，可以維護元素的插入順序

性能：

• 與HashSet一樣，在散列均勻的情況下，基本操作（add、remove、contains）的時間復(fù)雜度為O ( 1 ) O(1)O(1)
• 但實際性能稍遜于HashSet，因為維護元素間的雙向鏈表需要一定的開銷。
• LinkedHashSet元素的遍歷，不再基于桶，而是基于鏈表，遍歷時間與元素個數(shù)成正比
• LinkedHashSet是非線程安全的，多線程訪問，可以使用Collections.synchronizedSet()將其轉(zhuǎn)為線程安全的set類型
• 使用fail-fast 迭代器，一旦創(chuàng)建好迭代器，除非使用迭代器自身的remove方法，其他任何修改結(jié)構(gòu)的方法，都將觸發(fā)迭代器拋出ConcurrentModificationException 異常

總結(jié)：

• 使用哈希表加（雙向）鏈表的結(jié)構(gòu)，允許null值，可以維護元素的插入順序
• 基本操作的性能為O ( 1 ) O(1)O(1)，遍歷是基于鏈表而非桶
• 非線程安全，使用fail-fast 迭代器

疑問：

• 回想其余set類實現(xiàn)，LinkedHashSet應(yīng)該是基于LinkedHashMap實現(xiàn)的。
• 為何類注釋中，沒有說LinkedHashSet支持訪問順序呢？
• 只是說，通過雙向鏈表維護了元素的插入順序

2. LinkedHashSet & LinkedHashMap

2.1 LinkedHashSet的實現(xiàn)如此簡單

查看LinkedHashSet源碼，其結(jié)構(gòu)如下

除了構(gòu)造函數(shù)，沒有常見的set類的關(guān)鍵方法，甚至沒有成員變量

讓人感覺很神奇，為何實現(xiàn)如此簡單？

2.2 類圖

LinkedHashSet類的定義如下

public class LinkedHashSet<E> extends HashSet<E>
    implements Set<E>, Cloneable, java.io.Serializable 

類圖如下

查看LinkedHashMap的類圖，二者非常相似，簡直是照葫蘆畫瓢

2.3 關(guān)聯(lián)分析

• LinkedHashMap基于HashMap實現(xiàn)，對一些關(guān)鍵方法進行了重寫，從而在所有的entry中維護一個雙向鏈表
• HashSet基于HashMap實現(xiàn)，存在一個default構(gòu)造函數(shù)，使用子類LinkedHashMap初始化HashMap
  • dummy入?yún)ⅲ簾o意義的參數(shù)，只是為了實現(xiàn)重載，與其他的構(gòu)造函數(shù)相區(qū)別

HashSet(int initialCapacity, float loadFactor, boolean dummy) {
    map = new LinkedHashMap<>(initialCapacity, loadFactor);
}

• 從Java的多態(tài)可知，通過該構(gòu)造函數(shù)初始化的 map 字段，實際執(zhí)行時將調(diào)用子類LinkedHashMap的相關(guān)方法

巧妙之處來了：

LinkedHashSet的構(gòu)造函數(shù)，實際都調(diào)用HashSet的上述 default 構(gòu)造函數(shù)

也就是說，LinkedHashSet中的 map 字段，實際為LinkedHashMap類型

這樣，所有entry之間就存在一個雙向鏈表，即LinkedHashSet的所有元素之間存在一個雙向鏈表

從而，LinkedHashSet中元素是有序的，為元素的插入順序

// 指定初始化容量和loadFactor的空set
public LinkedHashSet(int initialCapacity, float loadFactor) {
    super(initialCapacity, loadFactor, true);
}
// 指定初始化容量、使用默認loadFactor的空set
public LinkedHashSet(int initialCapacity) {
    super(initialCapacity, .75f, true);
}
// 使用默認值構(gòu)建一個空set
public LinkedHashSet() {
    super(16, .75f, true);
}
// 基于指定的元素構(gòu)建一個set
public LinkedHashSet(Collection<? extends E> c) {
    super(Math.max(2*c.size(), 11), .75f, true);
    addAll(c);
}

2.4 為何不支持訪問順序？

從HashSet的 default 構(gòu)造函數(shù)可以看出，構(gòu)建的LinkedHashMap將默認使用插入順序

HashSet(int initialCapacity, float loadFactor, boolean dummy) {
    map = new LinkedHashMap<>(initialCapacity, loadFactor);
}

因此，基于LinkedHashMap的LinkedHashSet，也將使用插入順序

沒有其他的構(gòu)造函數(shù)可以提供一個具有訪問順序的LinkedHashMap，LinkedHashSet自然也不會支持訪問順序

3. 總結(jié)

關(guān)于LinkedHashSet

• 繼承HashSet類，巧妙的依靠Java的繼承與多態(tài)，建立起與LinkedHashMap之間的聯(lián)系
• 實際上，基于LinkedHashMap實現(xiàn)了Set接口

與HashSet的區(qū)別

• 最大的區(qū)別：元素是有序的，支持插入順序
• 先學(xué)習(xí)List類：ArrayList、Vector、LinkedList
• 再學(xué)習(xí)Map類：TreeMap（先學(xué)習(xí)紅黑樹）、HashMap、LinkedHashMap
• 最后學(xué)習(xí)Set類：TreeSet、HashSet、LinkedHashSet；與上述Map類一起，對照學(xué)習(xí)

到此這篇關(guān)于淺析Java集合中的LinkedHashSet的文章就介紹到這了,更多相關(guān)Java的LinkedHashSet內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論