0

containsLinkedList で頻繁に呼び出しているマイクロ最適化に直面しています。それをLinkedHashMapに変更するのは良い考えでしょうか?

注：リストに特定の値が含まれているかどうかを追加して確認しているだけです。

4

3 に答える 3

6

LinkedList「平均的なケースを含むだけ」よりも少し複雑ですO(1)が、基本的には機能性はイエスです。

は要素を含むことをLinkedHashMap許可O(1)し、要素が挿入された順序で保持します - と同じLinkedListです。あなたも見てみたいかもしれませんLinkedHashSet

ただし、重複したエントリが必要な場合は、問題に直面する可能性があります。LinkedHashMapとはインターフェースではなくインターフェースLinkedHashSetを実装Setしているため、重複は許可されません。MapList

于 2012-08-07T08:06:11.260 に答える
1

はい、LinkedHashMap は O(1) メンバーシップ チェックを提供します

HashMap と同様に、ハッシュ関数がバケット間で要素を適切に分散すると仮定すると、基本操作 (追加、包含、および削除) に対して一定時間のパフォーマンスが提供されます。

また注意してください

リンクされたリストを維持するためのコストが追加されるため、パフォーマンスは HashMap のパフォーマンスをわずかに下回る可能性があります。ただし、1 つの例外があります。 . HashMap の反復は、その容量に比例して時間がかかり、よりコストがかかる可能性があります。

http://docs.oracle.com/javase/6/docs/api/java/util/LinkedHashMap.html

予測可能な順序付けが必要ない場合、HashMap は、順序付けを維持するためにリンクされたリストを維持する必要がないため、挿入/変更時にわずかに高速になります。

于 2012-08-07T08:06:13.083 に答える
0

いいえ; aLinkedListは aListであり、aLinkedHashMapは aMapです。

それとは別に、O(1) が含まれていることを保証するものでLinkedHashMapはありません。実際、LinkedHashMap.containsO(n) です。完全なハッシュまたは (大まかに) バケットへのキーの均一な分散 (つまり、最良のケース) を使用する場合、一定時間containsは可能ですが、衝突のあるシナリオでは、定数係数 0 < k <の平均ケースの線形時間です。 1.

あなたが望んでいるように見えるのは、 に匹敵する平均的なケースのパフォーマンスを備えた挿入Set順序です。HashMap.contains

HashSetこの実装は、すべてのエントリを実行する二重リンク リストを維持するという点でとは異なります。このリンクされたリストは、反復順序を定義します。これは、要素がセットに挿入された順序 ( insert-order ) です。

于 2012-08-07T08:14:08.717 に答える