Leistungsüberlegungen für keySet () und entrySet () von Map

Alle,

Kann mir bitte jemand genau mitteilen, was die Leistungsprobleme zwischen den beiden sind? Die Site: CodeRanch bietet einen kurzen Überblick über die internen Aufrufe, die bei Verwendung von keySet () und get () erforderlich wären. Es wäre jedoch großartig, wenn jemand genaue Angaben zum Ablauf machen könnte, wenn die Methoden keySet () und get () verwendet werden. Dies würde mir helfen, die Leistungsprobleme besser zu verstehen.

Dies hängt zunächst ganz davon ab, welchen Kartentyp Sie verwenden. Da der JavaRanch-Thread jedoch über HashMap spricht, gehe ich davon aus, dass dies die Implementierung ist, auf die Sie sich beziehen. Nehmen wir auch an, Sie sprechen von der Standard-API-Implementierung von Sun / Oracle.

Zweitens, wenn Sie sich Sorgen über die Leistung beim Durchlaufen Ihrer Hash-Map machen, sollten Sie sich diese ansehen LinkedHashMap. Aus den Dokumenten:

Das Durchlaufen der Sammlungsansichten einer LinkedHashMap erfordert unabhängig von ihrer Kapazität Zeit, die proportional zur Größe der Karte ist. Die Iteration über eine HashMap ist wahrscheinlich teurer und erfordert Zeit proportional zu ihrer Kapazität.

HashMap.entrySet ()

Der Quellcode für diese Implementierung ist verfügbar. Die Implementierung gibt im Grunde nur eine neue zurück HashMap.EntrySet. Eine Klasse, die so aussieht:

private final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
    public Iterator<Map.Entry<K,V>> iterator() {
        return newEntryIterator(); // returns a HashIterator...
    }
    // ...
}

und HashIteratorsieht aus wie

private abstract class HashIterator<E> implements Iterator<E> {
    Entry<K,V> next;    // next entry to return
    int expectedModCount;   // For fast-fail
    int index;      // current slot
    Entry<K,V> current; // current entry

    HashIterator() {
        expectedModCount = modCount;
        if (size > 0) { // advance to first entry
            Entry[] t = table;
            while (index < t.length && (next = t[index++]) == null)
                ;
        }
    }

    final Entry<K,V> nextEntry() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        Entry<K,V> e = next;
        if (e == null)
            throw new NoSuchElementException();

        if ((next = e.next) == null) {
            Entry[] t = table;
            while (index < t.length && (next = t[index++]) == null)
                ;
        }
    current = e;
        return e;
    }

    // ...
}

Da haben Sie es also ... Das ist der Code, der vorschreibt, was passieren wird, wenn Sie ein entrySet durchlaufen. Es geht durch das gesamte Array, das so lang ist wie die Kartenkapazität.

HashMap.keySet () und .get ()

Hier müssen Sie zuerst den Schlüsselsatz beschaffen. Dies benötigt Zeit proportional zur Kapazität der Karte (im Gegensatz zur Größe für die LinkedHashMap). Danach rufen Sie get()für jede Taste einmal auf. Sicher, im Durchschnitt dauert dies bei einer guten HashCode-Implementierung eine konstante Zeit. Allerdings wird es zwangsläufig viele erfordern .hashCodeund .equalsAnrufe, die offensichtlich mehr Zeit in Anspruch nehmen als nur einen tun entry.value()Anruf.

Der häufigste Fall, in dem die Verwendung von entrySet gegenüber keySet vorzuziehen ist, besteht darin, dass Sie alle Schlüssel / Wert-Paare in einer Map durchlaufen.

Das ist effizienter:

for (Map.Entry entry : map.entrySet()) {
    Object key = entry.getKey();
    Object value = entry.getValue();
}

als:

for (Object key : map.keySet()) {
    Object value = map.get(key);
}

Denn im zweiten Fall wird für jeden Schlüssel im keySet die map.get()Methode aufgerufen, die - im Fall einer HashMap - erfordert, dass die hashCode()und equals()-Methoden des Schlüsselobjekts ausgewertet werden, um den zugehörigen Wert * zu finden. Im ersten Fall entfällt diese zusätzliche Arbeit.

Bearbeiten: Dies ist noch schlimmer, wenn Sie eine TreeMap in Betracht ziehen, bei der ein abzurufender Aufruf O (log2 (n)) ist, dh der Komparator für Testament muss möglicherweise log2 (n) Mal (n = Größe der Karte) ausführen, bevor er gefunden wird der zugehörige Wert.

* Einige Map-Implementierungen verfügen über interne Optimierungen, die die Identität der Objekte vor dem hashCode()und überprüfen equals().

Hier ist der Link zu einem Artikel , in dem die Leistung von und verglichen entrySet()wird , sowie Ratschläge, wann die einzelnen Ansätze verwendet werden sollen.keySet()values()

Anscheinend ist die Verwendung von keySet()schneller (außer bequemer) als entrySet()solange Sie Map.get()die Werte nicht benötigen .