面试题：Java中HashSet如何处理哈希冲突

Question

简述在Java的HashSet中，当发生哈希冲突时，是通过怎样的机制来确保元素的唯一性与存储合理性的。

Answer 1

在Java的HashSet中，当发生哈希冲突时，通过以下机制确保元素的唯一性与存储合理性：

1. 哈希值与equals方法：
   • HashSet在添加元素时，首先会计算元素的哈希值。当两个元素的哈希值相同时，即发生哈希冲突。
   • 此时，HashSet会调用元素的equals方法来进一步判断这两个元素是否相等。如果equals方法返回true，则认为这两个元素是相同的，不会将新元素添加到集合中，从而确保了元素的唯一性。
2. 链表或红黑树（JDK 1.8 后改进）：
   • JDK 1.7 及之前：在发生哈希冲突时，新元素会被插入到冲突位置对应的链表头部。这种方式在哈希冲突严重时，查找元素的时间复杂度会退化为O(n)，其中n为链表长度。
   • JDK 1.8 及之后：当链表长度达到一定阈值（默认为8）且哈希表容量达到一定值时，链表会转换为红黑树。红黑树的查找、插入和删除操作的时间复杂度为O(log n)，相比链表大大提高了效率，确保了存储的合理性。

通过哈希值和equals方法判断元素唯一性，以及采用链表和红黑树结合的方式处理哈希冲突，HashSet有效地保证了元素的唯一性与存储的合理性。