存储ArrayList的HashSet调用contains方法的时间复杂度疑问

先把你的示例代码贴出来方便参考：

HashSet<ArrayList<Integer>> hs = new HashSet<>();
ArrayList<Integer> a = new ArrayList<>();
ArrayList<Integer> b = new ArrayList<>();
ArrayList<Integer> 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<Integer> d = new ArrayList<>();
d.add(3);
d.add(4);
hs.contains(d); // 该操作的时间复杂度是多少？

问题核心：hs.contains(d)的时间复杂度是O(1)、O(n)还是O(n*m)？ #

嘿，这个问题问得很到位，刚好是FAANG面试里喜欢考察的集合底层细节点！让我一步步给你拆解清楚：

首先，我们得结合HashSet的contains底层逻辑，再搭配ArrayList的hashCode和equals实现来分析：

1. 第一步：计算待查找元素的哈希值
   HashSet底层依赖HashMap，执行contains时首先会计算d的hashCode。而ArrayList的哈希值计算规则是遍历所有元素，通过公式hashCode = 31 * hashCode + element.hashCode()累加得到——这意味着计算d的哈希值需要遍历它的m个元素，时间是O(m)。

2. 第二步：定位哈希桶并执行元素比较
   根据哈希值找到对应的哈希桶后，需要在桶内的元素中逐个用equals方法和d比较：

   • 理想情况（哈希分布均匀，无冲突）：桶内只有一个元素，此时只需要一次equals比较。而ArrayList的equals会遍历两个列表的所有元素逐一比对，这一步也是O(m)。不过你的选项里没有O(m)这个选项，我们重点看面试中更常考察的最坏情况。
   • 最坏情况（极端哈希冲突）：如果d的哈希值和HashSet中所有n个ArrayList的哈希值完全相同（比如所有列表的元素哈希值组合刚好碰撞），那么需要遍历HashSet里的全部n个列表，每个列表都要和d执行一次O(m)的equals比较。此时总时间复杂度就是O(n*m)。

为什么不是O(1)？因为O(1)是哈希表理想情况下的平均时间，但这里的元素是ArrayList，它的哈希计算和相等判断都不是常数时间操作，所以即使哈希无冲突，也达不到O(1)。而O(n)的情况也不成立，因为每个相等判断都需要遍历m个元素，不可能只花O(n)的时间。

所以结论是：最坏时间复杂度为O(n*m)。

内容的提问来源于stack exchange，提问作者Sherlock Holmes