HashSet中List搜索复杂度解析

HashSet工作原理概述

HashSet在Java中是一个基于哈希表实现的集合，其底层实际上是通过HashMap来存储元素的。HashSet的每个元素都作为HashMap的一个键，而对应的值则是一个固定的占位符对象。当一个元素被添加到HashSet时，HashMap会为这个元素（键）计算哈希值，并根据哈希值将其存储在内部数组（桶）的特定位置。

HashMap内部存储的每个条目都是一个Node对象，其定义类似如下：

static class Node implements Map.Entry {
    final int hash; // 存储键的哈希值，一旦计算便不可更改
    final K key;    // 键本身
    V value;
    Node next;

    // ...
}

值得注意的是，Node中的hash字段被声明为final，这意味着一旦计算并赋值后，它将不会再改变。在后续的查找（如contains()）、添加（add()）或删除（remove()）操作中，HashSet会直接使用这个已存储的哈希值来定位桶，而不会重新计算元素的哈希值。这是理解HashSet中可变对象行为的关键。

HashSet.contains()的通用时间复杂度

在理想情况下，即哈希值分布均匀，没有大量哈希冲突时，HashSet的contains()操作的平均时间复杂度是O(1)。这是因为通过哈希值可以直接定位到元素所在的桶，然后只需进行少量（通常是常数时间）的比较即可找到目标元素。

然而，在最坏情况下，如果所有元素都哈希到同一个桶中，contains()操作的时间复杂度会退化。在Java 8及更高版本中，当一个桶中的元素数量超过某个阈值时（默认为8），HashMap会将链表结构转换为红黑树，以优化查找性能。因此，在最坏情况下，查找时间复杂度为O(log n)，其中n是HashSet中元素的总数。在Java 8之前，由于桶中元素以链表形式存储，最坏情况下的查找时间复杂度为O(n)。

ArrayList作为HashSet元素时的特殊性

当HashSet存储ArrayList对象时，情况会变得复杂。例如：

HashSet> hs = new HashSet<>();
ArrayList a = new ArrayList<>();
ArrayList b = new ArrayList<>();
ArrayList c = new ArrayList<>();

a.add(1); a.add(2);
b.add(3); b.add(4);
c.add(5); c.add(6);

hs.add(a);
hs.add(b);
hs.add(c);

ArrayList d = new ArrayList<>();
d.add(3); d.add(4);

boolean found = hs.contains(d); // 此时的时间复杂度是多少？

要理解hs.contains(d)的时间复杂度，我们需要考虑两个主要步骤：

1. 计算待查找对象的哈希值： 当调用hs.contains(d)时，首先需要计算d这个ArrayList对象的哈希值。ArrayList的hashCode()方法是根据其内部所有元素的哈希值以及它们的顺序来计算的。这意味着，计算一个ArrayList的哈希值需要遍历其所有元素。如果ArrayList包含m个元素，那么计算其哈希值的时间复杂度为O(m)。

2. 在HashSet中查找： 一旦d的哈希值计算出来，HashSet就会使用这个哈希值去定位到对应的桶，并在桶中查找与d相等的元素。这个查找过程的时间复杂度取决于哈希冲突的情况：平均为O(1)，最坏情况下为O(log n)（Java 8+）或O(n)（Java 7及以前）。

综合以上两点，hs.contains(d)的总时间复杂度为：

• O(m)：在哈希分布良好的情况下，主要开销是计算ArrayList d的哈希值。
• O(log n + m)：在最坏情况下（哈希冲突严重，桶退化为树），需要O(m)来计算哈希，然后O(log n)来遍历树。
• O(n + m)：在Java 7及以前版本的最坏情况下，需要O(m)来计算哈希，然后O(n)来遍历链表。

因此，对于包含m个元素的ArrayList，在HashSet中进行搜索的实际时间复杂度至少是O(m)，因为计算哈希值本身就需要遍历列表。

不建议将可变对象作为HashSet元素或HashMap键

这是一个非常重要的注意事项：强烈不建议将可变对象（如ArrayList）存储在HashSet中，或作为HashMap的键。

原因在于，HashSet（以及HashMap）在添加元素时，会计算该元素的哈希值并存储在内部Node的final hash字段中。如果该元素是可变对象，并且在被添加到HashSet之后其内容发生了改变，那么其hashCode()方法返回的值也会随之改变。

然而，HashSet内部存储的final hash值并不会更新。当后续调用contains()、remove()等方法时，HashSet会使用当前待查找对象的哈希值去定位桶，但由于桶中的元素（原先的那个可变对象）的内部哈希值已经改变，HashSet将无法正确地找到它，即使这个对象实际上还在集合中。

示例：

HashSet> hs = new HashSet<>();
ArrayList list1 = new ArrayList<>();
list1.add(1);
list1.add(2);

hs.add(list1); // list1的哈希值此时基于[1, 2]计算并存储

System.out.println(hs.contains(list1)); // true (哈希值匹配)

// 改变list1的内容
list1.add(3); // list1的哈希值现在基于[1, 2, 3]计算

// 此时，hs内部存储的list1的哈希值仍然是基于[1, 2]的旧值
// 而hs.contains(list1)会计算新的哈希值（基于[1, 2, 3]）去查找
System.out.println(hs.contains(list1)); // 极有可能返回 false，因为哈希值不匹配，导致查找失败

上述代码中，hs.contains(list1)在list1被修改后，很可能返回false，这会造成逻辑错误和难以调试的问题。

注意事项与最佳实践

1. 使用不可变对象： 最好的实践是使用不可变对象（Immutable Objects）作为HashSet的元素或HashMap的键。例如，String、Integer等包装类都是不可变对象，它们的哈希值在创建后不会改变。如果需要存储列表，可以考虑使用Collections.unmodifiableList()将其包装成不可变列表，或者使用List.of()（Java 9+）创建不可变列表。
2. 确保哈希值稳定性： 如果确实需要使用可变对象，请务必确保在将对象添加到HashSet之后，其用于计算hashCode()和equals()方法所依赖的内部状态不再发生改变。这通常意味着在对象加入集合后，不应再修改其内容。
3. 自定义哈希和相等性： 对于自定义的可变类，如果必须用作哈希集合的元素，则需要正确地实现hashCode()和equals()方法。并且，更重要的是，要确保这两个方法所依赖的字段在对象被添加到哈希集合后不再被修改。
4. 替代方案： 如果需要基于可变列表的内容进行动态搜索，并且列表内容可能频繁变化，HashSet可能不是最佳选择。可以考虑其他数据结构或搜索策略，例如使用线性搜索（List.contains()），但其时间复杂度为O(N)，或者构建一个辅助的哈希结构来存储列表的不可变表示（例如，将列表转换为字符串或自定义的不可变列表封装类）。

总结

在HashSet中搜索ArrayList对象的时间复杂度是O(m)（平均情况）或O(log n + m)（最坏情况，Java 8+），其中m是ArrayList的元素数量，n是HashSet中的元素数量。这主要是因为ArrayList的哈希值计算需要遍历其所有元素。更重要的是，将可变对象（如ArrayList）作为HashSet的元素或HashMap的键是一个危险的实践，因为它可能导致哈希值与对象内容不一致，从而使集合无法正确地查找或管理这些对象。为了避免此类问题，应优先使用不可变对象，或严格管理可变对象的生命周期，确保其在加入集合后不再改变哈希相关的内部状态。