java - Java 中 HashSet.contains() 的时间复杂度性能是多少？

Question

我倾向于认为 HashSet.contains(Object)方法在恒定时间内执行。它只是获取一个对象的哈希码，然后在哈希表中查找它。

首先，有人可以确认这是否属实吗？

其次，如果它是真的，是否存在冲突的风险，其中两个对象可能具有相同的哈希码，因此 HashSet 在只有一个时认为它具有两者？

Answer 1

它在 O(1) 预期时间内运行，就像任何哈希表一样(假设哈希函数不错)。它由 HashMap 支持，其中键是对象。

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

contains 方法调用(间接地)HashMap 的 getEntry，其中 key 是您要使用的 Object想知道它是否在 HashSet 中。

如下所示，两个对象可以存储在 HashMap/HashSet 中，即使它们的键被哈希函数映射到相同的值。该方法遍历所有具有相同哈希值的键，并对每个键执行 equals 以找到匹配的键。

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;
     }