一、什么是 Set

在 Java 集合框架中，Set 是一个不允许重复元素的集合。

特点：

1. 元素唯一

2. 无索引

3. 部分实现类无序

示例：

Set<String> set = new HashSet<>();

set.add("Java");
set.add("Python");
set.add("Java");

System.out.println(set);

输出：

[Java, Python]

说明：

Set 自动去重

---

二、Set 集合体系结构

Java Set 结构：

Collection
    │
    └── Set
         │
         ├── HashSet
         │     └── LinkedHashSet
         │
         └── SortedSet
                │
                └── TreeSet

常见实现类：

类	特点
HashSet	无序、不重复
LinkedHashSet	有序、不重复
TreeSet	排序、不重复

---

三、HashSet 原理（重点）

HashSet 本质：

HashSet = HashMap

源码：

private transient HashMap<E,Object> map;

HashSet 存储结构：

key -> element
value -> 固定对象

源码：

private static final Object PRESENT = new Object();

add 方法：

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

结构示意：

HashMap
│
key      value
Java  -> PRESENT
Python-> PRESENT
C++   -> PRESENT

所以：

HashSet 底层完全依赖 HashMap

---

四、HashSet 数据结构

HashSet 的底层结构就是 HashMap

即：

数组 + 链表 + 红黑树

结构：

table
 │
 ├── Node -> Node
 │
 ├── Node -> Node -> Node
 │
 └── Node -> 红黑树

因此：

HashSet 的性能 ≈ HashMap

---

五、HashSet 去重原理

Set 之所以不允许重复，核心依赖：

hashCode()
equals()

执行流程：

add(element)
      │
计算 hashCode
      │
定位数组位置
      │
是否存在元素
      │
equals 判断

流程图：

hashCode 相同
        │
  equals 判断
   │       │
 true     false
 │         │
不插入     插入

---

示例

class Student{
    int id;
    String name;
}

如果不重写：

equals
hashCode

结果：

不会去重

因为：

地址不同

必须重写：

@Override
public int hashCode() {
    return Objects.hash(id,name);
}

@Override
public boolean equals(Object obj) {
    if(this == obj) return true;
    if(!(obj instanceof Student)) return false;
    Student s = (Student)obj;
    return id == s.id && Objects.equals(name,s.name);
}

---

六、LinkedHashSet 原理

LinkedHashSet 是：

HashSet 子类

源码：

public class LinkedHashSet<E>
extends HashSet<E>

底层：

LinkedHashMap

结构：

Hash表 + 双向链表

示意：

HashMap
   │
双向链表维护顺序

结构：

A → B → C → D

特点：

保持插入顺序

示例：

Set<String> set = new LinkedHashSet<>();

set.add("C");
set.add("A");
set.add("B");

System.out.println(set);

输出：

[C, A, B]

顺序保持。

---

七、TreeSet 原理

TreeSet 特点：

自动排序

底层：

TreeMap

源码：

private transient NavigableMap<E,Object> m;

数据结构：

红黑树

示意：

        10
       /  \
      5    15
     / \
    3   7

时间复杂度：

O(log n)

---

八、TreeSet 排序规则

TreeSet 排序方式有两种：

1 自然排序

对象实现：

Comparable

示例：

class Student implements Comparable<Student>{

    int age;

    @Override
    public int compareTo(Student o){
        return this.age - o.age;
    }
}

TreeSet：

Set<Student> set = new TreeSet<>();

---

2 自定义排序

使用：

Comparator

示例：

Set<Student> set = new TreeSet<>(
    (a,b)->a.age - b.age
);

---

九、HashSet vs LinkedHashSet vs TreeSet

集合	底层结构	是否有序	时间复杂度
HashSet	HashMap	无序	O(1)
LinkedHashSet	LinkedHashMap	插入顺序	O(1)
TreeSet	红黑树	排序	O(log n)

选择建议：

需要去重 → HashSet
需要顺序 → LinkedHashSet
需要排序 → TreeSet

---

十、Set 常用方法

add(E e)

remove(Object o)

contains(Object o)

size()

clear()

示例：

Set<String> set = new HashSet<>();

set.add("Java");

set.remove("Java");

set.contains("Java");

---

十一、Set 遍历方式

Set 没有索引，因此不能：

for(i)

遍历方式：

增强for

for(String s:set){
    System.out.println(s);
}

---

Iterator

Iterator<String> it = set.iterator();

while(it.hasNext()){
    System.out.println(it.next());
}

---

forEach

set.forEach(System.out::println);

---

十二、Set 为什么没有 get()

原因：

Set 无索引

Set 设计理念：

只关心元素存在

而不是：

位置

---

十三、Set 面试高频问题

1 HashSet 底层结构

HashMap

---

2 HashSet 如何去重

依赖：

hashCode
equals

---

3 HashSet 是否有序

无序

---

4 LinkedHashSet 为什么有序

因为：

双向链表

维护：

插入顺序

---

5 TreeSet 为什么能排序

因为底层：

红黑树

---

6 TreeSet 插入复杂度

O(log n)

---

7 TreeSet 为什么不能存 null

因为排序需要：

compareTo

null 无法比较。

---

十四、总结

Java Set 核心结构：

Set
 │
 ├─ HashSet
 │     HashMap
 │
 ├─ LinkedHashSet
 │     LinkedHashMap
 │
 └─ TreeSet
       红黑树

核心知识：

HashSet去重原理
LinkedHashSet顺序
TreeSet排序
hashCode + equals
红黑树