Java HashSet 最坏情况查找时间复杂度

Question

如果 hashtables/maps 封闭散列是最坏的情况 O(n)，HashSet 是否也需要 O(n) 时间进行查找，还是常数时间？

Answer 1

当在 HashMap 中查找元素时，它执行 O(1) 计算以找到正确的桶，然后连续迭代那里的项目，直到找到等于 the 的那个请求密钥，或检查所有项目。

在最坏的情况下，地图中的所有项目都具有相同的哈希码，因此存储在同一个桶中。在这种情况下，您需要连续迭代所有这些，这将是一个 O(n) 操作。

A HashSet 只是一个 HashMap，您不关心值，只关心键 - 在引擎盖下，它是一个 HashMap，其中所有值都是虚拟 Object.

Answer 2

如果您查看 HashSet 的实现（例如来自 OpenJDK 8：https://hg.openjdk.java.net/jdk8/jdk8/jdk/file/687fd7c7986d/src/share/classes/java/util/HashSet.java），您会发现它实际上只是构建在 HashMap 之上。相关代码片段在这里：

public class HashSet<E>

    extends AbstractSet<E>

    implements Set<E>, Cloneable, java.io.Serializable

{
    private transient HashMap<E,Object> map;

    // Dummy value to associate with an Object in the backing Map

    private static final Object PRESENT = new Object();

    /**

     * Constructs a new, empty set; the backing <tt>HashMap</tt> instance has

     * default initial capacity (16) and load factor (0.75).

     */

    public HashSet() {

        map = new HashMap<>();

    }

    public boolean add(E e) {

        return map.put(e, PRESENT)==null;

    }

HashSet 尝试通过创建一个名为 PRESENT 的静态空对象值并将其用作每个 key/value 条目的值部分来稍微优化内存使用HashMap.

因此，无论使用 HashMap 对性能有何影响，HashSet 都会或多或少具有相同的性能，因为它实际上是在幕后使用 HashMap。

直接回答你的问题：在最坏的情况下，是的，正如 HashMap 的最坏情况复杂度是 O(n)，[=11 的最坏情况复杂度也是如此=] 是 O(n).

值得注意的是，除非您的散列函数非常糟糕或使用的散列表小得离谱，否则您在实践中不太可能看到最坏情况下的性能。您必须将每个元素散列到哈希表中完全相同的存储桶中，这样性能基本上会降低到链表遍历（假设哈希表使用链接进行冲突处理，Java 这样做）。

Answer 3

如前所述，最坏的情况是 O(N)，平均和摊销运行时间是常数。

来自 GeeksForGeeks： HashSet 的底层数据结构是哈希表。因此，HashSet 的添加、删除和查找（包含方法）操作的摊销（平均或通常情况）时间复杂度需要 O(1) 时间。

Answer 4

我看到很多人说最坏的情况是 O(n)。这是因为旧的 HashSet 实现曾经使用 LinkedList 来处理对同一桶的冲突。然而，这并不是一个确定的答案。

在java8中，当一个bucket的碰撞次数增加时，这样的LinkedList被一个平衡二叉树所取代。这将查找的最坏情况性能从 O(n) 提高到 O(log n)。

您可以在此处查看更多详细信息。

Java HashSet 最坏情况查找时间复杂度

Java HashSet worst case lookup time complexity

java

performance

big-o

hashmap

hashset