哈希映射方法的时间复杂性

time-complexity hashmap methods java

2022-09-01 10:45:15

由于我正在研究时间复杂性，因此我一直在通过oracle Java类库搜索列表，映射和类上使用的一些标准方法的时间复杂性。（更具体地说，ArrayList，HashSet和HashMap）

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

我仍然需要知道的方法是：

remove(Object o)
size()
values()

我认为这将是与，，相同的复杂性，假设我们没有一个具有相等哈希码的巨型哈希图，等等......remove()get()O(1)

对于我也假设，因为一个没有顺序的HashSet有一个具有复杂性的方法。size()O(1)size()O(1)

我不知道的是 - 我不确定这种方法是否会以某种方式“复制”HashMap，给出的时间复杂度，或者它是否必须迭代HashMap，使复杂性等于存储在HashMap中的元素数量。values()O(1)

谢谢。

答案 1

来源通常是有帮助的：http://kickjava.com/src/java/util/HashMap.java.htm

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

答案 2

删除的代码（如在 rt.jar 中对于 HashMap）是：

/**
 * 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）。