编辑“︁Java Linkedhashset”︁

{{Note|本条目是[[Java集合框架]]系列的一部分，介绍'''LinkedHashSet'''的实现原理与使用方法。}}

== 概述 ==
'''LinkedHashSet'''是Java集合框架中一个有序的哈希表实现，继承自[[HashSet]]并实现了[[Set]]接口。其核心特性为：
* 保留元素插入顺序（与[[LinkedList]]类似）
* 不允许重复元素（遵循Set接口契约）
* 基于哈希表+双向链表实现（Java 8后采用数组+链表+红黑树结构）

其类继承关系如下：
<mermaid>
classDiagram
    Set <|-- HashSet
    HashSet <|-- LinkedHashSet
    class Set {
        <<interface>>
        +add(e E): boolean
        +remove(o Object): boolean
    }
    class HashSet {
        -table: Node[]
        +iterator(): Iterator
    }
    class LinkedHashSet {
        -head: Entry
        -tail: Entry
    }
</mermaid>

== 实现原理 ==
LinkedHashSet通过组合两种数据结构实现：
# '''哈希表'''：底层使用[[HashMap]]存储元素（实际是[[LinkedHashMap]]）
# '''双向链表'''：维护元素插入顺序

当元素被插入时，会同时加入哈希表和链表：
<mermaid>
flowchart LR
    A[插入元素X] --> B[计算hash值]
    B --> C{是否已存在?}
    C -->|否| D[存入哈希表]
    D --> E[加入链表尾部]
    C -->|是| F[放弃操作]
</mermaid>

数学表达其时间复杂度为：
* 插入/删除/查找：平均<math>O(1)</math>，最坏<math>O(n)</math>
* 遍历：<math>O(n)</math>

== 基础用法 ==
=== 构造方法 ===
<syntaxhighlight lang="java">
// 1. 默认构造（初始容量16，负载因子0.75）
LinkedHashSet<String> set1 = new LinkedHashSet<>();

// 2. 指定初始容量
LinkedHashSet<Integer> set2 = new LinkedHashSet<>(32);

// 3. 指定初始容量和负载因子
LinkedHashSet<Double> set3 = new LinkedHashSet<>(64, 0.6f);

// 4. 从其他集合创建
List<String> list = Arrays.asList("A", "B", "C");
LinkedHashSet<String> set4 = new LinkedHashSet<>(list);
</syntaxhighlight>

=== 基本操作示例 ===
<syntaxhighlight lang="java">
LinkedHashSet<String> colors = new LinkedHashSet<>();
colors.add("Red");    // true
colors.add("Green");  // true
colors.add("Blue");   // true
colors.add("Red");    // false（重复元素）

System.out.println(colors); // 输出顺序与插入顺序一致
// 输出: [Red, Green, Blue]

colors.remove("Green");
System.out.println(colors.contains("Green")); // false
</syntaxhighlight>

== 高级特性 ==
=== 顺序访问保证 ===
LinkedHashSet提供两种顺序保证：
# '''插入顺序'''（默认）
# '''访问顺序'''（需使用特殊构造方法）

<syntaxhighlight lang="java">
// 访问顺序示例（元素被访问后会移动到链表末尾）
LinkedHashSet<String> accessOrderSet = new LinkedHashSet<>(16, 0.75f, true);
accessOrderSet.addAll(Arrays.asList("A", "B", "C"));

accessOrderSet.contains("B"); // 访问B
System.out.println(accessOrderSet); // [A, C, B]
</syntaxhighlight>

=== 性能调优 ===
重要参数对比表：
{| class="wikitable"
|-
! 参数 !! 默认值 !! 影响
|-
| 初始容量 || 16 || 减少扩容次数
|-
| 负载因子 || 0.75 || 空间与时间的权衡
|-
| 访问顺序 || false || 改变迭代顺序
|}

优化建议：
* 预估元素数量时指定初始容量
* 高查询频率场景可降低负载因子
* 遍历操作多时考虑普通HashSet

== 实际应用案例 ==
=== 网页访问记录 ===
<syntaxhighlight lang="java">
// 记录用户最近访问的10个唯一URL
public class RecentUrlTracker {
    private static final int MAX_URLS = 10;
    private LinkedHashSet<String> urls = new LinkedHashSet<>(MAX_URLS, 0.75f, true);

    public void visit(String url) {
        if (urls.size() >= MAX_URLS) {
            String oldest = urls.iterator().next();
            urls.remove(oldest);
        }
        urls.add(url);
    }

    public List<String> getRecentUrls() {
        return new ArrayList<>(urls);
    }
}
</syntaxhighlight>

=== 数据去重并保留顺序 ===
<syntaxhighlight lang="java">
// 从日志文件中提取唯一错误码（保留首次出现顺序）
public Set<String> getUniqueErrorCodes(List<LogEntry> logs) {
    LinkedHashSet<String> errorCodes = new LinkedHashSet<>();
    for (LogEntry log : logs) {
        if (log.isError()) {
            errorCodes.add(log.getErrorCode());
        }
    }
    return errorCodes;
}
</syntaxhighlight>

== 常见问题 ==
=== 与HashSet比较 ===
{| class="wikitable"
|-
! 特性 !! LinkedHashSet !! HashSet
|-
| 顺序保证 || 有 || 无
|-
| 迭代性能 || 稍慢 || 更快
|-
| 内存占用 || 更高（多维护链表） || 更低
|}

=== 线程安全性 ===
LinkedHashSet'''不是'''线程安全的，多线程环境下需使用：
<syntaxhighlight lang="java">
Set<String> safeSet = Collections.synchronizedSet(new LinkedHashSet<>());
</syntaxhighlight>

== 最佳实践 ==
* '''适用场景'''：
  * 需要保留插入/访问顺序的集合
  * 需要快速查找且维护顺序的系统
* '''避免场景'''：
  * 纯数学集合运算（使用HashSet更高效）
  * 超大规模数据集（考虑专门顺序存储方案）

{{Tip|在Java 8+中，当链表长度超过8时，桶会转为红黑树结构，大幅提升最坏情况下的性能。}}

== 参见 ==
* [[Java集合框架]]
* [[HashSet]]
* [[LinkedHashMap]]（底层实现）

[[Category:编程语言]]
[[Category:Java]]
[[Category:Java集合框架]]