大家好，我是小米，一个喜欢分享技术的 29 岁程序员。前两天，有个学弟跟我吐槽，说社招面试题越来越卷了，居然问到 HashSet 的实现原理！他还说：“我明明只用了 new HashSet() 和 add()，怎么要我知道底层实现？” 听完学弟的吐槽，我觉得是时候写一篇通俗易懂的文章，把 HashSet 的实现原理讲清楚，顺便附上面试中的高分回答模板，让大家也能轻松拿下这类题目！ 什么是 HashSet？ 先从 HashSet 的定义讲起。我们平时使用 HashSet 的场景是为了存储一组 唯一 的元素，类似数学中的集合。比如：
看，HashSet 自动帮我们去重了！是不是很方便？ 但这个方便背后，有哪些机制在默默运作呢？ HashSet 的底层是什么？ 这里是个知识点：HashSet 是基于 HashMap 实现的。 在源码中，HashSet 其实是一个“壳”，所有的操作最终都委托给了内部的 HashMap 来完成。来看一段 HashSet 的源码（以 JDK 8 为例）：
从这段代码我们能看出，HashSet 的本质是一个特殊的 HashMap：它只存储键（Key），不存储值（Value）。 在 HashMap 中，每个键值对是 Key-Value 的形式，而 HashSet 则将所有值固定为一个虚拟常量 PRESENT，实现了只存储键的效果。 HashSet 的实现原理详解 1. 添加元素时如何保证唯一性？ 要理解 HashSet 去重的秘密，我们必须先搞懂 HashMap 的 put() 方法。 HashMap 的底层是一个数组 + 链表 + 红黑树的结构。具体步骤如下： 计算哈希值： 当你调用 add() 方法时，HashSet 会把元素传给 HashMap 的 put() 方法。 HashMap 首先通过 hash() 方法计算出元素的哈希值，用于确定该元素存储的位置（桶索引）。 找到存储桶： 根据哈希值找到数组中的存储桶。如果桶里已经有元素，则会遍历链表或树，比较这些元素。 通过 equals() 判断重复： 如果新元素的 hashCode() 和 equals() 方法都与已有元素匹配，则认为是重复的，直接返回。 如果不重复，则将新元素插入链表或红黑树中。 所以，HashSet 的唯一性，依赖于元素的 hashCode() 和 equals() 方法！ 2. 查找和删除的效率如何？ HashSet 的查找和删除效率非常高，平均时间复杂度为 O(1)。这是因为： 查找时直接通过哈希值定位到数组的存储桶； 如果桶内有多个元素（哈希冲突），则在链表中遍历或在红黑树中查找，最坏复杂度为 O(log n)。 3. 扩容机制是怎样的？ HashSet 的扩容同样依赖于 HashMap。当存储的元素数量超过一定阈值（默认容量的 75%）时，HashMap 会触发扩容： 数组容量翻倍； 重新计算所有元素的哈希值，并将它们分布到新的桶中。 面试高分回答模板 如果面试官问你 HashSet 的实现原理，可以参考以下回答： HashSet 是基于 HashMap 实现的，它的本质是一个只存储键（Key）的 HashMap。添加元素时，HashSet 会通过哈希值和 equals() 方法判断是否重复，以保证唯一性。 底层采用数组 + 链表 + 红黑树的结构，平均时间复杂度为 O(1)。当哈希冲突较多时，链表会转化为红黑树，查找复杂度降为 O(log n)。同时，HashSet 支持动态扩容，保证性能的稳定性。 加分项： 提到 hashCode() 和 equals() 方法的重要性； 描述扩容机制。 学弟的面试翻盘之路 讲完这些，学弟一拍大腿：“原来如此！不过面试官还问我，HashSet 和 TreeSet 有啥区别，我又答不上来。” 哈哈，其实这个问题更简单了！ HashSet 和 TreeSet 的区别 底层结构不同： HashSet 基于 HashMap，底层是哈希表。 TreeSet 基于 TreeMap，底层是红黑树。 排序特性： HashSet 中的元素是无序的。 TreeSet 会自动对元素进行排序（基于自然顺序或自定义比较器）。 性能差异： HashSet 的增删查操作平均时间复杂度为 O(1)。 TreeSet 的增删查操作时间复杂度为 O(log n)。 END 相信看到这里，你已经对 HashSet 的实现原理有了深刻的理解。在面试中，如果还能提到 HashSet 和 TreeSet 的区别，面试官一定会对你的细致和全面印象深刻！ 如果你有其他关于 Java 集合框架的问题，欢迎在评论区留言，我们一起探讨！ 小米的问答时光机 下一篇想聊聊 ArrayList 和 LinkedList 的区别？还是 ConcurrentHashMap 的并发机制？留言告诉我吧！ 我是小米，一个喜欢分享技术的29岁程序员。如果你喜欢我的文章，欢迎关注我的微信公众号“软件求生”，获取更多技术干货！
