当前位置： 首页 > news >正文

Java 集合框架： LinkedHashSet

news 2025/8/3 7:27:09

目录

文档链接

一、初识 LinkedHashSet

1.1 与其他 Set 实现的对比

1.2 核心优势

二、底层实现：哈希表 + 双向链表

2.1 数据结构细节

2.2 元素节点的结构

三、构造方法

3.1 无参构造方法：LinkedHashSet()

3.2 指定初始容量：LinkedHashSet(int initialCapacity)

3.3 指定初始容量和加载因子

3.4 从集合初始化：LinkedHashSet(Collectionc)

四、核心方法

4.1 增删查

4.1.1 add(E e)：添加元素

4.1.2 remove(Object o)：删除元素

4.1.3 contains(Object o)：判断元素是否存在

4.2 迭代器：按插入顺序遍历

4.3 spliterator()：支持并行迭代

4.4 其他常用方法

五、并发问题

5.1Fail-Fast 机制

六、实际应用场景

6.1 需保留插入顺序的去重场景

6.2 复制集合并保持顺序

七、注意事项

 7.1 元素必须重写equals和hashCode

在 Java 集合框架中，Set接口的实现类各有特色：HashSet以高效著称却无序，TreeSet能排序但性能稍逊。而今天的主角 ——LinkedHashSet，则巧妙地融合了两者的优势：既保持了HashSet的常数时间性能，又通过维护元素的插入顺序提供了可预测的迭代行为。

文档链接

看这一篇之前，建议先看看：点击这里，HashSet

之后再看文档：

点击这里， LinkedHashSet

一、初识 LinkedHashSet

LinkedHashSet是HashSet的子类，同时实现了Set、Cloneable和Serializable接口。

它的核心特性可以用一句话概括：基于哈希表实现快速查找，通过双向链表维护元素的插入顺序。

 有这么厉害吗？看看就知道啦。

1.1 与其他 Set 实现的对比

实现类底层结构迭代顺序基本操作性能特点
HashSet哈希表（数组 + 链表 / 红黑树）无序（取决于哈希值）O(1)高效但顺序不可控
TreeSet红黑树自然排序或自定义排序O(log n)有序但性能稍低
LinkedHashSet哈希表 + 双向链表插入顺序（插入时的顺序）O(1)高效且顺序可预测

1.2 核心优势

  • 有序性：迭代时按元素插入的顺序遍历（重新插入已存在元素不会改变顺序）。
  • 高效性：add、contains、remove等基本操作与HashSet一样，均为常数时间复杂度（假设哈希函数均匀分布）。
  • 去重性：作为Set的实现，天然保证元素唯一（依赖equals和hashCode方法）。

二、底层实现：哈希表 + 双向链表

LinkedHashSet继承自HashSet，但在其基础上增加了一个双向链表，用于记录元素的插入顺序。这是关键。

2.1 数据结构细节

  • 哈希表：与HashSet一致，底层是一个数组（称为 "桶"），每个桶中存放哈希值相同的元素（以链表或红黑树形式）。作用是实现快速的查找、添加和删除。
  • 双向链表：额外维护的链表贯穿所有元素，每个元素同时属于哈希表和双向链表。链表中的节点包含before和after指针，分别指向前后元素，以此记录插入顺序。

简单来说：哈希表负责 "快"，双向链表负责 "序"。

2.2 元素节点的结构

LinkedHashSet的元素节点（Entry）可以理解为包含以下字段：

  • hash：元素的哈希值（用于确定在哈希表中的位置）。
  • key：元素本身。
  • next：哈希表中同一桶的下一个元素（解决哈希冲突）。
  • before：双向链表中当前元素的前一个元素。
  • after：双向链表中当前元素的后一个元素。

这种结构使得元素既能通过哈希表快速定位，又能通过双向链表按插入顺序遍历。

三、构造方法

LinkedHashSet提供了 4 个构造方法，用于不同场景的初始化。

3.1 无参构造方法：LinkedHashSet()

使用默认初始容量（16）和加载因子（0.75）创建空集合。

关于加载因子我在上一篇  HashSet 中讲过，大家可以去看看，或者你没看就跳过来这了？愤怒ing

