46

LinkedHashMapの時間計算量がHashMapの複雑さと同じである場合、なぜHashMapが必要なのですか？JavaのHashMapと比較した場合、LinkedHashMapの余分なオーバーヘッドはどれくらいですか？

4

8 に答える 8

44

LinkedHashMapはより多くのメモリを使用します。通常の各エントリにHashMapは、キーと値があります。各LinkedHashMapエントリには、それらの参照と、次および前のエントリへの参照があります。通常は関係ありませんが、やるべきハウスキーピングももう少しあります。

于 2010-06-11T06:29:55.470 に答える
30

LinkedHashMapの時間計算量がHashMapの複雑さと同じである場合、なぜHashMapが必要なのですか？

複雑さとパフォーマンスを混同しないでください。2つのアルゴリズムは同じ複雑さを持つことができますが、一方は他方よりも一貫して優れたパフォーマンスを発揮できます。

つまり、次のことを覚えておいてくださいf(N) is O(N)。

limit(f(N), N -> infinity) <= C*N

ここCで、は定数です。C複雑さは、値がどれほど小さいか大きいかについては何も言いません。2つの異なるアルゴリズムの場合、定数Cはおそらく異なります。

（そして、big-Oの複雑さは、非常に大きくなるにつれての動作/パフォーマンスに関するものであることを忘れないでください。小さな値の場合Nの動作/パフォーマンスについては何もわかりません。）N

そうは言っても：

  • HashMapと同等のユースケースでの操作のパフォーマンスの違いLinkedHashMapは比較的小さいです。

  • ALinkedHashMapはより多くのメモリを使用します。たとえば、Java 11実装には、前後のリストを表すために、各マップエントリに2つの追加の参照フィールドがあります。圧縮されたOOPのない64ビットプラットフォームでは、追加のオーバーヘッドはエントリあたり16バイトです。

  • パフォーマンスやメモリ使用量の比較的小さな違いは、パフォーマンスやメモリが重要なアプリケーションを使用している人にとって実際には非常に重要です1。

1-...そしてこれらのことに不必要に執着している人々にも。

于 2010-06-11T06:43:40.930 に答える
16
  • LinkedHashMapはさらに、そのすべてのエントリを実行する二重リンクリストを維持します。これにより、再現可能な順序が提供されます。このリンクリストは、反復順序を定義します。これは通常、キーがマップに挿入された順序（挿入順序）です。
  • HashMapにはこれらの追加コスト（実行時間、スペース）がないため、挿入順序を気にしない場合はLinkedHashMapよりも優先する必要があります。
于 2010-06-11T06:31:48.010 に答える
9

LinkedHashMapは、マップへのキーの挿入順序を知る必要がある場合に役立つデータ構造です。適切なユースケースの1つは、LRUキャッシュの実装です。LinkedHashMapの順序が維持されるため、データ構造にはHashMapと比較して追加のメモリが必要です。挿入順序が必須ではない場合は、常にHashMapを使用する必要があります。

于 2010-06-11T06:35:45.930 に答える
7

HashMapとLinkedHashMapには、もう1つの大きな違いがあります。LinkedHashMapの場合、反復がより効率的になります。

LinkedHashMapの要素は相互に接続されているため、反復には、容量に関係なく、マップのサイズに比例した時間が必要です。しかし、HashMapの場合; 固定された順序がないため、反復には容量に比例した時間が必要です。

ブログに詳細を載せました。

于 2012-12-28T11:10:20.830 に答える
2

HashMap挿入順序を維持しないため、二重リンクリストを維持しません。

の最も顕著な特徴はLinkedHashMap、キーと値のペアの挿入順序を維持することです。LinkedHashMapそのために二重リンクリストを使用します。

のエントリはLinkedHashMap次のようになります。

  static class Entry<K, V> {
     K key;
     V value;
     Entry<K,V> next;
     Entry<K,V> before, after;        //For maintaining insertion order    
     public Entry(K key, V value, Entry<K,V> next){
         this.key = key;
         this.value = value;
         this.next = next;
     }
  }

前後を使用することにより、に新しく追加されたエントリを追跡しLinkedHashMap、挿入順序を維持するのに役立ちます。

前のエントリを参照する前と後はの次のエントリを参照しLinkedHashMapます。

図とステップバイステップの説明については、http： //www.javamadesoeasy.com/2015/02/linkedhashmap-custom-implementation.htmlを参照してください。

于 2015-05-04T09:41:02.360 に答える
1

LinkedHashMapはHashMapを継承します。つまり、HashMapの既存の実装を使用して、キーと値をノード（エントリオブジェクト）に格納します。これ以外に、キーが入力された挿入順序を維持するために、別個の二重リンクリスト実装を格納します。

このように見えます：

ヘッダーノード<--->ノード1<--->ノード2<--->ノード3<---->ノード4<--->ヘッダーノード。

したがって、余分な過負荷は、この二重リンクリストでの挿入と削除を維持しています。利点は次のとおりです。反復順序は、HashMapにはない挿入順序であることが保証されています。

于 2014-02-01T18:33:47.623 に答える
0
  • 内容を新しいテーブル配列に転送するために二重リンクリストを反復処理するため、サイズ変更の方が高速であると考えられます。
  • containsValue（）は、より高速なイテレータを利用するためにオーバーライドされます。
  • LinkedHashMapを使用して、LRUキャッシュを作成することもできます。特別なLinkedHashMap（capacity、loadFactor、accessOrderBoolean）コンストラクターが提供され、反復の順序が、エントリが最後にアクセスされた順序（最近アクセスされた順序から最近アクセスされた順序）になります。この場合、get（）を使用してマップをクエリするだけで、構造が変更されます。
于 2013-02-05T13:54:25.240 に答える