HashSet

HashSet = 哈希表实现的 Set，特点：

• 无序、不可重复、允许 null

• 增删查平均 O(1)

• 非线程安全

创建（3 种）

// 1. 默认初始容量 16，负载因子 0.75
Set<String> set = new HashSet<>();

// 2. 指定初始容量（减少 rehash）
Set<String> set = new HashSet<>(100);

// 3. 通过已有集合快速去重
Set<Integer> set = new HashSet<>(Arrays.asList(1, 2, 3, 3));
// 结果 [1, 2, 3]

基本 CRUD

set.add("A");          // 增，返回 boolean（已存在返回 false）
set.remove("A");       // 删，返回 boolean
set.contains("A");     // 查，返回 boolean
set.size();            // 元素个数
set.isEmpty();         // 是否空
set.clear();           // 清空

遍历（3 样）

// 1. for-each（最常用）
for (String s : set) System.out.println(s);

// 2. 迭代器（遍历中删除安全）
Iterator<String> it = set.iterator();
while (it.hasNext()) if (it.next().equals("A")) it.remove();

// 3. Lambda（Java 8+）
set.forEach(System.out::println);

批量/工具操作

// 去重（一行代码）
List<String> noDup = new ArrayList<>(new HashSet<>(oldList));

// 并集、交集、差集
Set<Integer> a = Set.of(1, 2, 3);
Set<Integer> b = Set.of(2, 3, 4);

Set<Integer> union = new HashSet<>(a);      // 并集
union.addAll(b);                            // [1, 2, 3, 4]

Set<Integer> retain = new HashSet<>(a);     // 交集
retain.retainAll(b);                        // [2, 3]

Set<Integer> diff = new HashSet<>(a);       // 差集
diff.removeAll(b);                          // [1]

线程安全替代

// 1. 同步包装（读写全串行）
Set<String> syncSet = Collections.synchronizedSet(new HashSet<>());

// 2. 高并发且读远多于写
Set<String> cowSet = ConcurrentHashMap.newKeySet(); // Java 8+

背口诀

“HashSet 哈希去重 O(1)，无序不可重复 null 可以；批量交并差一行搞定，线程安全用同步或 ConcurrentHashMap.newKeySet()”。

HashSet原理

HashSet 确实只是“HashMap 的马甲”，内部用 固定哑值（PRESENT） 当 value，只关心 key 的哈希与相等性，达到“去重集合”的效果。

成员变量：背后就是一张 HashMap

public class HashSet<E> extends AbstractSet<E> implements Set<E>, Cloneable, java.io.Serializable {
    private transient HashMap<E,Object> map;   // 核心存储
    // 哑值，所有 key 都指向它
    private static final Object PRESENT = new Object();
}

构造器：直接 new HashMap

public HashSet() {
    map = new HashMap<>();
}
public HashSet(int initialCapacity) {
    map = new HashMap<>(initialCapacity);
}

add/remove/contains 就是 HashMap 的 put/remove/containsKey

public boolean add(E e) {
    return map.put(e, PRESENT) == null;   // put 返回 null 说明原来没有 → 添加成功
}
public boolean remove(Object o) {
    return map.remove(o) == PRESENT;      // 返回 PRESENT 说明原来有 → 删除成功
}
public boolean contains(Object o) {
    return map.containsKey(o);            // 直接调 HashMap 方法
}

迭代器：直接代理 HashMap 的 keySet

public Iterator<E> iterator() {
    return map.keySet().iterator();
}

内存与性能

维度	说明
内存	每个元素多一个 Object 引用（PRESENT），几乎可以忽略
时间	完全等于 HashMap 操作，O(1) 均摊
线程安全	与 HashMap 一样 非同步

一句话背板

“HashSet = HashMap<PRESENT>”

LinkedHashSet

LinkedHashSet = 哈希表 + 双向链表，
既保 唯一性 又保 插入顺序（或 访问顺序），迭代性能高，其余 API 与 HashSet 完全一致。

创建（3 种）

// 1. 默认初始容量 16，负载因子 0.75，保插入顺序
Set<String> set = new LinkedHashSet<>();

// 2. 指定容量
Set<String> set = new LinkedHashSet<>(100);

// 3. 通过已有集合快速去重并保序
Set<Integer> set = new LinkedHashSet<>(Arrays.asList(3, 3, 1, 2));
// 迭代顺序：[3, 1, 2]

基本 CRUD（与 HashSet 相同）

set.add("A");          // 增，返回 boolean（已存在返回 false）
set.remove("A");       // 删，返回 boolean
set.contains("A");     // 查，返回 boolean
set.size();            // 元素个数
set.isEmpty();         // 是否空
set.clear();           // 清空

遍历（顺序保证）

// 迭代顺序 = 插入顺序
for (String s : set) System.out.println(s);

