面试题：Java中Set集合HashSet的底层实现原理

Question

请详细阐述Java中HashSet集合的底层是如何实现的，包括数据结构的使用以及元素唯一性判断的机制。

Answer 1

HashSet集合底层实现

1. 数据结构
   • HashSet的底层是基于HashMap实现的。HashMap是一种哈希表数据结构，它使用数组加链表（JDK 1.8 后引入红黑树优化链表过长的情况）来存储键值对。
   • 在HashSet中，HashMap的键（key）用来存储HashSet的元素，而值（value）则是一个固定的对象PRESENT，其定义如下：

   private static final Object PRESENT = new Object();
   

   • 当向HashSet中添加元素时，实际上是将元素作为key，PRESENT作为value添加到HashMap中。
2. 元素唯一性判断机制
   • hashCode方法：当向HashSet中添加一个元素时，首先会调用该元素的hashCode()方法。hashCode()方法返回一个整数值，这个值会被用来计算元素在HashMap内部数组中的存储位置（桶的索引）。如果两个对象的hashCode()返回值相同，它们可能存储在同一个桶中，但不一定是同一个元素。
   • equals方法：如果两个元素的hashCode()值相同（发生哈希碰撞），那么HashSet会调用这两个元素的equals()方法来进一步判断它们是否相等。如果equals()方法返回true，则认为这两个元素是相同的，HashSet不会重复添加该元素。如果equals()方法返回false，则这两个元素虽然哈希值相同，但仍然是不同的元素，会以链表（或红黑树）的形式存储在同一个桶中。
   • 总结来说，HashSet判断元素唯一性的标准是：如果两个元素的hashCode()值不同，则认为它们是不同的元素；如果hashCode()值相同，再通过equals()方法判断，若equals()返回true则认为是相同元素，否则是不同元素。这就要求在自定义类作为HashSet的元素时，必须正确重写hashCode()和equals()方法，以保证元素唯一性判断的正确性。