【集合框架LinkedHashSet底层原理】

本文主要介绍集合框架Set接口下的实现类LinkedHashSet底层添加元素机制。

首先，Set接口下的集合的特点一般有三个：无序、不可重复、无索引。

其三个实现类的特点也各有异同

我们也可以再次回顾以前的单列集合体系，以确保我们将这些结构熟记于心。

那么LinkedHashSet为什么是：有序、不重复、无索引

不重复和无索引，我在上一篇文章中已经介绍过了，详情请参考HashSet底层原理

这里我们主要介绍为什么是有序的，注意这里的有序是指：保证存储和取出的元素顺序一致

底层原理：底层数据结构依然是哈希表，只是每个元素额外多了一个双链表的机制记录存储的顺序。

1、如何存储？

-> 首先，1号元素经过计算哈希值后存入8索引形成头节点

-> 2号元素经过计算存入3索引

-> 接下来1号元素和2号元素会互相记录对方的地址值，从而形成了一个双链表

-> 然后3号元素经过计算也是3索引，然后经过equals方法比较后确认对象内部属性不一致，则按照JDK8以后的规则采用尾插法挂至2号元素下面并且2、3元素互相记录地址值，

-> 此时双链表为1 <-> 2 <-> 3

-> 经过最后4号元素存储完之后，最终为1 <-> 2 <-> 3 <-> 4

-> 此时所有元素全部存入

2、如何遍历？

-> 按照从头节点到尾节点的顺序进行遍历

-> 从而与插入顺序保持的一致，也验证了LinkedHashSet的有序

存疑，如果形成了环会不会影响遍历？

解答：

场景：元素1存到了索引5，元素2、3存到了索引3，元素4、5存到了索引1，此时双链表为1-2-3-4-5，但是元素6经过计算也存到了索引3，那么按说应该是元素5和元素6进行连接，但是又因为元素6也在索引3，索引3已经挂了元素2、3，那么此时索引3下是2 - 3 - 6，但是可以明显的看到一个环：3 - 4 - 5 - 6。

1. LinkedHashSet 的双重结构

LinkedHashSet 实际上是：

• 一个 HashMap（用于快速查找，解决哈希冲突的拉链法）
• 一个双向链表（维护插入顺序）

当你描述 "索引3挂了元素2、3" 时，你指的是 HashMap 的桶（bucket）里通过链表（或红黑树）挂载了多个哈希冲突的元素。但 LinkedHashSet 的 双向链表 是独立于 HashMap 的冲突链表的。

2. 你的场景分析

假设当前状态：

• 哈希表结构：
  • 桶1：4 → 5
  • 桶3：2 → 3
  • 桶5：1
• 双向链表：1 → 2 → 3 → 4 → 5（严格按插入顺序）

现在插入 元素6，假设它哈希到桶3（与 2、3 冲突）。此时：

1. HashMap 会将 6 添加到桶3的链表/树中（比如 2 → 3 → 6）。
2. 双向链表 会忽略哈希冲突，直接按插入顺序将 6 链接到当前链表末尾：
   • 原链表：1 → 2 → 3 → 4 → 5
   • 新链表：1 → 2 → 3 → 4 → 5 → 6 （与 5 连接，和 3 无关！）

3. 关键结论

• 哈希冲突的链表（如桶3的 2 → 3 → 6）和 维护顺序的双向链表（1 → 2 → 3 → 4 → 5 → 6）是两条独立的链。
• 双向链表仅按插入顺序连接元素，完全不受哈希冲突的影响。无论元素哈希到哪个桶，双向链表都会严格按插入顺序串联所有元素。
• 因此，LinkedHashSet 不会因为哈希冲突形成环。

4. 源码佐证（Java 8）

在 java.util.LinkedHashMap（LinkedHashSet 的底层实现）中：

• 每个节点除了 next 指针（解决哈希冲突），还有 before/after 指针（维护双向链表）。
• 插入新元素时，会先处理哈希冲突（HashMap 的逻辑），再将其追加到双向链表尾部：

// LinkedHashMap.Entry 结构
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);
    }
}

// 插入时链接到双向链表尾部
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
    LinkedHashMap.Entry<K,V> last = tail;
    tail = p;
    if (last == null)
        head = p;
    else {
        p.before = last;
        last.after = p;
    }
}

5. 你的误解

你混淆了两种链表：

1. 哈希冲突链表：属于 HashMap 的拉链法结构，同一个桶内的元素用单向链表连接（如 2 → 3 → 6）。
2. 双向链表：属于 LinkedHashSet 的顺序维护结构，所有元素按插入顺序用双向链表连接（如 1 → 2 → 3 → 4 → 5 → 6）。

它们互不干扰，因此不会形成环。