1. 類的特性

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

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

性能：

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

總結(jié)：

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

疑問(wèn)：

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

2. LinkedHashSet & LinkedHashMap

2.1 LinkedHashSet的實(shí)現(xiàn)如此簡(jiǎn)單

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

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

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

2.2 類圖

LinkedHashSet類的定義如下

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

類圖如下

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

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

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

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

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

巧妙之處來(lái)了：

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

也就是說(shuō)，LinkedHashSet中的 map 字段，實(shí)際為L(zhǎng)inkedHashMap類型

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

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

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

2.4 為何不支持訪問(wèn)順序？

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

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

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

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

3. 總結(jié)

關(guān)于LinkedHashSet

• 繼承HashSet類，巧妙的依靠Java的繼承與多態(tài)，建立起與LinkedHashMap之間的聯(lián)系
• 實(shí)際上，基于LinkedHashMap實(shí)現(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類一起，對(duì)照學(xué)習(xí)

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

最新評(píng)論