LinkedHashSet底层源码解析并给出代码示例

<think>我们正在讨论LinkedHashSet的底层实现原理。根据之前对HashSet的分析，我们知道HashSet是基于HashMap实现的。那么LinkedHashSet呢？ 实际上，LinkedHashSet是HashSet的子类，它通过维护一个双向链表来保证元素的插入顺序或访问顺序（取决于构造参数）。在底层，LinkedHashSet使用LinkedHashMap来实现。 关键点： 1. LinkedHashSet继承自HashSet，但在构造时使用的是LinkedHashMap。 2. LinkedHashMap是HashMap的子类，它通过维护一个双向链表（即header和每个节点的before/after指针）来记录插入顺序或访问顺序。 3. 因此，LinkedHashSet具有可预测的迭代顺序，即按照元素插入的顺序进行迭代（或者按照最近最少使用的顺序，如果设置为访问顺序）。 下面我们详细解析： 一、内部结构 在LinkedHashSet中，实际存储结构是LinkedHashMap（而HashSet使用的是HashMap）。LinkedHashMap在HashMap的基础上增加了一个双向链表，用于记录节点的顺序。 二、工作机制 1. 当添加元素时，元素作为键被放入LinkedHashMap中，值则是固定的PRESENT（与HashSet相同）。 2. 在LinkedHashMap中，每个节点除了有HashMap中的next指针（用于解决哈希冲突的链表或红黑树）外，还有before和after指针，用于维护双向链表。 3. 这个双向链表定义了迭代顺序，默认是插入顺序（也可以设置为访问顺序，但LinkedHashSet只使用插入顺序）。 三、源码分析 我们来看LinkedHashSet的构造方法（部分源码）： ```java public class LinkedHashSet<E> extends HashSet<E> implements Set<E>, Cloneable, java.io.Serializable { // 构造方法 public LinkedHashSet() { super(16, .75f, true); // 调用HashSet的特定构造方法 } // ... 其他构造方法 } ``` 在HashSet中有一个专门为LinkedHashSet设计的构造方法： ```java // HashSet的构造方法（包私有，供LinkedHashSet使用） HashSet(int initialCapacity, float loadFactor, boolean dummy) { map = new LinkedHashMap<>(initialCapacity, loadFactor); } ``` 这个构造方法创建了一个LinkedHashMap实例，并赋值给map变量（在HashSet中定义的map）。 四、LinkedHashMap中的双向链表 LinkedHashMap.Entry类（继承自HashMap.Node）增加了两个指针：before和after。 ```java static class Entry<K,V> extends HashMap.Node<K,V> { Entry<K,V> before, after; Entry(int hash, K key, V value, Node<K,V> next) { super(hash, key, value, next); } } ``` 在LinkedHashMap中，维护了一个双向链表的头尾（通过head和tail指针）。每次插入新节点时，除了将其放入哈希表中，还会将其链接到双向链表的尾部。 五、迭代顺序 当我们迭代LinkedHashSet时，实际上是迭代这个双向链表，因此顺序是插入顺序。 六、代码示例 下面是一个使用LinkedHashSet的示例： ```java import java.util.LinkedHashSet; public class LinkedHashSetExample { public static void main(String[] args) { LinkedHashSet<String> linkedHashSet = new LinkedHashSet<>(); linkedHashSet.add("Apple"); linkedHashSet.add("Banana"); linkedHashSet.add("Orange"); linkedHashSet.add("Apple"); // 重复元素，不会被添加 // 遍历输出，顺序为添加顺序 for (String fruit : linkedHashSet) { System.out.println(fruit); } } } ``` 输出： ``` Apple Banana Orange ``` 七、性能特点 1. 由于需要维护双向链表，LinkedHashSet在插入和删除时比HashSet略慢（但常数时间）。 2. 迭代LinkedHashSet的时间与元素数量成正比（因为直接遍历双向链表），而HashSet的迭代时间则与桶的数量加上元素数量成正比（可能更慢）。 3. 因此，如果需要保持插入顺序，并且需要Set的特性，LinkedHashSet是一个很好的选择。 八、与HashSet对比 特性 | HashSet | LinkedHashSet ----|---------|-------------- 迭代顺序 | 无特定顺序 | 插入顺序 性能 | 插入、删除略快 | 插入、删除略慢（但仍是O(1)） 迭代性能 | 可能较慢（取决于桶的数量） | 较快（直接按链表顺序） 九、总结 LinkedHashSet通过继承HashSet并在底层使用LinkedHashMap，实现了元素按插入顺序排列的特性。其内部通过双向链表维护顺序，使得迭代时能够按照插入顺序输出元素。 引用说明：关于Java集合框架的底层实现，可以参考相关源码分析[^2][^3]。 §§相关问题§§ 1. LinkedHashSet如何实现按插入顺序迭代的？ 2. 在并发环境下使用LinkedHashSet需要注意什么？ 3. LinkedHashSet和TreeSet在排序机制上有何不同？ 4. 为什么LinkedHashSet的迭代性能比HashSet好？</think>### Java LinkedHashSet底层实现原理详解 LinkedHashSet是Java集合框架中独特的有序集合，它在HashSet的基础上添加了链表结构来维护插入顺序。下面从源码层面详细解析其实现原理。 --- #### 一、核心设计思想 LinkedHashSet继承自HashSet，但底层使用**LinkedHashMap**替代HashMap： ```java public class LinkedHashSet<E> extends HashSet<E> implements Set<E>, Cloneable, java.io.Serializable { // 构造方法显式调用父类特殊构造器 public LinkedHashSet() { super(16, .75f, true); // 关键参数：dummy=true } } ``` 在HashSet中对应的特殊构造器： ```java // HashSet内部构造器（包访问权限） HashSet(int initialCapacity, float loadFactor, boolean dummy) { map = new LinkedHashMap<>(initialCapacity, loadFactor); // 创建LinkedHashMap } ``` **设计核心**：通过LinkedHashMap同时实现： - 哈希表的$O(1)$访问效率 - 双向链表维护插入顺序 --- #### 二、底层数据结构 ##### 1. LinkedHashMap内部结构 ```java static class Entry<K,V> extends HashMap.Node<K,V> { Entry<K,V> before, after; // 双向链表指针 Entry(int hash, K key, V value, Node<K,V> next) { super(hash, key, value, next); } } ``` **双重结构**： 1. **哈希表**：解决桶定位（同HashMap） 2. **双向链表**：头尾指针维护顺序 ```java transient LinkedHashMap.Entry<K,V> head; // 链表头 transient LinkedHashMap.Entry<K,V> tail; // 链表尾 ``` ##### 2. 数据存储原理 | 集合元素 | 实际存储结构 | |----------|--------------| | "A" | `Entry(hash=65, key="A", value=PRESENT, next=null)`<br> `before→null, after→B` | | "B" | `Entry(hash=66, key="B", value=PRESENT, next=null)`<br> `before→A, after→C` | | "C" | `Entry(hash=67, key="C", value=PRESENT, next=null)`<br> `before→B, after→null` | --- #### 三、核心操作源码分析 ##### 1. 元素添加（覆盖HashMap方法） ```java // LinkedHashMap中重写的方法 void afterNodeAccess(Node<K,V> e) { // 将访问的节点移动到链表末尾（LRU特性） } void afterNodeInsertion(boolean evict) { // 新节点插入链表尾部 LinkedHashMap.Entry<K,V> last = tail; if (last != null) { e.before = last; last.after = e; } tail = e; // 更新尾指针 } ``` ##### 2. 迭代器实现 ```java abstract class LinkedHashIterator { LinkedHashMap.Entry<K,V> next; // 下一个节点 LinkedHashMap.Entry<K,V> current; // 当前节点 LinkedHashIterator() { next = head; // 从头节点开始迭代 } final LinkedHashMap.Entry<K,V> nextNode() { LinkedHashMap.Entry<K,V> e = next; // 沿着after指针遍历 next = e.after; return e; } } ``` **迭代顺序**：严格遵循插入顺序（`head → tail`） --- #### 四、完整使用示例 ```java import java.util.LinkedHashSet; public class LinkedHashSetDemo { public static void main(String[] args) { LinkedHashSet<String> cities = new LinkedHashSet<>(); // 添加元素（保持插入顺序） cities.add("Beijing"); cities.add("Shanghai"); cities.add("Guangzhou"); cities.add("Shenzhen"); cities.add("Beijing"); // 重复元素被忽略 System.out.println("迭代顺序: " + cities); // 输出: [Beijing, Shanghai, Guangzhou, Shenzhen] // 删除中间元素 cities.remove("Shanghai"); System.out.println("删除后: " + cities); // 输出: [Beijing, Guangzhou, Shenzhen] // 按插入顺序迭代 System.out.println("遍历结果:"); for (String city : cities) { System.out.println("→ " + city); } /* 输出: → Beijing → Guangzhou → Shenzhen */ } } ``` --- #### 五、性能特性分析 | 操作 | 时间复杂度 | 说明 | |--------------|------------|--------------------------| | `add()` | $O(1)$ | 哈希定位+链表尾部插入 | | `remove()` | $O(1)$ | 哈希定位+链表节点移除 | | `contains()` | $O(1)$ | 哈希表桶定位 | | 迭代 | $O(n)$ | 直接遍历链表（优于HashSet）| **内存开销**：比HashSet多~12字节/元素（存储before/after指针） --- #### 六、应用场景 1. **需要保持插入顺序的去重集合** ```java void processLogs(List<String> logs) { Set<String> uniqueLogs = new LinkedHashSet<>(logs); // 按出现顺序处理去重后的日志 } ``` 2. **实现LRU缓存基础** ```java // 设置accessOrder=true可实现访问顺序 LinkedHashMap<String, Object> lruMap = new LinkedHashMap<>(16, 0.75f, true) { @Override protected boolean removeEldestEntry(Map.Entry eldest) { return size() > MAX_ENTRIES; } }; ``` --- #### 七、与相关集合对比 | 特性 | HashSet | LinkedHashSet | TreeSet | |--------------------|---------|---------------|---------------| | 迭代顺序 | 无 | **插入顺序** | 排序顺序 | | 底层结构 | 哈希表 | **哈希表+链表** | 红黑树 | | `contains()`效率 | $O(1)$ | $O(1)$ | $O(\log n)$ | | 内存开销 | 最小 | 中等 | 较大 | | 是否保序 | ❌ | **✅** | ✅（排序顺序） | > **设计启示**：LinkedHashSet通过组合哈希表和双向链表，在保持$O(1)$操作效率的同时实现顺序维护，是典型的**空间换时间**设计[^2][^3]。