【面试干货】 Java 中的 HashSet 底层实现

1、HashSet 的底层实现
2、 HashSet 的特点
3、总结

💖The Begin💖点点关注，收藏不迷路💖

HashSet 是 Java 集合框架中的一个重要成员，它提供了不存储重复元素的集合。但是，你有没有好奇过 HashSet 是如何实现这一特性的呢？本文将带你深入了解 HashSet 的底层实现机制。

1、HashSet 的底层实现

HashSet 的实现是基于 HashMap 的。当我们创建一个 HashSet 对象时，实际上是在背后初始化了一个 HashMap 对象。

但是，HashSet 和 HashMap 的使用方式并不完全相同，这是因为 HashSet 隐藏了 HashMap 的某些复杂性，只暴露了简单的集合操作接口。

HashSet 不允许值重复，这是如何实现的呢？ 关键在于 HashSet 是如何存储其元素的。在 HashSet 中，元素是作为 HashMap 的 key 存储的，而 HashMap 的 value 则是一个固定的对象（在 Java 8 及以后的版本中，这个固定的对象通常是一个名为 PRESENT 的静态常量对象）。

示例：

package com.mypackage;

import java.util.HashMap;
import java.util.Map;

public class MyHashSet<E> {
    // 使用 HashMap 存储元素，这里将 key 视为 HashSet 中的元素
    private Map<E, Object> map;

    // 静态常量，模拟 HashSet 中的 PRESENT
    private static final Object PRESENT = new Object();

    // 构造函数，初始化 HashMap
    public MyHashSet() {
        map = new HashMap<>();
    }

    // 添加元素到 HashSet 中
    public boolean add(E e) {
        // 如果 put 方法返回 null，表示该 key 尚未在 HashMap 中存在
        return map.put(e, PRESENT) == null;
    }

    // 从 HashSet 中移除元素
    public boolean remove(E e) {
        // 如果 remove 方法返回 true，表示该 key 在 HashMap 中存在并且已被移除
        return map.remove(e) != null;
    }

    // 检查 HashSet 是否包含某个元素
    public boolean contains(E e) {
        // 如果 get 方法返回非 null 值，表示该 key 在 HashMap 中存在
        return map.containsKey(e);
    }

    // 为了展示 HashSet 的内容，我们提供一个简单的方法来打印它
    public void printSet() {
        for (E e : map.keySet()) {
            System.out.println(e);
        }
    }

    // 主函数，用于测试 MyHashSet
    public static void main(String[] args) {
        MyHashSet<String> myHashSet = new MyHashSet<>();
        myHashSet.add("apple");
        myHashSet.add("banana");
        myHashSet.add("apple"); // 这将不会添加，因为 "apple" 已经存在
        System.out.println(myHashSet.contains("apple")); // 输出：true
        System.out.println(myHashSet.contains("orange")); // 输出：false
        myHashSet.remove("banana");
        myHashSet.printSet(); // 输出：apple
    }
}

在这里插入图片描述

2、 HashSet 的特点

无序性：HashSet 不保证元素的迭代顺序与插入顺序相同。这是因为 HashSet 是基于 HashMap 实现的，而 HashMap 本身不保证映射的顺序。
元素唯一性：HashSet 中的元素是唯一的，不允许重复。这是通过 HashMap 的 key 唯一性保证的。
性能：HashSet 的查找、添加和删除操作的时间复杂度通常为 O(1)，但在最坏的情况下可能会达到 O(n)（当哈希冲突严重，导致链表或红黑树过长时）。