1. 哈希集合与可变对象：潜在陷阱
在Java中，HashSet和HashMap等基于哈希的集合，其性能和正确性高度依赖于存储对象的hashCode()和equals()方法的实现。当一个对象被添加到HashSet中时，它的哈希值会被计算并用于确定其在内部哈希表中的存储位置（桶）。此哈希值通常被存储为Node内部的一个final字段，这意味着一旦对象被添加，其哈希值就不会再重新计算。
因此，将可变对象（如ArrayList）存储在HashSet或用作HashMap的键是不被推荐的做法。如果一个可变对象在被添加到集合后其内容发生了改变，导致其hashCode()返回不同的值，那么当尝试通过其新的哈希值查找该对象时，它可能无法被正确检索到，因为集合仍然会尝试在旧的哈希值对应的位置查找。
2. HashSet内部机制与时间复杂度
HashSet底层是基于HashMap实现的，它将元素作为HashMap的键，而值则是一个虚拟的占位符对象。HashMap内部使用Node来存储键值对，其结构大致如下：
static class Node<K,V> implements Map.Entry<K,V> {
final int hash; // 存储键的哈希值，一旦计算，不再改变
final K key; // 键
V value; // 值
Node<K,V> next; // 链表下一个节点
// ... 构造器及方法
}当调用contains()、add()等方法时，HashSet会首先计算传入参数的哈希值，然后根据这个哈希值定位到对应的桶。接着，它会遍历该桶中的链表（或红黑树，Java 8+优化），通过equals()方法逐一比较元素。
立即学习“Java免费学习笔记（深入）”；
2.1 contains()操作的一般时间复杂度
在理想情况下，即哈希值分布均匀，极少发生哈希冲突时：
- contains()操作的平均时间复杂度为 O(1)。这是因为通过哈希值可以直接定位到桶，并且桶中元素数量极少。
在最坏情况下，即所有元素都哈希到同一个桶中时：
- 在Java 7及更早版本中，同一个桶中的元素以链表形式存储，此时contains()操作需要遍历整个链表，时间复杂度为 O(n)，其中n是集合中元素的总数。
- 在Java 8及更高版本中，当一个桶中的链表长度超过某个阈值（默认为8）时，链表会自动转换为红黑树。此时，contains()操作在遍历该桶时的时间复杂度会优化为 O(log n)。
3. 搜索ArrayList<Integer>的时间复杂度分析
现在，我们考虑一个具体的场景：在HashSet<ArrayList<Integer>>中搜索一个ArrayList<Integer>对象。
HashSet<ArrayList<Integer>> hs = new HashSet<>(); // ... 省略添加元素代码 ... ArrayList<Integer> d = new ArrayList<>(); d.add(3); d.add(4); hs.contains(d); // 这个操作的时间复杂度是多少？
当执行hs.contains(d)时，其时间复杂度由两部分组成：
计算传入参数d的哈希值：ArrayList的hashCode()方法是根据其所有元素的哈希值计算的。这意味着，为了计算d的哈希值，需要遍历d中的所有元素并累加它们的哈希值。如果d包含m个元素，那么计算d.hashCode()的时间复杂度为 O(m)。
-
在HashSet中查找： 一旦d的哈希值计算完毕，HashSet会使用这个哈希值来定位到对应的桶，并进行元素比较。
- 在哈希分布均匀的平均情况下，查找桶内元素的时间复杂度为 O(1)。
- 在哈希冲突严重的最坏情况下（Java 8+），查找桶内元素的时间复杂度为 O(log n)，其中n是集合中元素的数量。
综合以上两点，hs.contains(d)的整体时间复杂度如下：
平均情况：O(m) 这是因为计算传入参数d的哈希值（O(m)）是主要的时间消耗，而随后的桶内查找通常是O(1)。
最坏情况：O(log n + m) (Java 8+) 或 O(n + m) (Java 7-) 在这种情况下，m代表计算d的哈希值的时间，log n（或n）代表在哈希冲突严重时遍历桶内结构的时间。
总结： 尽管HashSet的平均查找时间是O(1)，但当其元素是ArrayList这种可变集合类型时，由于每次搜索都需要计算传入参数ArrayList的哈希值，这个计算过程本身就取决于列表的长度m。因此，对于ArrayList的搜索操作，时间复杂度至少是O(m)。
4. 注意事项与最佳实践
- 避免使用可变对象作为哈希集合元素或映射键： 除非你能确保这些对象在被添加到集合后永不改变其内容，否则应避免使用它们。如果必须使用，请确保在对象内容改变时将其从集合中移除，修改后重新添加。
-
确保hashCode()和equals()契约的正确实现： 对于自定义对象，务必正确地实现hashCode()和equals()方法，确保它们遵循Java规范：
- 如果两个对象通过equals()方法比较为相等，那么它们的hashCode()方法必须产生相同的整数结果。
- 如果两个对象的hashCode()方法产生相同的整数结果，它们不一定通过equals()方法比较为相等（哈希冲突是允许的）。
- hashCode()的实现应尽可能地将不同的对象分散到不同的哈希值，以减少哈希冲突，从而提高哈希集合的性能。
- 考虑使用不可变对象： 如果可能，将ArrayList<Integer>替换为不可变集合，例如List.of()创建的列表（Java 9+），或使用ImmutableList（Guava库）。这样可以保证对象的哈希值在创建后保持不变。
通过理解HashSet的内部工作原理及其对hashCode()和equals()的依赖，我们可以更有效地使用哈希集合，并避免潜在的性能问题和逻辑错误。
