1

簡単なケースを想像してください:

class B{
    public final String text;
    public B(String text){
        this.text = text;
    }
}

class A {
    private List<B> bs = new ArrayList<B>;

    public B getB(String text){
        for(B b :bs){
           if(b.text.equals(text)){
               return b;
           }
        }
        return null;
    }

    [getter/setter]
}

A の各インスタンスについて、List<B>が大きく、getB(String) 頻繁に を呼び出す必要があると想像してください。ただし、リストが変更される可能性もあると仮定します (要素の追加/削除、または再割り当ても)。

この段階で、getB(String) の平均的な複雑さは O(n) です。これを改善するために、巧妙なキャッシングを使用できないかと考えていました。

キーがList<B>である場所に をキャッシュすると想像してください。これによりパフォーマンスが向上しますが、リストが変更された場合 (新しい要素または削除された要素) または再割り当てされた場合 (新しい参照を指す) は機能しません。Map<String, B>B.textA.bs

それを回避するために、 とともにMap<String, B>、 list のハッシュを格納できると考えましたbs。メソッドを呼び出すgetB(String)と、 list のハッシュが計算されますbs。ハッシュが変更されていない場合はマップから結果を取得し、変更されている場合はマップをリロードします。

問題は、 a のハッシュをjava.util.List計算すると、リストのすべての要素を調べて、少なくとも O(n) であるハッシュを計算することです。

質問

私が知りたいのは、JVM が List のハッシュを計算する際に、getB(String)メソッドでループを実行するよりも高速になるかどうかです。のハッシュの実装に依存する可能性がありますB。もしそうなら、どのようなことがうまくいくでしょうか？一言で言えば、これがばかげているのか、それともパフォーマンスの向上につながるのかを知りたいです。

4

4 に答える 4

5

理由を実際に説明することなく、何らかの理由で、リスト構造も維持することが不可欠であると信じているようです。これの唯一の合理的な理由は、コレクションの順序の一貫性を保つ必要があるということです。「プレーン」マップに切り替えると、値の順序は一定ではなくなります。たとえば、アイテムをマップに追加した順序が維持されます。

順序を維持すること (リストの動作)と、キーを使用して個々のアイテムにアクセスすることの両方が必要な場合は、とLinkedHashMapの動作を本質的に結合するを使用できます。リストではなくコレクションを返す場合でも、リストの動作はコレクション内で保証されます。LinkedListHashMapLinkedHashMap.values()

あなたの質問のもう1つの問題は、リストのハッシュコードを使用して変更を安全に判断できないことです。ハッシュ コードが変更された場合、リストも変更されたことは確かです。2 つのハッシュ コードが同一である場合でも、リストが実際に同一であると確信することはできません。たとえば、ハッシュ コードの実装が文字列に基づいている場合、"1a" と "2B" のハッシュ コードは同一です。

于 2013-04-24T12:34:02.783 に答える
1

IndexedBArrayListを拡張する独自のクラスを実装できますArrayList<B>。

次に、この機能を追加します。

  • あprivate HashMap<String, B> index
  • ArrayList のすべてのミューテーター メソッドは、対応するスーパーメソッドを呼び出すだけでなく、このインデックス ハッシュ マップを最新の状態に保つためにオーバーライドされます。
  • public B getByString(String)ハッシュマップを利用した新方式
于 2013-04-24T12:26:00.983 に答える
1

もしそうなら、どのようなことがうまくいくでしょうか？

簡単に言えば、知らないうちにリストを変更させないでください。現在、次のようなものがあると思います：

public List<String> getAllBs() {
    return bs;
}

...そして同様のセッター。それをやめて、代わりに適切な変更メソッドを用意すれば、コードがリストを変更する唯一のコードであることを確認できます...つまり、マップが「ダーティ」であることを思い出すか、単に変更することができますリストを変更すると同時にマップします。

于 2013-04-24T12:18:17.100 に答える