我應該使用HashMap，List還是其他？

Question

我寫一個程序，

1. 保存鍵 - 值對（場景，listOfResults）
2. 隨機模擬新方案的名單，發現結果
3. 檢查，看是否該方案是在鍵值對
4. 如果是這樣的名單，更新鍵值對，以使新的結果添加到列表中
5. 否則，增加了情景結果對到鍵值對的列表
6. 重複步驟＃2-5

目前我使用的是一個HashMap，因爲它的鍵值系統是有意義的。然而，這些計算似乎需要很長時間，我正在考慮一種不同的數據結構是否更合適。

模擬100個場景花費了8.623秒，並且使用4,600個鍵值對留下了HashMap。

模擬200個場景需要42.690秒，並且使用9,431個鍵值對留下了HashMap。

似乎鍵值對的數量呈線性增加，而時間呈指數增長，並且很快就會失去控制。我可能能夠進一步優化程序，但我是否完全使用了錯誤的數據結構？

更新：我懷疑問題是我的hashcode（）方法。在這裏它是：

@Override 
public int hashCode() { 
    int result = 31 + legalBoard; 
    result = result*31 + playerToMove; 
    result = result*31 + Arrays.hashCode(getSmallestFieldConfiguration()); 
    //System.out.println("Hashcode: " + result + " ---------- " + Arrays.toString(field)); 
    return result; 
} 

legalBoard是-1和8之間的int playerToMove要麼-1或1 field是int [81]與值-1,0和1。getSmallestConfiguration()方法找到最小的陣列從陣列的每個可能的反射/旋轉，如下所示：

public int[] getSmallestFieldConfiguration(){  
    int[] smallestConfig = field; 
    for(int[] config : getAllOtherFieldConfigurations()){ 
     if(isGreater(smallestConfig, config)){ 
      smallestConfig = config; 
     } 
    } 
    return smallestConfig; 
} 

public int[][] getAllOtherFieldConfigurations(){ 
    int[][] configs = new int[7][]; 
    int[][] twoDimensionalField = new int[][]{ 
     {field[0],field[1],field[2],field[3],field[4],field[5],field[6],field[7],field[8]}, 
     {field[9],field[10],field[11],field[12],field[13],field[14],field[15],field[16],field[17]}, 
     {field[18],field[19],field[20],field[21],field[22],field[23],field[24],field[25],field[26]}, 
     {field[27],field[28],field[29],field[30],field[31],field[32],field[33],field[34],field[35]}, 
     {field[36],field[37],field[38],field[39],field[40],field[41],field[42],field[43],field[44]}, 
     {field[45],field[46],field[47],field[48],field[49],field[50],field[51],field[52],field[53]}, 
     {field[54],field[55],field[56],field[57],field[58],field[59],field[60],field[61],field[62]}, 
     {field[63],field[64],field[65],field[66],field[67],field[68],field[69],field[70],field[71]}, 
     {field[72],field[73],field[74],field[75],field[76],field[77],field[78],field[79],field[80]}, 
    }; 
    /*for(int i=0; i<81; i++){ 
     twoDimensionalField[i%9][i/9] = field[i]; 
    }*/ 

    //Reflections 
    configs[0] = getFieldFromMatrix(MatrixTransformations.reflectVertical(twoDimensionalField)); 
    configs[1] = getFieldFromMatrix(MatrixTransformations.reflectHorizontal(twoDimensionalField)); 
    //Rotations 
    int[][] singleRotation = MatrixTransformations.rotate(twoDimensionalField); 
    configs[2] = getFieldFromMatrix(singleRotation); 
    int[][] doubleRotation = MatrixTransformations.rotate(twoDimensionalField); 
    configs[3] = getFieldFromMatrix(doubleRotation); 
    configs[4] = getFieldFromMatrix(MatrixTransformations.rotate(doubleRotation)); 
    //Transpositions 
    configs[5] = getFieldFromMatrix(MatrixTransformations.transpose(twoDimensionalField)); 
    configs[6] = getFieldFromMatrix(MatrixTransformations.transpose(doubleRotation)); 

    return configs; 
} 

MatrixTransformations的方法是這樣的：

公共類MatrixTransformations { 公共MatrixTransformations（）{}

public static int[][] reflectVertical(int[][] arr){ 
    for(int j=0; j<9; j++){ 
     for(int k=0; k<4; k++){ 
      int temp = arr[j][k]; 
      arr[j][k] = arr[j][3-k]; 
      arr[j][8-k] = temp; 
     } 
    } 
    return arr; 
} 
public static int[][] reflectHorizontal(int[][] arr){ 
    for(int j=0; j<4; j++){ 
     for(int k=0; k<9; k++){ 
      int temp = arr[j][k]; 
      arr[j][k] = arr[8-j][k]; 
      arr[8-j][k] = temp; 
     } 
    } 
    return arr; 
} 
public static int[][] transpose (int[][] array) { 
     if (array == null || array.length == 0)//empty or unset array, nothing do to here 
     return array; 

     int width = array.length; 
     int height = array[0].length; 

     int[][] array_new = new int[height][width]; 

     for (int x = 0; x < width; x++) { 
     for (int y = 0; y < height; y++) { 
      array_new[y][x] = array[x][y]; 
     } 
     } 
     return array_new; 
    } 

public static int[][] rotate(int[][] arr){ 
    int[][] newArr = new int[9][9]; 
    for (int i = 0; i < 9; ++i) { 
     for (int j = 0; j < 9; ++j) { 
      newArr[i][j] = arr[8 - j][i]; 
     } 
    } 
    return newArr; 
} 
} 

Answer 1

也許你應該堅持使用地圖。除非你的密鑰是連續的1,2,3使用9K的隨機數可能會導致你沒有足夠的內存問題。