36

HashMap には次の実装があることを読みました。

main array 
   ↓
[Entry] → Entry → Entry      ← linked-list implementation
[Entry]
[Entry] → Entry
[Entry]
[null ]

そのため、Entry オブジェクトの配列があります。

質問:

  1. 同じ hashCode で異なるオブジェクトの場合、この配列のインデックスが複数の Entry オブジェクトをどのように格納できるのか疑問に思っていました。

  2. LinkedHashMapこれは実装とどう違うのですか？map の二重連結リストの実装ですが、上記のような配列を維持し、次の要素と前の要素へのポインターをどのように格納しますか?

4

5 に答える 5

84

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

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

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

LinkedHashMap

図と段階的な説明については、http: //www.javamadesoeasy.com/2015/02/linkedhashmap-custom-implementation.html を参照してください。

ありがとう..！！

于 2015-05-04T09:34:10.143 に答える
53

したがって、Entryオブジェクトの配列があります。

ではない正確に。Entryオブジェクトチェーンの配列があります。HashMap.Entryオブジェクトには、オブジェクトを連結リストとして連鎖nextできるフィールドがあります。Entry

Entry同じ hashCode で異なるオブジェクトの場合、この配列のインデックスに複数のオブジェクトをどのように格納できるのか疑問に思っていました。

（質問の写真が示すように）Entryオブジェクトが連鎖しているためです。

LinkedHashMapこれは実装とどう違うのですか？map の二重連結リストの実装ですが、上記のような配列を維持し、次の要素と前の要素へのポインターをどのように格納しますか?

LinkedHashMap実装では、クラスはフィールドを追加してクラスをLinkedHashMap.Entry拡張します。これらのフィールドは、挿入順序を記録する独立した二重リンク リストにオブジェクトを組み立てるために使用されます。そのため、このクラスでは、各エントリ オブジェクトは 2 つの異なるチェーンにあります。HashMap.EntrybeforeafterLinkedHashMap.EntryLinkedHashMap

  • メイン ハッシュ配列を介してアクセスされる単一リンクのハッシュ チェーンが多数あります。これは、(通常の) ハッシュマップ検索に使用されます。

  • すべてのエントリ オブジェクトを含む別の二重リンク リストがあります。エントリの挿入順に保持され、ハッシュマップ内のエントリ、キー、または値を反復するときに使用されます。

于 2013-11-02T05:02:39.067 に答える
13

自分で見てください。今後の参考のために、グーグルで検索できます：

Java LinkedHashMap ソース

HashMapは衝突を処理するために aを使用しますが、とLinkedListの違いは予測可能な反復順序があることです。これは、追加の二重リンク リストによって実現され、通常はキーの挿入順序が維持されます。例外は、キーが再挿入された場合です。この場合、キーはリスト内の元の位置に戻ります。 HashMapLinkedHashMapLinkedHashMap

参考までに、 a を反復する方が a をLinkedHashMap反復するよりも効率的ですHashMapが、LinkedHashMapメモリ効率は低くなります。

上記の説明から明確でない場合、ハッシュ プロセスは同じであるため、通常のハッシュの利点が得られますが、二重にリンクされたリストを使用しているため、上記の反復の利点も得られます。オブジェクトの順序を維持しEntryます。これは、あいまいな場合に備えて、衝突のハッシュ中に使用されるリンク リストとは無関係です。

編集: (OPのコメントに応じて):
AHashMapは配列に支えられており、一部のスロットにEntryは衝突を処理するためのオブジェクトのチェーンが含まれています。すべての (キー、値) ペアを反復処理するには、配列内のすべてのスロットを通過してから、LinkedLists;を通過する必要があります。したがって、全体の時間は容量に比例します。

を使用する場合LinkedHashMap、双方向リンク リストをトラバースするだけでよいため、全体の時間はサイズに比例します。

于 2013-11-02T04:39:30.057 に答える
-1

hashCodeハッシュ関数によって任意のバケットにマッピングされます。衝突が発生した場合は、連鎖によってこの衝突を解決します。つまり、リンクされたリストに値が追加されますhashCode。HashMap以下は、これを行うコードです。

for (Entry<K,V> e = table[i]; e != null; e = e.next) {
392             Object k;
393             if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
394         `enter code here`        V oldValue = e.value;
395                 e.value = value;
396                 e.recordAccess(this);
397                 return oldValue;
398             }
399         }

リンクされたリストをトラバースし、キーが見つかった場合は古い値を新しい値に置き換え、それ以外の場合はリンクされたリストに追加することが明確にわかります。

LinkedHashMapただし、との違いHashMapはLinkedHashMap、挿入順序を維持することです。ドキュメントから：

このリンクされたリストは反復順序を定義します。これは通常、キーがマップに挿入された順序 (挿入順序) です。キーがマップに再挿入されても、挿入順序は影響を受けないことに注意してください。(呼び出しの直前に m.containsKey(k) が true を返すときに m.put(k, v) が呼び出された場合、キー k はマップ m に再挿入されます)。

于 2013-11-02T04:39:02.390 に答える