Javaの

Question

でのHashMapの衝突で、有線のもの

私はleft_tableとright_tableの間で共通鍵を取得するためにHashMapを使用する場合（また、私はHashMapと比較するBloom Filterアルゴリズムをテストしていますので、私は注意を引くためのタグBloom Filterを追加し、HashMapこの問題があるかもしれません）、私はhm2（値のデフォルトは1）にright_tableのキーを置くと、常にキーが衝突します。HashMap hm1 and hm2を2つ宣言しました。私はキーのハッシュ値が同じであるかもしれないが、なぜ同じ場所にいつも存在するのかを理解しました。 hm1とhm2の宣言を並べ替えると、衝突は依然として残ります！

私は、hm1.sizeが常にnと同じであり、2000000 uuids以上を格納できるというテストをしています。 JavaのHashMapツールは信頼できますか？

import java.util.ArrayList; 
    import java.util.HashMap; 
    import java.util.List; 
    import java.util.Random; 
    import java.util.UUID; 

    public class HashMapBugTest { 
     public static void main(String[] argv) { 
      int n = 100; 
      int real = 10; 
      List<String> Uuids_in_left_table = new ArrayList<String>(); 

      // init left table 
      Long startInsertTime1 = System.currentTimeMillis(); 
     for (int i = 0; i < n; i++) { 
      String Uuid = UUID.randomUUID().toString(); 
      Uuids_in_left_table.add(Uuid); 
     } 
     Long endInsertTime1 = System.currentTimeMillis(); 
     System.out.println("The length of Uuids_in_left_table is:" + Uuids_in_left_table.size()); 
     System.out.println("The time use for insert the uuid into the left table used " + (endInsertTime1 - startInsertTime1) + "ms."); 

     // init right table 
     List<String> Uuids_in_right_table = new ArrayList<String>(); 
     Random r = new Random(n); 
     Long startInsertTime2 = System.currentTimeMillis(); 
     for (int i = 0; i < n - real; i++) { 
      String Uuid = UUID.randomUUID().toString(); 
      Uuids_in_right_table.add(Uuid); 
     } 
     for (int i = 0; i < real; i++) { 
      String Uuid = Uuids_in_left_table.get(r.nextInt(n)); 
      Uuids_in_right_table.add(Uuid); 
     } 
     Long endInsertTime2 = System.currentTimeMillis(); 
     System.out.println("The length of Uuids_in_left_table is: " + Uuids_in_left_table.size()); 
     System.out.println("The time use for insert the uuid into the right table used " + (endInsertTime2 - startInsertTime2) + "ms."); 

     // build hashmap 
     HashMap<String, Object> hm2 = new HashMap<String, Object>(); 
     HashMap<String, Object> hm1 = new HashMap<String, Object>(); 
     for (int i = 0; i < n; i++) { 
      int ind = hm2.size(); 
      if (ind == 97) 
       System.out.println(hm2.containsKey(Uuids_in_right_table.get(ind))); 
      hm2.put(Uuids_in_right_table.get(i), 1); 
      if (ind == hm2.size()) 
       System.out.println("a"+i+"---"+Uuids_in_right_table.get(i)); 
     } 
     for (int i = 0; i < n; i++) { 
      hm1.put(Uuids_in_left_table.get(i), 1); 
     } 

     int cnt = 0; 
     System.out.println("length of hm1 is:" + hm1.size()); 
     System.out.println("length of hm2 is:" + hm2.size()); 
     Long startHashMapTime = System.currentTimeMillis(); 
     for (String str:hm1.keySet()) { 
      if (hm2.containsKey(str)) 
       cnt += 1; 
     } 
     Long endHashMapTime = System.currentTimeMillis(); 
     System.out.println("The time used for check the uuid common in the left table and right table used " + (endHashMapTime - startHashMapTime) + "ms."); 
     System.out.println("The number of common uuid is:" + cnt); 
    } 
} 

前のコードの出力は次のようになります。

Random r = new Random(n); 

それはあなたがそれを考えて何をしません：あなたの問題はとても再現性のある

The length of Uuids_in_left_table is:100 
The time use for insert the uuid into the left table used 20ms. 
The length of Uuids_in_left_table is: 100 
The time use for insert the uuid into the right table used 3ms. 
true 
a97---c3b4f281-d82e-42c5-9a6d-b4de19032689 
true 
length of hm1 is:100 
length of hm2 is:99 
The time used for check the uuid common in the left table and right table used 0ms. 
The number of common uuid is:9 

Answer 1

理由は、このラインでありますそうです。

それは何か：初期種子がnのランダムジェネレータを作成します。 そしてnはあなたのプログラムでは常に10であるため、常に同じ乱数列が得られます。

常に左リストから選択した10個のuuidsを右リストに導き、インデックス88を2回使用します。

修正：あなたは10個の数字あなたが実行するたびに別のリストを取得することは非常に可能性が高いですので

Random r = new Random(); 

これは、ミリ秒単位の現在時刻に基づいて初期シードと乱数発生器を作成します。プログラム。

お客様のコードでは、HashMapの問題は強調表示されません。同じキー（左のリストのインデックス88からのuuid）をhm2に2回挿入すると、2回目の挿入時に最初に挿入するときに上書きされます。期待した100要素ではなく、99要素しか含まれていません。