import java.util.LinkedHashSet;public class LinkedHashSetDemo {public static void main(String[] args) {// 无参构造：默认容量16，加载因子0.75LinkedHashSet<String> set = new LinkedHashSet<>();set.add("Java");set.add("Python");set.add("C++");// 迭代顺序与插入顺序一致for (String lang : set) {System.out.println(lang); // 输出：Java、Python、C++}}
}

3.2 指定初始容量：LinkedHashSet(int initialCapacity)

使用指定的初始容量和默认加载因子（0.75）创建空集合。初始容量是哈希表的初始大小，当元素数量超过 容量*加载因子 时，哈希表会扩容（默认翻倍）。

// 指定初始容量为32（适合已知元素较多的场景）
LinkedHashSet<Integer> numbers = new LinkedHashSet<>(32);
numbers.add(10);
numbers.add(20);
numbers.add(30);
System.out.println(numbers); // 输出：[10, 20, 30]

注意：

初始容量并非越大越好。过大的容量会浪费空间，过小则可能导致频繁扩容（扩容时需要重新哈希，性能开销较大）。

3.3 指定初始容量和加载因子

LinkedHashSet(int initialCapacity, float loadFactor)

更灵活的初始化方式，可同时指定初始容量和加载因子。加载因子越大，哈希表越 "拥挤"（节省空间但冲突率高）；越小则越 "稀疏"（冲突率低但浪费空间）。

// 初始容量10，加载因子0.5（元素达到5个时扩容）
LinkedHashSet<Character> chars = new LinkedHashSet<>(10, 0.5f);
chars.add('a');
chars.add('b');
chars.add('c');
chars.add('d');
chars.add('e'); // 此时元素数=5，达到10*0.5，触发扩容

3.4 从集合初始化：LinkedHashSet(Collection<? extends E> c)

将指定集合中的元素复制到新的LinkedHashSet中，初始容量为足以容纳所有元素的最小值，加载因子为 0.75。新集合的迭代顺序与原集合的迭代顺序一致（但会自动去重）。

import java.util.ArrayList;
import java.util.List;public class LinkedHashSetFromCollection {public static void main(String[] args) {List<String> list = new ArrayList<>();list.add("Apple");list.add("Banana");list.add("Apple"); // 重复元素list.add("Orange");// 从list初始化LinkedHashSet（去重并保留原顺序）LinkedHashSet<String> fruits = new LinkedHashSet<>(list);System.out.println(fruits); // 输出：[Apple, Banana, Orange]}
}

应用场景：快速对一个有序集合去重，同时保留原始顺序（如处理用户输入的标签列表，去重后按输入顺序展示）。

四、核心方法

LinkedHashSet本身没有新增太多方法，主要继承自HashSet和Set接口。但其 "有序" 特性，让这些方法有了更丰富的用法。

4.1 增删查

4.1.1 add(E e)：添加元素

  • 若元素不存在，添加到集合并插入双向链表尾部（保持插入顺序）。
  • 若元素已存在（通过equals和hashCode判断），不改变集合（重新插入不会影响顺序）。
LinkedHashSet<String> set = new LinkedHashSet<>();
set.add("A");
set.add("B");
set.add("A"); // 重新插入已存在元素System.out.println(set); // 输出：[A, B]（顺序不变）

4.1.2 remove(Object o)：删除元素

  • 从哈希表和双向链表中同时移除元素，链表会自动调整前后节点的指针，不影响剩余元素的顺序。
LinkedHashSet<Integer> set = new LinkedHashSet<>();
set.add(1);
set.add(2);
set.add(3);set.remove(2); // 删除元素2System.out.println(set); // 输出：[1, 3]（剩余元素顺序不变）

4.1.3 contains(Object o)：判断元素是否存在

  • 基于哈希表实现，时间复杂度 O (1)，比ArrayList的contains（O (n)）高效得多。
LinkedHashSet<String> set = new LinkedHashSet<>();
set.add("Java");System.out.println(set.contains("Java")); // true
System.out.println(set.contains("Python")); // false

4.2 迭代器：按插入顺序遍历

LinkedHashSet 的迭代器（iterator()）是按插入顺序遍历元素的，这是它与HashSet的核心区别。

import java.util.Iterator;public class LinkedHashSetIteration {public static void main(String[] args) {LinkedHashSet<String> set = new LinkedHashSet<>();set.add("Spring");set.add("Spring Boot");set.add("Spring Cloud");// 迭代器遍历（按插入顺序）Iterator<String> iterator = set.iterator();while (iterator.hasNext()) {System.out.println(iterator.next()); // 输出：Spring、Spring Boot、Spring Cloud}// 增强for循环遍历（同样按插入顺序）for (String framework : set) {System.out.println(framework); // 同上}}
}

性能对比：LinkedHashSet的迭代时间与元素数量成正比（仅遍历双向链表），而HashSet的迭代时间与容量成正比（需遍历整个哈希表，包括空桶）。因此，当集合容量大但元素少时，LinkedHashSet迭代更高效。

4.3 spliterator()：支持并行迭代

Java 8 引入的Spliterator（可分割迭代器），支持并行处理元素。LinkedHashSet的spliterator()返回一个具有SIZED、DISTINCT、ORDERED特征的迭代器，继承了 fail-fast 特性。

应用场景：在多线程环境中并行处理集合元素，提高处理效率。

LinkedHashSet<String> set = new LinkedHashSet<>();
set.add("a");
set.add("b");
set.add("c");// 使用Spliterator遍历
set.spliterator().forEachRemaining(System.out::println); // 输出：a、b、c

4.4 其他常用方法

  • size()：      返回元素数量。
  • isEmpty()： 判断集合是否为空。
  • clear()：    清空所有元素。
  • clone()：    返回集合的浅拷贝（元素本身不拷贝）。
LinkedHashSet<String> set = new LinkedHashSet<>();
set.add("Hello");
set.add("World");System.out.println(set.size()); // 2
System.out.println(set.isEmpty()); // false// 克隆集合
LinkedHashSet<String> cloneSet = (LinkedHashSet<String>) set.clone();
System.out.println(cloneSet); // [Hello, World]set.clear();
System.out.println(set.isEmpty()); // true

五、并发问题

5.1Fail-Fast 机制

LinkedHashSet的迭代器是快速失败（fail-fast） 的：若迭代过程中集合被修改（除迭代器自身的remove方法），会立即抛出ConcurrentModificationException。

import java.util.Iterator;public class FailFastDemo {public static void main(String[] args) {LinkedHashSet<String> set = new LinkedHashSet<>();set.add("A");set.add("B");Iterator<String> iterator = set.iterator();while (iterator.hasNext()) {String elem = iterator.next();if (elem.equals("A")) {set.remove(elem); // 迭代中通过集合修改元素，触发异常}}}
}
// 运行结果：抛出ConcurrentModificationException

注意：

fail-fast 是 "尽最大努力" 抛出异常，不能依赖它保证程序正确性，仅用于检测 bug。

六、实际应用场景

6.1 需保留插入顺序的去重场景

例如：记录用户浏览历史（去重且按浏览顺序展示）、处理日志中的唯一操作（按时间顺序输出）。

// 模拟用户浏览历史去重并保持顺序
LinkedHashSet<String> history = new LinkedHashSet<>();
history.add("首页");
history.add("商品列表");
history.add("首页"); // 重复访问，不改变顺序
history.add("购物车");System.out.println("浏览历史：" + history); 
// 输出：浏览历史：[首页, 商品列表, 购物车]

6.2 复制集合并保持顺序

如用户文档中的示例，将任意Set复制为LinkedHashSet，确保返回结果的顺序与输入一致。

import java.util.HashSet;
import java.util.Set;public class CopySetExample {// 复制集合并保持顺序public static Set<String> copySet(Set<String> source) {return new LinkedHashSet<>(source);}public static void main(String[] args) {Set<String> hashSet = new HashSet<>();hashSet.add("C");hashSet.add("A");hashSet.add("B");Set<String> copiedSet = copySet(hashSet);System.out.println(copiedSet); // 输出：[C, A, B]（与hashSet的迭代顺序一致）}
}

七、注意事项

 7.1 元素必须重写equals和hashCode

LinkedHashSet依赖这两个方法判断元素是否重复，若未正确重写，会导致去重失效。

class Person {private String name;// 未重写equals和hashCodepublic Person(String name) { this.name = name; }
}public class BadExample {public static void main(String[] args) {LinkedHashSet<Person> set = new LinkedHashSet<>();set.add(new Person("Alice"));set.add(new Person("Alice")); // 因未重写方法，被视为不同元素System.out.println(set.size()); // 输出：2（错误，应为1）}
}

正确的：

class Person {private String name;public Person(String name) { this.name = name; }@Overridepublic boolean equals(Object o) {if (this == o) return true;if (o == null || getClass() != o.getClass()) return false;Person person = (Person) o;return name.equals(person.name);}@Overridepublic int hashCode() {return name.hashCode();}
}// 此时添加两个name相同的Person，set.size()为1（正确）

http://www.lryc.cn/news/607936.html

相关文章：

  • innoDB的buffer pool
  • API征服者：Python抓取星链卫星实时轨迹
  • k8s集群部署（脚本版）
  • 【CVPR2025】计算机视觉|即插即用|GCNet:炸裂！实时语义分割新星GCNet，性能速度双突破！
  • 前端应用权限设计面面观
  • JVM中的垃圾回收暂停是什么，为什么会出现暂停，不同的垃圾回收机制暂停对比
  • 题解：P4447 [AHOI2018初中组] 分组
  • rabbitmq消息队列详述
  • python创建一个excel文件
  • PHP 与 MySQL 详解实战入门（2）
  • Removing Digits(Dynamic Programming)
  • 【第三章】变量也疯狂：深入剖析 Python 数据类型与内存原理
  • Android13文件管理USB音乐无专辑图片显示的是同目录其他图片
  • 【NLP舆情分析】基于python微博舆情分析可视化系统(flask+pandas+echarts) 视频教程 - 微博舆情数据可视化分析-热词情感趋势柱状图
  • 机器学习 —— 决策树
  • 从C++0基础到C++入门（第十五节：switch语句）
  • 计算机网络：为什么IPv6没有选择使用点分十进制
  • 如何修复非json数据
  • Gemini CLI
  • 深入 Go 底层原理（五）：内存分配机制
  • 操作系统-lecture5（线程）
  • Vue3核心语法基础
  • 【大模型入门】3.从头实现GPT模型以生成文本
  • 相对路径 绝对路径
  • UniappDay07
  • sqli-labs：Less-19关卡详细解析
  • Qt 槽函数被执行多次，并且使用Qt::UniqueConnection无效【已解决】
  • 24黑马SpringCloud的Docker本地目录挂载出现相关问题解决
  • Tushare对接OpenBB分析A股与港股市场
  • 解锁智能油脂润滑系统：加速度与温振传感器选型协同攻略