LinkedHashSet 源码解析

简介

LinkedHashSet 继承自 HashSet，在保持「元素不可重复」的同时，维护了元素的插入顺序（迭代顺序 == 插入顺序）。

它的实现与 HashSet 几乎一样「偷懒」：底层包装的是 LinkedHashMap（accessOrder = false），利用 LinkedHashMap 的双向链表来记录插入次序。

• 不是线程安全的。
• 允许一个 null，去重同样依赖 hashCode() / equals()。
• 与 HashSet 相比多了「保序」能力，但内存占用略高（要维护链表指针）。

若想实现「访问顺序（LRU）」的 Set，标准库没有现成类，可基于 LinkedHashMap 自己实现（类似 LinkedHashMap 实现 LRU 的思路）。

底层数据结构分析

LinkedHashSet 自身没有任何新字段，唯一的区别在构造器：HashSet 提供了一个包级私有构造，让它创建的是 LinkedHashMap 而非 HashMap。

// HashSet 的包级私有构造：dummy 参数仅用于区分，真正的逻辑是创建 LinkedHashMap
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
    map = new LinkedHashMap<>(initialCapacity, loadFactor);
}

LinkedHashSet 正是调用了上面的构造：

public LinkedHashSet(int initialCapacity, float loadFactor) {
    super(initialCapacity, loadFactor, true); // 第三个参数 true 触发 LinkedHashMap
}

于是 add / remove / contains 与 HashSet 完全一致，只是底层从 HashMap 换成了 LinkedHashMap，迭代时会按双向链表顺序输出。

核心成员变量

// 没有新增字段，全部复用父类 HashSet 的 map（实际是 LinkedHashMap 实例）
// private transient HashMap<E,Object> map;

源码分析

写入：add

add 完全继承自 HashSet（委托给 LinkedHashMap.put）：

public boolean add(E e) {
    return map.put(e, PRESENT) == null; // map 实为 LinkedHashMap
}

因为 LinkedHashMap 在插入新 key 时会把它接到双向链表尾部，所以迭代时元素按插入顺序排列。

迭代顺序

// LinkedHashSet 的迭代直接复用 LinkedHashMap 的 keySet 顺序
public Iterator<E> iterator() {
    return map.keySet().iterator(); // 按链表顺序遍历
}

与 HashSet / TreeSet 的对比

维度	HashSet	LinkedHashSet	TreeSet
底层	HashMap	LinkedHashMap	TreeMap
顺序	无序	插入顺序	key 有序
允许 null	允许	允许	否（自然排序下）
复杂度	平均 O(1)	平均 O(1)	O(log n)

经典 Demo

import java.util.LinkedHashSet;

public class LinkedHashSetDemo {
    public static void main(String[] args) {
        LinkedHashSet<String> set = new LinkedHashSet<>();
        set.add("c"); set.add("a"); set.add("b");
        System.out.println(set); // [c, a, b] 严格保持插入顺序
    }
}