面试题：Java 中的 HashSet，内部是如何工作的？

HashSet 是 Java 集合框架中的一个类，它实现了 Set 接口，用于存储不重复的元素。HashSet 的内部实现基于 HashMap，以下是它的工作原理：

基于 HashMap 实现：
- HashSet 内部使用了一个 HashMap 来存储元素。
- HashSet 的元素实际上是存储在 HashMap 的键（key）中，而 HashMap 的值（value）则是一个固定的常量对象（PRESENT），这个常量对象是 HashSet 内部定义的一个私有静态对象。
添加元素：
- 当调用 HashSet 的 add(E e) 方法时，实际上是将元素 e 作为 HashMap 的键，而值则是 PRESENT。
- 如果元素 e 已经存在于 HashMap 的键中（即元素已经存在），则 add 方法返回 false，表示添加失败；否则返回 true，表示添加成功。
删除元素：
- 当调用 HashSet 的 remove(Object o) 方法时，实际上是从 HashMap 中移除键为 o 的条目。
- 如果键 o 存在于 HashMap 中，则返回 true，表示删除成功；否则返回 false。
检查元素是否存在：
- 当调用 HashSet 的 contains(Object o) 方法时，实际上是检查 HashMap 中是否包含键为 o 的条目。
不重复性：
- HashSet 的不重复性是通过 HashMap 的键的唯一性来实现的。HashMap 的键是唯一的，因此 HashSet 中的元素也是唯一的。
性能：
- HashSet 的添加、删除和查找操作的时间复杂度都是 O(1)，这是基于 HashMap 的哈希表实现的。
- 但是，如果哈希冲突较多，性能可能会下降，最坏情况下时间复杂度为 O(n)。

总结：

HashSet 是基于 HashMap 实现的，元素存储在 HashMap 的键中，值是一个固定的常量对象。
HashSet 的不重复性是通过 HashMap 的键的唯一性来保证的。
HashSet 的添加、删除和查找操作的时间复杂度通常是 O(1)。

代码示例：

import java.util.HashSet;

public class HashSetExample {
    public static void main(String[] args) {
        HashSet<String> set = new HashSet<>();
        set.add("Apple");
        set.add("Banana");
        set.add("Apple"); // 重复元素，不会被添加

        System.out.println(set); // 输出: [Apple, Banana]
        System.out.println(set.contains("Banana")); // 输出: true
        set.remove("Banana");
        System.out.println(set); // 输出: [Apple]
    }
}

通过理解 HashSet 的内部实现，可以更好地使用它来存储不重复的元素，并了解其性能特点。

THE END

Java 集合类