HashMap 方法的时间复杂度

Question

由于我在处理时间复杂度，所以我一直在搜索使用列表、映射和类的一些标准方法的Oracle Java类库中这些方法的时间复杂度。(更具体地说，是ArrayList、HashSet和HashMap)。

现在，在查看HashMap javadoc页面时，他们只真正讨论了get()和put()方法。

我仍需要知道的方法是：

remove(Object o)
size()
values()

我认为remove()的时间复杂度与get()相同，都是O(1)，假设我们没有一个具有相等哈希码的巨大HashMap等等...

对于size()，我也会认为它的时间复杂度是O(1)，因为HashSet（也没有顺序）有一个size()方法，其时间复杂度也是O(1)。

我不确定values()的时间复杂度。我不知道这个方法是否只是“复制”HashMap，从而使时间复杂度为O(1)，还是必须要遍历HashMap，使时间复杂度等于HashMap中存储的元素数量。

谢谢。

- Koeneuze

---

顺便问一下，如果values()只是以某种方式“复制”HashMap，那么它怎么可能达到O(1)的效率呢？ - Pacerier

顺便说一下，你的链接已经失效了。 - Hengameh

请问您在问题中寻找的确切复杂度（平均或最坏）是多少？正如@JavaGuy所指出的那样，remove()的复杂度也会相应不同。 - Dinesh

Answer 1

这里提供的源代码链接可能有所帮助：http://kickjava.com/src/java/util/HashMap.java.htm

• remove: O(1)
• size: O(1)
• values: O(n)（在通过迭代器遍历时）

- b_erb

---

删除已摊销复杂度O（1+a），其中a取决于已删除对象的哈希键槽中有多少项。 - Timofey

@Hengameh a - 是一个负载因子。负载因子是哈希表元素数量与哈希表槽位数量之比。更详细的解释请参考《算法导论》第11.2章哈希表。 - Timofey

通常情况下，在Java中HashMap的插入、删除和搜索的时间复杂度为O（1），这取决于负载因子（哈希表中已有的条目数除以哈希表中总桶数）和哈希函数的映射。这就是为什么简单的搜索可能在最坏的情况下需要O(n)的时间。可以查看我完整的回答，网址为https://dev59.com/8m455IYBdhLWcg3wCPfh#62965423 - Shashankesh Upadhyay

Answer 2

删除代码（例如HashMap中的rt.jar）如下：

/**
 * Removes and returns the entry associated with the specified key
 * in the HashMap.  Returns null if the HashMap contains no mapping
 * for this key.
 */
final Entry<K,V> removeEntryForKey(Object key) {
    int hash = (key == null) ? 0 : hash(key.hashCode());
    int i = indexFor(hash, table.length);
    Entry<K,V> prev = table[i];
    Entry<K,V> e = prev;

    while (e != null) {
        Entry<K,V> next = e.next;
        Object k;
        if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k)))) {
            modCount++;
            size--;
            if (prev == e)
                table[i] = next;
            else
                prev.next = next;
            e.recordRemoval(this);
            return e;
        }
        prev = e;
        e = next;
    }

    return e;
}

显然，最坏情况的时间复杂度为O(n)。

- JavaGuy

---

虽然从技术上讲是正确的，但这个答案可能会误导一些人。只有当HashMap中的所有键具有相同的hashCode时，此代码才为O(n)，这是不太可能或者是一个错误。我认为Tim的评论更加准确。 - Hawkeye Parker

同意@HawkeyeParker的观点，但关键是仍然有效：运行时间=最坏情况=线性。再次强调，这种情况不太可能发生且完全是理论上的，但在我们定义算法效率的方式中，答案必须是线性的，因为存在一种可能性使O(n)成立。 - Clayton C.

所有方法都需要分别报告大O、平均大O和摊销大O吗？ 大O是O(n)（当所有键具有相同的哈希值时），但平均为O(1)。 - baumannalexj

Answer 3

搜索：O(1+k/n)
插入：O(1)
删除：O(1+k/n) 其中k是添加到同一LinkedList的冲突元素数量（k个元素具有相同的hashCode）

插入操作是O(1)，因为您将元素直接添加到LinkedList的头部。

摊销时间复杂度接近于O(1)，前提是使用良好的哈希函数。如果您过于关注查找时间，则可以尝试使用BinarySearchTree来解决冲突，而不是使用Java的默认实现即LinkedList。

- Srujan Kumar Gulla

---

插入的时间复杂度为O(1)，因为你是将元素添加到LinkedList的头部，但仍需要通过遍历列表来检查该元素是否已经存在，这要涉及到关键字和哈希值的比较（参考-源代码）。 - Swapnil

最好使用lookup、put和remove :) - Hengameh

Answer 4

关于上面提到的HashMap在删除和搜索时可能出现最坏情况O(n)的评论，我想补充一下，这种情况不会发生，因为我们谈论的是Java HashMap实现。

对于有限数量（低于64个条目）的情况下，HashMap由数组支持，所以即使在非常不幸的情况下，但仍然很少见，它也是线性的，但从渐进的角度来看，在最坏的情况下，HashMap的时间复杂度应该是O(logN)。

- divjscr

Answer 5

你可以随时查看源代码，自行检查。
无论如何...我曾经查看过源代码，我记得有一个名为size的变量始终保存了HashMap中项的数量，所以size()是O(1)。

- Itay Karo

---

我对Java很新，所以对源代码一无所知，但我会尝试。谢谢！ - Koeneuze

Answer 6

平均而言，HashMap的插入、删除和搜索的时间复杂度为O(1)常数时间。

话虽如此，在最坏的情况下，Java对于搜索、插入和删除需要O(n)的时间。

请注意，HashMap的时间复杂度显然取决于负载因子n/b（哈希表中存在的条目数除以哈希表中的桶的总数）以及哈希函数将每个插入映射到的效率。通过高效我指的是，哈希函数可能将两个非常不同的对象映射到同一个桶中（这称为冲突）。解决冲突的各种方法称为冲突解决技术，例如：

• 使用更好的哈希函数
• 开放地址法
• 链接等

Java使用链接和重新散列来处理冲突。 链接的缺点是在最坏的情况下，删除和搜索需要O(n)的操作。因为所有对象都可能映射到特定的桶中，最终导致链长达到O(n)。

重新审视缺点 Java使用高效的负载因子(n/b)作为重新哈希限制（据我所知，链接似乎需要平均查找操作O(1+(n/b))。如果使用重新哈希且n/b<0.99，则是常数时间）。当表非常大时，重新哈希会失控，在这种情况下，如果我们将其用于实时应用程序，响应时间可能会成为问题。

在最坏的情况下，Java HashMap需要O(n)时间来搜索、插入和删除。

- Shashankesh Upadhyay