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

Так как я работаю с временной сложностью, я просматривал библиотеку классов 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.

Спасибо.

Ответы

Ответ 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).

Ответ 3

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

Ответ 4

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

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

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