最坏的情况是o（n），如前所述，平均和摊销运行时间是常数。
来自geeksforgeks：hashset的底层数据结构是hashtable。所以hashset的add、remove和查找（contains method）操作的摊销（平均或通常情况）时间复杂度需要o（1）个时间。

如果你看一个 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 把它作为 HashMap .
所以不管使用 HashMap ，一个 HashSet 会有更多或更少的相同的，因为它的字面上使用 HashMap 在被子下面。
直接回答你的问题：在最坏的情况下，是的，就像一个最坏的情况一样复杂 HashMap 是 O(n) 最坏情况下的复杂性 HashSet 是 O(n) .
值得注意的是，除非你有一个非常糟糕的散列函数，或者你正在使用一个小得离谱的散列表，否则你不太可能在实践中看到最糟糕的性能。您必须将每个元素散列到哈希表中完全相同的bucket中，这样性能基本上会降低到链表遍历（假设哈希表使用链表进行冲突处理，java就是这样做的）。

在中查找元素时 HashMap ，它执行一个o（1）计算以找到正确的bucket，然后依次迭代其中的项，直到找到与请求的键相等的项，或者检查所有项。
在最坏的情况下，Map中的所有项都具有相同的哈希代码，因此存储在同一个bucket中。在这种情况下，您需要串行地迭代所有这些操作，这将是一个o（n）操作。
一 HashSet 只是一个 HashMap 在这里你不在乎价值，只在乎钥匙-在引擎盖下，这是一个 HashMap 所有的值都是伪值 Object .