測試Java HashMap實現失敗：僅適用於大約99％的值

我爲Java中的簡單整數字符串鍵值編寫了一個HashMap實現。在試圖測試它時，我寫了一些測試代碼，並且每次看到0-4的值（超出5000的樣本），測試失敗。於是我將HashMap切換到Java默認實現，並注意到我的測試失敗了明顯正確的實現。所以，在過去的幾個小時裏，我一直在試圖弄清爲什麼我的測試失敗。有什麼我失蹤？（嗯，很明顯有......）測試Java HashMap實現失敗：僅適用於大約99％的值

這裏是我的代碼：

package HashMapOther; 

import java.math.BigInteger; 
import java.security.SecureRandom; 
import java.util.HashMap; 

public class StudentStore { 
    private static SecureRandom random = new SecureRandom(); 
    static HashMap<Integer, String> map; 
    static String[] studentNames; 
    static int[] keys; 
    static int magicNumber =5000; //still fails no matter size 

    public static void main(String[] args){ 
     long startTime = System.currentTimeMillis(); 
     start(); 
     test(); 
     long endTime = System.currentTimeMillis(); 
     System.out.println("TIME: " + (endTime - startTime) + " ms"); 
    } 

    public static void start(){ 
     studentNames = getStudents(); //random strings 
     keys = getKeys(); //random integers 
     map = new HashMap<Integer, String>(magicNumber, (float) 0.7); 
     for(int i=0; i< magicNumber; i++){ 
      map.put(keys[i],studentNames[i]); 
     } 
    } 

    public static int[] getKeys(){ //random integers 
     int[] a = new int[magicNumber]; 
     for(int k=0; k< magicNumber; k++){ 
      a[k] = (int) (Math.random()*10000000+1); 
     } 
     return a; 
    } 

    public static String[] getStudents(){ //random strings 
     String[] temp = new String[magicNumber]; 
     for(int i=0; i<magicNumber; i++){ 
      temp[i] = randomString(); 
     } 
     return temp; 
    } 

    public static String randomString(){ //random string 
     return new BigInteger(130, random).toString(32); 
    } 

    public static void test(){ //test code 
     boolean passed = true; 
     for(int i=0; i<magicNumber; i++){ 
      if(!studentNames[i].equals(map.get(keys[i]))){ 
       System.out.println("FAILURE: "+studentNames[i] + " " + map.get(keys[i])); 
       passed = false; 
      } 
     } 
     System.out.println("RESULT: " + passed); 
    } 
}

這裏是輸出示例：

FAILURE: vq0cpihdsr4vfru6126suufvp4 3dq4shra6dps49psehqjuof4ib 
FAILURE: lo2t73n1upqk6cmirdpui29ndt r6accv6ja5pkv723c5g0fe0d1q 
RESULT: false 
TIME: 94 ms

，或者在另一個運行：

RESULT: true 
TIME: 104 ms

和另一個：

FAILURE: c7848b9rejbtguj2d70llotvpu od7r0fjdphvdli6mgonbictg4d 
FAILURE: 4ouk2cj9ipoo4hjrco8vd6p7e kt0u925jdn102cjul96thsfhcm 
FAILURE: 2spd0u9lp7531hm09rqu8oncvm scrui9hl7tr0aq85at13oekgf7 
RESULT: false 
TIME: 99 ms

來源

2017-03-14 David

我注意到如果我改變getKeys（）函數來設置鍵值等於唯一的k值而不是隨機數，它就解決了這個問題。由於HashMaps必須具有唯一的密鑰，因此隨機數與前一個數相等的可能性足以使測試完全失敗。我想我會離開這個帖子，如果任何人在未來需要它。 – David

正如你所看到的，重複鍵的機會遠非輕微，儘管它看起來可能違反直覺。這被稱爲[生日問題]（https://en.wikipedia.org/wiki/Birthday_problem）。 – shmosel

您的密鑰包含重複（有時）。您可以通過評估map.put(...)的返回值來檢查。如果密鑰不在地圖中，則返回null。如果地圖上已經有指定鍵的條目，它將返回所述條目的值。

public static void start(){ 
    studentNames = getStudents(); //random strings 
    keys = getKeys(); //random integers 
    map = new HashMap<Integer, String>(magicNumber, (float) 0.7); 
    for(int i=0; i< magicNumber; i++){ 
     String previousValue = map.put(keys[i],studentNames[i]); 
     if (previousValue != null) { 
      System.out.println(keys[i] + " is a duplicate key"); 
     } 
    } 
}

來源

2017-03-14 08:12:54 Manu

測試Java HashMap實現失敗：僅適用於大約99％的值

回答

相關問題