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中的元素.

谢谢.

Answer 1

源代码通常很有帮助:http://kickjava.com/src/java/util/HashMap.java.htm

• remove: O(1)
• size: O(1)
• values: O(n)(遍历迭代器)

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).