Сложность времени методов HashMap

Question

Поскольку я работаю над временной сложностью, я искал в библиотеке классов Java-оракула временную сложность некоторых стандартных методов, используемых в списках, картах и ​​классах.(точнее, ArrayList, HashSet и HashMap)

Теперь, глядя на страницу javadoc HashMap , они действительно говорят только о методах 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

Код для удаления (как в 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).

Answer 3

Поиск: O (1 + k / n)
Вставка: O (1)
Удалить: O (1 + k / n), где k - это номер.элементов столкновения, добавленных в один и тот же LinkedList (k элементов имели одинаковый hashCode)

Вставка - это O (1), поскольку вы добавляете элемент прямо в начало LinkedList.

Сложности Amortized Time близкик O (1) дана хорошая хеш-функция.Если вы слишком обеспокоены временем поиска, попробуйте разрешить коллизии, используя BinarySearchTree вместо реализации java по умолчанию, т.е. LinkedList

Answer 4

Вы всегда можете взглянуть на исходный код и проверить его самостоятельно.
В любом случае ... Я однажды проверил исходный код, и я помню, что есть переменная с именем size, которая всегда содержит номерэлементов в HashMap, поэтому size() равно O(1).