面试题：Java中HashSet如何实现高效查找

Question

请简述Java HashSet内部实现高效查找的机制，涉及到哪些关键方法和数据结构，以及它们是如何协同工作来保证查找效率的。

Answer 1

1. 关键数据结构：
   • 哈希表（本质上是数组 + 链表/红黑树）：HashSet内部使用HashMap来存储元素。HashMap是基于哈希表实现的，它有一个数组，数组中的每个位置称为桶（bucket）。当向HashSet添加元素时，会根据元素的哈希值决定该元素应放入数组的哪个桶中。
2. 关键方法：
   • hashCode()方法：
     • 当向HashSet中添加一个元素时，首先调用该元素的hashCode()方法。这个方法会返回一个哈希码值。这个哈希码值是一个整数，它在一定程度上标识了该对象的特征。
     • 例如，对于自定义类Person，如果重写了hashCode()方法，可以根据Person的关键属性（如姓名、年龄等）来生成哈希码。
   • equals()方法：
     • 假设两个不同对象的哈希码值通过哈希函数计算后映射到了哈希表数组的同一个桶中（即发生了哈希冲突）。此时，HashSet会调用这两个对象的equals()方法来进一步判断它们是否相等。
     • 如果equals()方法返回true，则认为这两个对象在逻辑上是相同的，HashSet不会将第二个对象添加进去（因为HashSet不允许重复元素）。如果equals()方法返回false，则会将第二个对象以链表（JDK 1.8之前）或红黑树（JDK 1.8及之后，当链表长度达到一定阈值时会转换为红黑树）的形式挂在该桶的位置上。
3. 协同工作保证查找效率：
   • 快速定位桶：通过hashCode()方法生成的哈希码，经过哈希函数计算，可以快速定位到元素应该存储在哈希表数组中的哪个桶位置。这一步大大缩小了查找范围，使得平均情况下查找一个元素只需要O(1)的时间复杂度（理想情况下，即没有哈希冲突时）。
   • 处理哈希冲突：当发生哈希冲突时，通过equals()方法精确判断元素是否相同。在JDK 1.8之前，冲突的元素以链表形式存储在桶中，查找时需要遍历链表，时间复杂度为O(n)（n为链表长度）。而在JDK 1.8及之后，当链表长度达到一定阈值（默认为8）时，链表会转换为红黑树，红黑树的查找时间复杂度为O(log n)，进一步提高了在冲突情况下的查找效率。