35

関数を介したトラバーサルのHashMapとの間にパフォーマンスの違いはありますか?LinkedHashMapvalues()

4

7 に答える 7

46

LinkedHashMapの優れたnextEntry実装により、トラバーサルを高速化する必要があると思いますIterator

理由は次のとおりです。

values実装から段階的に見ていきましょう。
のHashMap実装valuesは次のとおりです。

public Collection<V> values() {
    Collection<V> vs = values;
    return (vs != null ? vs : (values = new Values()));
}

は同じ実装LinkedHashMap から拡張されHashMap、継承されます。

違いは、両方の のIterator実装にあります。Values

からHashMap伸びるから java.util.HashMap.HashIterator 

private final class ValueIterator extends HashIterator<V> {
    public V next() {
        return nextEntry().value;
    }
}

しかし、LinkedHashMapそれはjava.util.LinkedHashMap.LinkedHashIterator 

private class ValueIterator extends LinkedHashIterator<V> {
    public V next() { return nextEntry().value; }
}

したがって、違いは本質的に実装に帰着しnextEntryます。

LinkedHashMape が である e.after を呼び出すだけですがEntry、次の次を見つけるために配列をHashMapトラバースする作業が必要です。Entry[]

更新nextEntry(): in のコードHashMap

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

Entry[] は連続したストアではありません。(その間に null 値が存在する可能性があります)。上記のコードを見ると、それが行うことは、 current の次をポイントし、 Entry[] を反復処理して次の次を見つけることです。

しかし、このパフォーマンスの向上は、挿入を犠牲にしてもたらされると思います。addEntry演習として、両方のクラスのメソッドを確認してください。

于 2012-10-21T14:43:53.420 に答える
45

Boolean.TRUE に対して 100 万個のキー (Integer) を作成し、100 回繰り返す小さなプロファイリング プログラムを作成しました。以下が見つかりました。

HashMap:-
Create:  3.7sec
Iterate: 1.1sec
Access:  1.5sec
Total:   6.2sec

LinkedHashMap:-
Create:  4.7sec   (30% slower)
Iterate: 0.5sec   (50% faster)
Access:  0.8sec   (50% faster)
Total :  6.0sec

ガベージ コレクションが行われていないため、数値がいくらか汚染されていますが、LinkedHashMap は HashMap よりも有利であり、将来のコードでそれを使用する予定です。

于 2014-04-03T13:20:24.947 に答える
5

ほとんど問題ありません。問題は、何が必要かということです。要素の順序が関係する場合は、 を使用する必要がありますLinkedHashMap。それ以外の場合は必要ないので、使用してHashMapください。

于 2012-10-21T14:25:22.767 に答える
3

最善のアドバイスは「試してみることを恐れないでください」ですが、それらは非常に似ていると確信しています。値セットのゲッターはO（1）であり、各イテレーターステップも同様です。リンクリストを反復処理することは、ハッシュバケットを反復処理するのと同じくらい簡単ですが、リンクリストを優先する可能性のある小さなエッジがあります。

于 2012-10-21T14:21:11.640 に答える
3

はい、すべての繰り返しで得られるのと同じパフォーマンスの違いがあります: エントリの数とHashMapハッシュテーブルのサイズに比例して時間がかかり、エントリの数に比例して時間がかかります.LinkedHashMapHashMapLinkedHashMap

于 2012-10-21T18:53:08.127 に答える
3

私は UnitTest で試してみましたが、values() を 10000 回繰り返し、ミリ秒は 806 対 902 でした。ほぼ同じです。

于 2012-10-21T14:29:54.197 に答える