13

LinkedHashMap は本質的に LIFO または FIFO ですか? 私のマップが次の形式の場合：

map.put(1,"one");
map.put(2,"two");

キーセットを使用してマップを反復する場合、順序はどうなりますか??

編集：私は実際に2つの異なる概念を混同したと思います. 質問を言い換えさせてください。entryset を使用して数量に遭遇する順序はどうなりますか?ところで、それを指摘してくれてありがとう。エントリを削除するつもりはありません。

4

4 に答える 4

14

リンクされたハッシュマップでは、バッキングの二重リンクリストの要素が最後に追加されますが (明らかに: 反復順序を維持するため)、要素がマップから削除されると、リストの任意の部分から削除できます。これは正しくありません。バッキング リスト (および拡張: マップ) に LIFO または FIFO のラベルを付けます。どちらでもありません。マップには削除順序の概念がないため、リンクされたハッシュ マップのバッキング リストに対して削除順序を想定することはできません。

リンクされたハッシュ マップが保証するのは、その内容 (キーまたはエントリ) の反復処理が、要素がマップに挿入された順序と同じ順序で行われることです。ドキュメントから：

この実装が HashMap と異なる点は、そのすべてのエントリを実行する二重リンク リストを維持することです。この連結リストは反復順序を定義します。これは通常、キーがマップに挿入された順序 (挿入順序) です。

編集 ：

質問の最後の編集に関して、の反復順序が要素が挿入された順序と同じであることをLinkedHashMap 保証します。質問の例の場合。これは FIFO/LIFO とは関係ありません。これらの概念は、要素がデータ構造から削除される順序を扱い、要素を挿入した後の反復順序とは関係ありません。keySet()1, 2

于 2012-06-16T18:50:05.930 に答える
7

javadocsから引用する LinkedHashMapは、「Map インターフェースのハッシュ テーブルとリンク リストの実装であり、反復順序は予測可能です」です。そのため、keySetは挿入の順序、本質的に FIFOに基づいてキーを返します。

于 2012-06-16T18:48:21.223 に答える
1

アクセス順序が使用されていない場合 (標準的なケース)、LHM は、キーによる O(1) への非常に高速なアクセスを備えたリンク リストと見なすことができます。

その点では、アクセス順序が使用されていない場合は FIFO です (c-tors を見てください)。get()アクセス順序が使用される場合、挿入順序は、エントリの順序を変更する操作があるかどうかに関係ありません。eldest protected boolean removeEldestEntry(Map.Entry<K,V> eldest) =FIFO を見てください。

基本的に、LHM はMap.Entry<Key, Value>、キーにハッシュ インデックスを付けた優れた二重リンク リストです。私自身、現在の impl のようにバニラの HashMap を使用することはありません。LHM よりも利点はほとんどありません。メモリ フットプリントは低くなりますが、反復処理は恐ろしいものです。Java8 (または 9) で最終的に HashMap が修正される可能性があります。Doug Lea が実装をプッシュすることを願っています。

于 2012-06-16T19:36:10.717 に答える
1

Java docs によると、マップを反復処理する場合、キーセットは挿入順になります。したがって、取得する最初のキーは、既存のキーに対して最初に入力されたキーです。キーと値のペアを再挿入しても、元のキーの位置は変更されないことに注意してください。

于 2012-06-16T18:54:08.910 に答える