HashSet 底层原理

HashSet 底层就是一个 HashMap，元素作为 key 存储，利用 HashMap key 的唯一性保证元素不重复。判断重复依赖 hashCode() + equals()，整体无序、不保证插入顺序。

底层实现

public class HashSet<E> extends AbstractSet<E> implements Set<E> {
    // 底层就是一个 HashMap
    private transient HashMap<E, Object> map;

    // 所有 value 共用的占位对象
    private static final Object PRESENT = new Object();

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

    public boolean add(E e) {
        return map.put(e, PRESENT) == null;  // key 不存在返回 null → add 返回 true
    }

    public boolean remove(Object o) {
        return map.remove(o) == PRESENT;
    }

    public boolean contains(Object o) {
        return map.containsKey(o);
    }
}

核心思路：HashMap 的 key 天然不允许重复，HashSet 就利用这一点，将元素存为 HashMap 的 key，value 统一用一个 PRESENT 常量占位。

元素去重流程

添加元素 e
  ↓
计算 e.hashCode()
  ↓
定位到桶位置
  ↓
桶为空？── 是 → 直接存入，返回 true
  │
  否
  ↓
遍历桶中节点，用 equals() 逐个比较
  ↓
找到相等的？── 是 → 不存入（重复），返回 false
  │
  否
  ↓
追加到链表/红黑树，返回 true

hashCode 和 equals 的约定

// 自定义对象必须正确重写这两个方法才能在 HashSet 中正常去重
public class Person {
    private String name;
    private int age;

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

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Person person = (Person) o;
        return age == person.age && Objects.equals(name, person.name);
    }
}

不重写会怎样？

Set<Person> set = new HashSet<>();
set.add(new Person("张三", 25));
set.add(new Person("张三", 25));
set.size();  // 不重写：2（被认为是不同对象）
             // 正确重写后：1

HashSet、LinkedHashSet、TreeSet 的区别

TreeSet 的排序实现

两种方式：

// 方式1：元素实现 Comparable 接口（自然排序）
public class Student implements Comparable<Student> {
    @Override
    public int compareTo(Student o) {
        return this.age - o.age;  // 按年龄升序
    }
}
TreeSet<Student> set = new TreeSet<>();

// 方式2：构造时传入 Comparator（自定义排序）
TreeSet<Student> set = new TreeSet<>((s1, s2) -> s1.getName().compareTo(s2.getName()));

Set 选型指南

需要去重？
├─ 不需要排序
│   ├─ 不关心顺序 → HashSet（最快）
│   └─ 保持插入顺序 → LinkedHashSet
└─ 需要排序 → TreeSet