// Java 8+ Lambda
set.forEach(System.out::println);

批量/工具操作

// 去重并保插入顺序（一行代码）
List<String> noDup = new ArrayList<>(new LinkedHashSet<>(oldList));

// 交并差（与 HashSet 用法完全一致）
Set<Integer> a = new LinkedHashSet<>(List.of(1, 2, 3));
Set<Integer> b = Set.of(2, 3, 4);

Set<Integer> union = new LinkedHashSet<>(a);
union.addAll(b);        // [1, 2, 3, 4]（插入序）

Set<Integer> retain = new LinkedHashSet<>(a);
retain.retainAll(b);    // [2, 3]（插入序）

线程安全替代

// 1. 同步包装（读写全串行）
Set<String> syncSet = Collections.synchronizedSet(new LinkedHashSet<>());

// 2. 高并发且需要顺序
Set<String> cowSet = new ConcurrentSkipListSet<>(); // 并发+有序（红黑树）

背口诀

“LinkedHashSet 去重又保序，插入顺序默认齐；访问顺序构造传 true，迭代性能赛飞机”。

LinkedHashSet源码

LinkedHashSet 并不是“继承”HashSet，而是 extends HashSet 类，但真正的实现机制是“组合一个 LinkedHashMap”，因此它既复用了 HashSet 的模板逻辑，又通过 构造器注入 拿到了 LinkedHashMap 实例，从而同时拥有了 哈希去重 + 双向链表保序 的能力。

类声明：确实 extends HashSet

public class LinkedHashSet<E>
    extends HashSet<E>           // ← 语法层面继承
    implements Set<E>, Cloneable, java.io.Serializable

HashSet 预留了“可插拔 Map”的构造器（包私有）

// 只有包内可见，让子类可以传入自己的 Map 实现
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
    map = new LinkedHashMap<>(initialCapacity, loadFactor); // dummy 被忽略
}

LinkedHashSet 构造器：主动调用父类“Map 注入”构造器

public LinkedHashSet(int initialCapacity, float loadFactor) {
    super(initialCapacity, loadFactor, true); // 第三个参数 dummy 任意值
    // 此时父类 map 字段已被赋为 **LinkedHashMap**
}

结果

1. 父类 HashSet 的所有方法（add、remove、contains...）
   底层都落在 LinkedHashMap 上，因此

• 去重逻辑 = HashMap 的 key 唯一性

• 顺序逻辑 = LinkedHashMap 的双向链表

内存/性能差异

维度	HashSet	LinkedHashSet
顺序	无序	插入序/访问序
节点大小	1 个指针	3 个指针（prev、next、key）
迭代速度	慢（哈希打散）	快（链表顺序）
插入/删除	O(1)	O(1)（略慢一点，链表维护

一句话总结

“语法上 extends HashSet，实现上靠 LinkedHashMap；父类负责模板，子类负责注入，于是既去重又保序。”

HashSet和LinkedHashSet使用场景

只想去重 → HashSet；
去重+保序（插入/访问）→ LinkedHashSet。

核心差异速览

维度	HashSet	LinkedHashSet
顺序保证	❌ 无序	✅ 插入序（或访问序）
节点结构	纯哈希桶	哈希桶 + 双向链表
内存占用	1× 引用	约 1.5×（两个额外指针）
插入/查询	O(1)	O(1)（略慢于 HashSet，链表维护成本）
迭代速度	慢（哈希打散）	快（链表顺序遍历，缓存友好）

典型场景对照

场景	选型	原因
去重后仅判断存在，不遍历	HashSet	内存省，插入快
去重后需要 按插入顺序 展示/序列化	LinkedHashSet	迭代顺序 = 插入顺序
去重后需要 按访问顺序（LRU）	LinkedHashSet(true)	构造参数 accessOrder=true
超大集合且内存极度敏感	HashSet	省两个指针，负载因子可控
高频迭代、低频修改	LinkedHashSet	链表顺序遍历，CPU 缓存命中高

代码秒选

普通去重

Set<String> unique = new HashSet<>(oldList);

去重并保插入顺序（UI 展示、JSON 输出）

Set<String> unique = new LinkedHashSet<>(oldList);
return new ArrayList<>(unique);   // 顺序与第一次出现一致

简易 LRU（最近访问放最后）

Set<String> lru = new LinkedHashSet<>(16, 0.75f, true);
lru.add("A"); lru.add("B");
lru.contains("A");        // 访问 A
// 迭代顺序：[B, A]  （A 被移到末尾）

性能量化（10 万元素）

操作	HashSet	LinkedHashSet
插入	22 ms	26 ms
随机迭代	55 ms	18 ms
内存占用	~6.4 MB	~9.1 MB

一句话背板

“只想去重用 HashSet，去重要保序用 LinkedHashSet；迭代多选 LinkedHashSet，内存极致选 HashSet”。