跳到主要内容

Set 实现

问题​

HashSet、LinkedHashSet、TreeSet 分别是怎么实现的？如何保证元素不重复？

答案​

HashSet​

基于 HashMap 实现，元素作为 HashMap 的 key，value 统一使用一个 dummy 对象：

HashSet 核心源码（简化）
public class HashSet<E> implements Set<E> {
    private transient HashMap<E, Object> map;
    private static final Object PRESENT = new Object(); // 所有 value 共用

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

    public boolean add(E e) {
        return map.put(e, PRESENT) == null; // key 不存在则返回 null，表示添加成功
    }

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

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

去重原理：依赖元素的 hashCode() + equals() 方法。先比较 hashCode，相同再比较 equals，两者都相同则判定为重复元素。

LinkedHashSet​

继承 HashSet，底层使用 LinkedHashMap，维护插入顺序：

LinkedHashSet 核心原理
public class LinkedHashSet<E> extends HashSet<E> {
    // 构造函数调用 HashSet 的特殊构造函数，内部创建 LinkedHashMap
    public LinkedHashSet() {
        super(16, .75f, true); // 第三个参数触发使用 LinkedHashMap
    }
}

TreeSet​

基于 TreeMap（红黑树）实现，元素有序（自然排序或自定义 Comparator）：

TreeSet 使用示例
// 自然排序（元素实现 Comparable）
TreeSet<Integer> set1 = new TreeSet<>();
set1.add(3);
set1.add(1);
set1.add(2);
System.out.println(set1); // [1, 2, 3]

// 自定义排序
TreeSet<String> set2 = new TreeSet<>(Comparator.comparingInt(String::length));
set2.add("banana");
set2.add("apple");
set2.add("cherry");
System.out.println(set2); // [apple, banana, cherry]

三者对比​

维度HashSetLinkedHashSetTreeSet
底层HashMapLinkedHashMapTreeMap（红黑树）
有序性无序插入顺序排序顺序
null 元素允许 1 个允许 1 个不允许（比较时 NPE）
时间复杂度O(1)O(1)O(1)O(1)O(log⁡n)O(\log n)
线程安全不安全不安全不安全

常见面试问题​

Q1: HashSet 如何保证元素不重复？​

答案：

HashSet 底层是 HashMap，添加元素时：

  1. 计算元素的 hashCode() 确定桶位置
  2. 如果桶中已有元素，通过 equals() 比较内容
  3. 如果 hashCode() 相同且 equals() 返回 true，判定为重复，不添加

因此自定义类作为 Set 元素时，必须重写 hashCode() 和 equals() 方法。

Q2: HashSet 和 HashMap 的区别？​

答案：

维度HashSetHashMap
接口SetMap
存储内容单个对象键值对
添加方法add(e)put(k, v)
底层实现基于 HashMap自身就是实现
hashCode 使用对元素计算对 key 计算

Q3: 如何对自定义对象去重？​

答案：

必须同时重写 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 user)) return false;
        return age == user.age && Objects.equals(name, user.name);
    }

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

// 现在 HashSet 可以正确去重
Set<User> users = new HashSet<>();
users.add(new User("Alice", 25));
users.add(new User("Alice", 25)); // 重复，不会添加
System.out.println(users.size()); // 1

相关链接​