第 13 章:Set 接口与 HashSet

学习目标

• 掌握 Set 去重的本质(hashCode + equals)
• 学会 HashSet / LinkedHashSet / TreeSet 的选型

一、Set:无序、不可重复

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

set.add("A");
set.add("B");
set.add("A");           // ⚠️ 重复,不添加
System.out.println(set.size());   // 2

set.contains("A");      // true
set.remove("A");
set.size();
set.isEmpty();
set.clear();

// 遍历(只能用 for-each,Set 没有索引)
for (String s : set) {
    System.out.println(s);
}

二、Set 去重的本质

HashSet 依赖 hashCode + equals 判断重复:

Set<String> set = new HashSet<>();
set.add("hello");
set.add("hello");       // 因为 hashCode + equals 相同,被判定为重复,不加入

// 自定义对象必须重写 hashCode + equals,否则去重失败
public class User {
    private String name;
    private int age;

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof User)) return false;
        User u = (User) o;
        return age == u.age && Objects.equals(name, u.name);
    }

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

⚠️ 坑 1:自定义对象想放进 HashSet,必须同时重写 equals 和 hashCode,否则去重不生效。

三、Set 实现类对比与选型

实现	底层	有序	性能	适用
HashSet	HashMap	❌	O(1)	默认,99% 用这个
LinkedHashSet	链表 + HashMap	✅ 插入序	O(1)	要保留插入顺序
TreeSet	红黑树	✅ 排序	O(log n)	要自动排序

// ✅ 99% 用 HashSet
Set<String> tags = new HashSet<>();

// ✅ 需要按插入顺序遍历(如 LRU 缓存)
Set<String> orderedTags = new LinkedHashSet<>();

// ✅ 需要元素自动排序
Set<Integer> sortedSet = new TreeSet<>();

四、实战:用 Set 去重

// 数组去重
List<Integer> list = new ArrayList<>(List.of(1, 2, 3, 2, 1, 4));
Set<Integer> set = new HashSet<>(list);            // List → Set 自动去重
List<Integer> unique = new ArrayList<>(set);       // Set → List
System.out.println(unique);                        // [1, 2, 3, 4](顺序不保证)

// 保留顺序的去重:LinkedHashSet
Set<Integer> orderedSet = new LinkedHashSet<>(list);

五、本章小结

要点	关键
Set 特性	无序、不可重复
去重原理	依赖 hashCode + equals
HashSet	99% 用,O(1) 性能
LinkedHashSet	保留插入顺序
TreeSet	自动排序,但 O(log n)
自定义对象	必须同时重写 equals 和 hashCode

动手练习

1. 数组去重:把一个含重复元素的数组转成无重复的 List
2. 字符串字符去重:写 uniqueChars(String s),返回不含重复字符的字符串
3. 自定义 Set:把 User 对象放进 HashSet,验证去重需要重写 equals/hashCode

---

下一章:第 14 章:Map 接口与 HashMap →