ハッシュマップの比較実行時間

2つのHashMapsを比較していますが、比較ループの時間の複雑さを把握しようとしています。次のようにコードがある：ループのハッシュマップの比較実行時間

//map1 is a HashMap and contains m elements and keys 
//map2 is a HashMap and contains n elements and keys 
List<myObject> myList = new ArrayList<myObject>() 
for (String key: map1.keySet()){ 
    if(!map2.containsKey(key)){ 
     myList.add(map.get(key)); 
    } 
}

最初O（M）あろう。他のフォーラムでcontainsKey（）がlg（n）の時間がかかることがわかりました。誰かがそれを確認できますか？私はJavaDocsでそれを見つけることができませんでした。
もしそうなら、合計時間複雑度は（mlg {n}）となる。
また、この比較をより良い方法で実行する方法については、参考にしてください。

出典

2011-10-26 rgamber

ここでのHashMapの実装です：http://www.docjar.com/html/apiは/java/util/HashMap.java.html – blackcompe

ハッシュコードのアルゴリズムと衝突によって異なります。

完全なハッシュコードを使用すると、理論的にマップルックアップはO（1）、一定時間です。衝突があれば、O（n）まで可能です。あなたのケースでは、良いハッシュアルゴリズムがあれば、それはO（m）になります。

wikiを見ると、その概念についての理解を深めることができます。マップソースコードを見ることもできます。

出典

2011-10-26 23:36:51 DarthVader

私はデフォルトのJava HashMapを使用しています。どこにでも私はこれらのデフォルトを見つけることができましたか？ – rgamber

javaのデフォルトのインプリメンテーションが文字列に対してはOKであると仮定すると、平均ケースの一定時間でなければなりません。 – Kevin

彼はデフォルトのハッシュコードimplを意味します。あなたが1つを提供しない場合。 – DarthVader

Java HashMapの実装では、内部データ構造のサイズをマップ内の要素の数よりも一定量大きくする必要があります。ハッシュアルゴリズムは良いので、衝突は最小限で済むと思われます。 O（n）よりもO（1）に近い。

どのHashMapを使用していますか？ Javaに付属しているのは？あなた自身の？

出典

2011-10-26 23:42:09 dgrant

私はJavaに付属しているデフォルトのものを使用しています。 – rgamber

さて、それはかなり良いです。ソースを見てください：http://www.docjar.com/html/api/java/util/HashMap.java.html 特に、resizeメソッド、しきい値メンバー（HashMapはすぐにサイズ変更されます要素の数== capacity * load_factor）になります。デフォルトのload_factorは0.75です。テーブルサイズは毎回2倍になります。デフォルトの初期容量は16です。 – dgrant

これに同意しません。バッキングアレイまたはリンクされたリストのサイズは、ルックアップ時間に影響しません。オブジェクトが同じハッシュコードを返す場合、mapはequalsメソッドを使用し、一致したものを見つけるために衝突したすべてのものを参照します。 – DarthVader

外部ループの時間の複雑さについては、正しくお答えします。O（n）HashMap.containsKey()の漸近的な複雑さは、myObject.hashCode()の実装で何かばかげたことをしない限り、O（1）です。したがって、あなたのメソッドはO（n）時間で実行する必要があります。最適化は、2つのマップのうちの小さい方をループするようにすることです。

TreeMap.containsKey()はO（n個のログ）複雑さ、ないHashMap ...これらのフォーラムを見て停止していることに注意してください:)

出典

2011-10-26 23:53:52 mergeconflict

ありがとうございます。それが私がここに投稿した理由です、私は混乱していました！ – rgamber

ああ、ところで 'map1.keySet（）。retainAll（map2.keySet（））' – mergeconflict

ハッシュマップの比較実行時間

答えて

関連する問題