Set集合

什么是Set集合？

Set（集合）是Java集合框架中的一个重要接口，它继承自Collection接口。Set最大的特点是不允许存储重复的元素。你可以把Set想象成一个装着unique（不重复）物品的盒子——每样东西只能放进去一次。

Set的底层实现原理

HashSet的工作原理

HashSet的内部实现其实是一个HashMap！当你向HashSet添加一个元素时，实际上是把元素作为HashMap的key存储，而value用一个固定的PRESENT对象填充。

添加元素 "Apple" 到 HashSet:
┌─────────────────────────────────────────────────────────┐
│  1. 计算 "Apple" 的哈希值 (hashCode())                   │
│  2. 根据哈希值确定在数组中的存储位置 (index)               │
│  3. 如果该位置为空，直接存储                              │
│  4. 如果不为空，调用 equals() 比较是否相同                │
│     - 相同：放弃添加（已存在）                            │
│     - 不同：链表或红黑树添加新节点                         │
└─────────────────────────────────────────────────────────┘

TreeSet的工作原理

TreeSet的内部实现是一个TreeMap，而TreeMap底层是红黑树——一种自平衡的二叉搜索树。元素按照自然顺序（Comparable）或自定义比较器（Comparator）进行排序。

红黑树特点:
• 每个节点要么是红色，要么是黑色
• 根节点是黑色
• 叶子节点（NIL）是黑色
• 红色节点的子节点必须是黑色
• 从任一节点到其每个叶子的路径上黑色节点数量相同

优势: 自动平衡，保证查找、插入、删除都是 O(log n) 时间复杂度

HashSet基本用法

import java.util.HashSet;

public class HashSetDemo {
    public static void main(String[] args) {
        // 创建HashSet
        HashSet set = new HashSet<>();

        // 添加元素
        set.add("Apple");
        set.add("Banana");
        set.add("Cherry");
        set.add("Apple");  // 重复元素，不会被添加！

        System.out.println("Set大小: " + set.size());  // 3
        System.out.println("Set内容: " + set);  // [Banana, Apple, Cherry]（无序）

        // 常用操作
        System.out.println("包含Apple? " + set.contains("Apple"));  // true
        System.out.println("包含Grape? " + set.contains("Grape"));  // false

        // 删除元素
        set.remove("Banana");
        System.out.println("删除Banana后: " + set);

        // 批量操作
        HashSet set2 = new HashSet<>();
        set2.add("Apple");
        set2.add("Durian");

        set.addAll(set2);  // 合并
        System.out.println("合并后: " + set);

        set.retainAll(set2);  // 交集
        System.out.println("交集: " + set);
    }
}

TreeSet基本用法

import java.util.TreeSet;

public class TreeSetDemo {
    public static void main(String[] args) {
        TreeSet set = new TreeSet<>();

        // 添加元素 - 自动排序
        set.add(5);
        set.add(2);
        set.add(8);
        set.add(1);
        set.add(9);
        set.add(3);

        System.out.println("TreeSet: " + set);  // [1, 2, 3, 5, 8, 9]

        // TreeSet特有方法 - 获取有序相关的元素
        System.out.println("第一个元素: " + set.first());      // 1
        System.out.println("最后一个元素: " + set.last());     // 9
        System.out.println("小于5的最大元素: " + set.lower(5));   // 3
        System.out.println("大于5的最小元素: " + set.higher(5));   // 8
        System.out.println("<=5的最大元素: " + set.floor(5));     // 5
        System.out.println(">=5的最小元素: " + set.ceiling(5));   // 5

        // 范围操作
        System.out.println("子集 [2, 8): " + set.subSet(2, 8));  // [2, 3, 5]
        System.out.println("从头到5: " + set.headSet(5));         // [1, 2, 3]
        System.out.println("从5到尾: " + set.tailSet(5));        // [5, 8, 9]
    }
}

LinkedHashSet基本用法

import java.util.LinkedHashSet;

public class LinkedHashSetDemo {
    public static void main(String[] args) {
        LinkedHashSet set = new LinkedHashSet<>();

        set.add("First");
        set.add("Second");
        set.add("Third");
        set.add("First");  // 重复，不会添加

        // 维护插入顺序
        System.out.println(set);  // [First, Second, Third]

        // 判断元素是否存在
        System.out.println("包含Second? " + set.contains("Second"));
    }
}

三种Set对比

Set遍历方式

Set有三种主要的遍历方式，每种都有其适用场景：

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

Iterator it = set.iterator();
while (it.hasNext()) {
    String element = it.next();
    if (element.equals("要删除的")) {
        it.remove();  // 安全删除，不会ConcurrentModificationException
    }
}

set.forEach(element -> System.out.println(element));
// 或者更简洁:
set.forEach(System.out::println);

实战应用场景

场景1：数组去重

import java.util.Arrays;
import java.util.HashSet;

public class RemoveDuplicates {
    public static void main(String[] args) {
        Integer[] array = {1, 2, 3, 2, 1, 4, 3, 5, 4, 6};

        // 方法1：使用HashSet去重
        HashSet unique = new HashSet<>(Arrays.asList(array));
        System.out.println("去重后: " + unique);  // [1, 2, 3, 4, 5, 6]

        // 方法2：转换为Integer数组
        Integer[] result = unique.toArray(new Integer[0]);
        System.out.println("去重后数组: " + Arrays.toString(result));
    }
}

场景2：集合运算（交、并、差）

import java.util.HashSet;
import java.util.Arrays;

public class SetOperations {
    public static void main(String[] args) {
        HashSet set1 = new HashSet<>(Arrays.asList(1, 2, 3, 4, 5));
        HashSet set2 = new HashSet<>(Arrays.asList(4, 5, 6, 7, 8));

        // 并集 (Union)
        HashSet union = new HashSet<>(set1);
        union.addAll(set2);
        System.out.println("并集: " + union);  // [1, 2, 3, 4, 5, 6, 7, 8]

        // 交集 (Intersection)
        HashSet intersection = new HashSet<>(set1);
        intersection.retainAll(set2);
        System.out.println("交集: " + intersection);  // [4, 5]

        // 差集 (Difference) - set1中有但set2中没有
        HashSet difference = new HashSet<>(set1);
        difference.removeAll(set2);
        System.out.println("差集: " + difference);  // [1, 2, 3]
    }
}

场景3：过滤重复对象

import java.util.*;

class Person {
    private String name;
    private int age;
    // 构造函数、getter、equals、hashCode省略
}

public class RemoveDuplicateObjects {
    public static void main(String[] args) {
        List people = new ArrayList<>();
        // 添加人员...

        // 使用LinkedHashSet根据name去重，同时保持插入顺序
        Set uniquePeople = new LinkedHashSet<>(people);
        System.out.println("去重后人数: " + uniquePeople.size());
    }
}

常见错误和注意事项

小结