Java中HashSet.contains（）的时间复杂度性能如何？

它在预期的时间内运行，就像任何哈希表一样（假设哈希函数是体面的）。它由 一个，其中键是对象。O(1)HashMap

两个对象可能具有相同的哈希代码，但不会认为它们是相同的，除非这些对象的方法说它们是相同的（即返回true）。HashSetequals

的方法调用 （间接） 的 ，其中 key 是您希望知道它是否在 .containsgetEntryHashMapObjectHashSet

如下图所示，两个对象可以存储在 / 中，即使它们的键通过哈希函数映射到相同的值。该方法循环访问具有相同哈希值的所有键，并对每个键执行以查找匹配的键。HashMapHashSetequals

final Entry<K,V> getEntry(Object key) {
         int hash = (key == null) ? 0 : hash(key.hashCode());
         for (Entry<K,V> e = table[indexFor(hash, table.length)];
              e != null;
              e = e.next) {
             Object k;
             if (e.hash == hash &&
                 ((k = e.key) == key || (key != null && key.equals(k))))
                 return e;
         }
         return null;
     }

对于 Java 8，包含的最坏情况性能将是 O（log n），对于 Java 7，则为 O（n），但平均情况更接近 O（1）。这是因为哈希集由哈希映射支持，因此具有与哈希映射查找（即HashMap.get（...））相同的效率。哈希映射中的实际映射是常数时间 （O（1）），但处理冲突的需要带来了记录 n 的成本。也就是说，哈希到同一数组索引的多个元素必须存储在辅助数据结构（也称为存储桶）中，而正是此存储桶决定了最坏情况的性能。在Java中，哈希映射冲突处理是使用自平衡树实现的。

自平衡树保证所有操作的 O（log n），因此，在 hashmap（和 hashset） 中插入和查找的总成本为 O（1） + O（log n） = O（log n）。在Java 8中引入了使用自平衡树进行冲突处理，作为对链接（直到java 7使用）的改进，后者使用链接列表，并且具有最坏的O（n）情况进行查找和插入（因为它需要遍历列表）。请注意，链接将具有恒定的插入时间（与查找相反），因为元素可以添加到O（1）中的链接列表中，但是在哈希映射的情况下，set属性（没有重复项）强加在链表上，因此在插入的情况下也需要遍历链接列表，以确保元素在列表/存储桶中不存在， 我们最终得到O（n）用于插入和查找。

引用：

此类实现 Set 接口，该接口由哈希表（实际上是哈希映射实例）提供支持。https://docs.oracle.com/javase/8/docs/api/java/util/HashSet.html

达到特定阈值后，包含大量冲突键的存储桶会将其条目存储在平衡树中，而不是链接列表。（https://www.nagarro.com/en/blog/post/24/performance-improvement-for-hashmap-in-java-8)