12

Javadoc から:
Hash table and linked list implementation of the Map interface, with predictable iteration order. This implementation differs from HashMap in that it maintains a doubly-linked list running through all of its entries.

もしそうなら、java の List のようなオブジェクト アクセスを提供しないのはなぜですか、list.get(index);

アップデート

LinkedHashMap を使用して LRU キャッシュを実装しました。私のアルゴリズムでは、キャッシュから LRU オブジェクトにアクセスする必要がありました。そのため、ランダムアクセスが必要でしたが、パフォーマンスが低下すると思われるため、ロジックを変更し、キャッシュがいっぱいになったときに LRU オブジェクトにアクセスしています... removeEldestEntry() を使用しています

皆さん、ありがとうございました...

4

6 に答える 6

15

a）エントリはリンクされているため、ランダムにアクセスできません。O(N)私がエラーを起こさなければ 、パフォーマンスは悲惨なものになるでしょう。

b）この機能をバックアップするためのインターフェースがないため。したがって、この（パフォーマンスの悪い）実装専用のインターフェイスを導入するか、クライアントにインターフェイスではなく実装クラスに対してプログラムするように要求するかを選択します。

ところで、Guavaには簡単な解決策があります。

Iterables.get(map.values(), offset);

キャッシングについては、GuavaMapMakerとその有効期限機能をご覧ください。

于 2011-04-14T17:04:50.830 に答える
7

値のバッキング コレクションを提供するためvalues()、次のように解決できます。

map.values().remove(map.values().toArray()[index]);

おそらくあまり効率的ではありませんが（特にメモリに関して）、O(N)期待どおりになるはずです。

Listところで、質問はすべての操作で正当だと思います。（とにかく遅くないはずLinkedListですよね？）

LinkedHashMapListを拡張し、インターフェイスLinkedHashMapを実装することに着手しました。List驚くべきことに、remove の競合のため、実行できないようです。既存のremoveメソッドは以前にマップされたオブジェクトを返しますが、List.removeはboolean.

それは単なる反省であり、正直なところ、 を のLinkedHashMapように扱うことができないことも煩わしいと思いLinkedListます。

于 2011-04-14T17:20:33.110 に答える
3

Apache Commons LinkedMapをご覧ください。

于 2011-04-14T17:12:06.397 に答える
1

これはIteratorインターフェースを提供し、リスト内の各ノードはその前後のノードにリンクされます。get(i)バッキング配列（と同じ）がないため、メソッドを持つことは、リスト内のすべての要素を反復処理することと同じLinkedListです。

あまりパフォーマンスが良くないこの能力が必要な場合は、自分でマップを拡張することをお勧めします

于 2011-04-14T17:06:00.550 に答える
1

ランダムアクセスが必要な場合は、次のことができます

Map<K,V> map = new LinkedHashMap<K,V>();
Map.Entry<K,V>[] entries = (Map.Entry<K,V>[]) map.toArray(new Map.Entry[map.size()]);
Map.Entry<K,V> entry_n = entry[n];

ご覧のとおり、entriesアレイをキャッシュしない限り、パフォーマンスは非常に低くなる可能性があります。

しかし、その必要性には疑問があります。

于 2011-04-14T17:22:04.527 に答える
0

インデックスによるアクセス効率が log(N) の Map を作成しても問題はありません。赤黒ツリーを使用し、各ノードにそのノードから始まるツリー内の要素数を格納すると、log(N) である get(int index) メソッドを記述できます。

于 2015-12-18T13:30:10.767 に答える