MapのkeySet()とentrySet()のパフォーマンスに関する考察

質問

すべて

どなたか、2 つの間のパフォーマンスの問題を正確に教えていただけませんか？サイト: CodeRanch というサイトでは、keySet()とget()を使用する際に必要となる内部呼び出しの概要が説明されています。しかし、keySet() と get() メソッドを使用したときのフローについて、正確な詳細を提供していただけると助かります。これは、パフォーマンスの問題をよりよく理解するのに役立つと思います。

どのように解決するのですか？

まず第一に、これはあなたが使っているMapのタイプに完全に依存します。しかし、JavaRanch のスレッドでは HashMap について話しているので、それがあなたが参照している実装であると仮定します。そして、Sun/Oracleの標準API実装について話していると仮定しましょう。

次に、ハッシュマップを反復処理する際のパフォーマンスについて懸念しているのであれば、以下を参照することをお勧めします。 LinkedHashMap . docsから。

LinkedHashMap のコレクションビューに対する反復は、その容量に関係なく、マップのサイズに比例した時間を必要とします。HashMap に対する反復はより高価になり、その容量に比例した時間を必要とする可能性があります。

HashMap.entrySet()

この実装のソースコードが公開されています。この実装は基本的に新しい HashMap.EntrySet . このようなクラスです。

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

というように HashIterator は次のようになります。

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;
    }

    // ...
}

さて、これで完成です... これが、entrySetを繰り返し処理するときに起こることを指示するコードです。これは、マップの容量と同じ長さの配列全体を走査します。

HashMap.keySet()と.get()

ここでは、まずキーの集合を取得する必要があります。これは 容量 に比べて）マップの サイズ である)。これが終わった後、あなたは get() を各キーに対して一度ずつ呼び出します。もちろん、平均的なケースでは、優れたhashCodeの実装では、これは一定の時間を要します。しかし、これは必然的に多くの .hashCode と .equals を呼び出すことになるので、単に entry.value() を呼び出すよりも明らかに時間がかかります。