浅析Java集合中的LinkedHashSet

1. 类的特性

LinkedHashSet的类注释，提供了以下信息

LinkedHashSet基于哈希表和链表实现了Set接口
- 允许有且只有一个null值
- 在所有的元素中维护了一个双向链表，可以维护元素的插入顺序

性能：

与HashSet一样，在散列均匀的情况下，基本操作（add、remove、contains）的时间复杂度为O ( 1 ) O(1)O(1)
但实际性能稍逊于HashSet，因为维护元素间的双向链表需要一定的开销。
LinkedHashSet元素的遍历，不再基于桶，而是基于链表，遍历时间与元素个数成正比
LinkedHashSet是非线程安全的，多线程访问，可以使用Collections.synchronizedSet()将其转为线程安全的set类型
使用fail-fast 迭代器，一旦创建好迭代器，除非使用迭代器自身的remove方法，其他任何修改结构的方法，都将触发迭代器抛出ConcurrentModificationException 异常

总结：

使用哈希表加（双向）链表的结构，允许null值，可以维护元素的插入顺序
基本操作的性能为O ( 1 ) O(1)O(1)，遍历是基于链表而非桶
非线程安全，使用fail-fast 迭代器

疑问：

回想其余set类实现，LinkedHashSet应该是基于LinkedHashMap实现的。
为何类注释中，没有说LinkedHashSet支持访问顺序呢？
只是说，通过双向链表维护了元素的插入顺序

2. LinkedHashSet & LinkedHashMap

2.1 LinkedHashSet的实现如此简单

查看LinkedHashSet源码，其结构如下

除了构造函数，没有常见的set类的关键方法，甚至没有成员变量

让人感觉很神奇，为何实现如此简单？

2.2 类图

LinkedHashSet类的定义如下

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

类图如下

查看LinkedHashMap的类图，二者非常相似，简直是照葫芦画瓢

2.3 关联分析

LinkedHashMap基于HashMap实现，对一些关键方法进行了重写，从而在所有的entry中维护一个双向链表
HashSet基于HashMap实现，存在一个default构造函数，使用子类LinkedHashMap初始化HashMap
- dummy入参：无意义的参数，只是为了实现重载，与其他的构造函数相区别

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

从Java的多态可知，通过该构造函数初始化的 map 字段，实际执行时将调用子类LinkedHashMap的相关方法

巧妙之处来了：

LinkedHashSet的构造函数，实际都调用HashSet的上述 default 构造函数

也就是说，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);
}
// 使用默认值构建一个空set
public LinkedHashSet() {
    super(16, .75f, true);
}
// 基于指定的元素构建一个set
public LinkedHashSet(Collection<? extends E> c) {
    super(Math.max(2*c.size(), 11), .75f, true);
    addAll(c);
}

2.4 为何不支持访问顺序？

从HashSet的 default 构造函数可以看出，构建的LinkedHashMap将默认使用插入顺序

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

因此，基于LinkedHashMap的LinkedHashSet，也将使用插入顺序

没有其他的构造函数可以提供一个具有访问顺序的LinkedHashMap，LinkedHashSet自然也不会支持访问顺序

3. 总结

关于LinkedHashSet

继承HashSet类，巧妙的依靠Java的继承与多态，建立起与LinkedHashMap之间的联系
实际上，基于LinkedHashMap实现了Set接口

与HashSet的区别

最大的区别：元素是有序的，支持插入顺序
先学习List类：ArrayList、Vector、LinkedList
再学习Map类：TreeMap（先学习红黑树）、HashMap、LinkedHashMap
最后学习Set类：TreeSet、HashSet、LinkedHashSet；与上述Map类一起，对照学习

您可能感兴趣的文章:

全部栏目