HashSet.equals()是否在恒定时间内运行？

Question

只是想知道是否HashSet.equals(anotherHashSet)在恒定时间内运行(也使用ConcurrentHashSetas参数),我认为这样做是出于效率原因.看不到任何提到它的东西,我正在构建的框架的一部分依赖于功能(不希望它花费太长时间!).

编辑:抱歉,意识到HashSet.equals()无法在恒定时间内运行,因为元素可以更改,而地图中元素的哈希码保持不变.因此,解决此问题的最佳方法是使用哈希码.虽然味道很难闻到吗？

Answer 1

查看典型的实现表明它确实如此containsAll.每个包含的检查都将是O(1),并且必须进行N个,所以我认为O(N).

Answer 2

据我从代码中看到 - 它以线性时间运行。迭代集合并比较每个元素：

equals(..) inAbstractSet调用containsAll(..)in AbstractCollection，它获取迭代器并调用contains(..)每个元素，然后调用map.containsKey(..)which is O(1)。所以O(n)如果我没记错的话。