ConcurrentHashMap的實現和侷限性

Question

我有一個相當大的項目要完成，我遇到了一些死路。我想看看這裏的偉大社區是否有任何建議。

我有一個大型的數據集，我試圖構建一個社交圖。數據包含超過950萬個座標映射到Short值。對於ConcurrentHashMap中的鍵值，我使用的是一個字符串，即與兩者之間的'，'連接的座標。

基本上，我找到了用戶之間共同的組數。我有一個很容易構建的初始hashmap，它將GroupID映射到AvatarID的Vector。這部分運行良好。然後，我有12個線程負責他們自己的一組GroupID和處理（每個groupID中的用戶之間的計數加1），從ConcurrentHashMap完成所有訪問。

經過大約8000組處理後，發生訪問問題。一次只有一條線程看起來很活躍，而且我不確定這是由於大規模還是其他因素。這是一個問題，因爲我有30萬組需要全部處理（及時處理）。

有沒有關於我如何實現這個的任何建議，以及我可以使用的任何快捷方式？我相信讀寫是同等重要的，因爲如果值存在（如果不創建它），然後再添加一個值並寫回，我必須讀取一個座標。

我願意根據需要提供代碼，我只是不知道哪些部分與討論相關。

感謝您的時間， -mojavestorm

進一步解釋：

兩種實現方式及其限制：

1）我有一個HashMap（整數，向量（整數））preMap包含作爲密鑰的GroupID和用戶ID的矢量。線程將GroupID彼此分開並使用每個Vector（Integer）返回，每個線程根據座標（說UserID x和UserID y屬於（短）n個組）將短值存儲到TLongShortHashMap threadMap中，並且每個線程擁有自己的線程映射。座標映射到長整型值。每個線程完成後，每個threadMaps中相應鍵的值將被添加到combinedMap中的同一個鍵上，這將顯示整個系統中多少個組UserID x和UserID y所屬的組。

這個實現的問題是線程之間有很高的重疊，所以會創建過多的short值。例如用戶1和用戶2一起屬於不同的組。線程A和線程B負責它們自己的組範圍，包括用戶1和用戶2所屬的組，因此線程A和線程B在它們的threadMap的副本中存儲座標（1,2）的長值和一個短暫的價值。如果發生過度重疊，則內存要求可能會非常突出。在我的情況下，我分配給Java的所有46GB RAM都會用完，而且速度也很快。

2）在這個實現中使用相同的preMap，給每個線程一個他們負責的用戶座標範圍。每個線程都運行並獲取每個座標，並通過preMap迭代，檢查每個groupID並查看UserID x和UserID y是否屬於從preMap返回的向量。這個實現消除了threadMaps之間會發生的重疊。

問題在於時間。目前該計劃正在以1400年的驚人速度運行。內存使用4GB至15GB左右的波動，但似乎保持「低」。不完全確定它會保持在極限內，但是，我想它會。沒有任何改善對我來說是顯而易見的。

希望這些描述很明確，並有助於洞察我的問題。謝謝。

Answer 1

我會讓每個線程處理自己的Map。這意味着每個線程可以相互依賴地工作。一旦線程完成，您可以將所有結果合併。 （或可能結合完成後的結果，但這可能會增加複雜性，但沒有多大優勢）

如果您使用的是short，我將使用像TObjectIntHashMap這樣的集合，這對於處理基元更有效。

---

在簡單的情況下，必須short座標 公共靜態無效主要（字符串...參數）拋出IOException異常{ INT長度= 10 * 1000 * 1000; int [] x = new int [length]; int [] y = new int [length];

Random rand = new Random(); 
    for (int i = 0; i < length; i++) { 
    x[i] = rand.nextInt(10000) - rand.nextInt(10000); 
    y[i] = rand.nextInt(10000) - rand.nextInt(10000); 
    } 

    countPointsWithLongIntMap(x, y); 
    countPointsWithMap(x, y); 

} 

private static Map<String, Short> countPointsWithMap(int[] x, int[] y) { 
    long start = System.nanoTime(); 
    Map<String, Short> counts = new LinkedHashMap<String, Short>(); 
    for (int i = 0; i < x.length; i++) { 
    String key = x[i] + "," + y[i]; 
    Short s = counts.get(key); 
    if (s == null) 
     counts.put(key, (short) 1); 
    else 
     counts.put(key, (short) (s + 1)); 
    } 
    long time = System.nanoTime() - start; 
    System.out.printf("Took %.3f seconds to use Map<String, Short>%n", time/1e9); 

    return counts; 
} 

private static TIntIntHashMap countPointsWithLongIntMap(int[] x, int[] y) { 
    long start = System.nanoTime(); 
    TIntIntHashMap counts = new TIntIntHashMap(); 
    for (int i = 0; i < x.length; i++) { 
    int key = (x[i] << 16) | (y[i] & 0xFFFF); 
    counts.adjustOrPutValue(key, 1, 1); 
    } 
    long time = System.nanoTime() - start; 
    System.out.printf("Took %.3f seconds to use TIntIntHashMap%n", time/1e9); 
    return counts; 
} 

打印

Took 1.592 seconds to use TIntIntHashMap 
Took 4.889 seconds to use Map<String, Short> 

---

如果你有雙座標，你需要使用一個兩層的地圖。

public static void main(String... args) throws IOException { 
    int length = 10 * 1000 * 1000; 
    double[] x = new double[length]; 
    double[] y = new double[length]; 

    Random rand = new Random(); 
    for (int i = 0; i < length; i++) { 
    x[i] = (rand.nextInt(10000) - rand.nextInt(10000))/1e4; 
    y[i] = (rand.nextInt(10000) - rand.nextInt(10000))/1e4; 
    } 

    countPointsWithLongIntMap(x, y); 
    countPointsWithMap(x, y); 

} 

private static Map<String, Short> countPointsWithMap(double[] x, double[] y) { 
    long start = System.nanoTime(); 
    Map<String, Short> counts = new LinkedHashMap<String, Short>(); 
    for (int i = 0; i < x.length; i++) { 
    String key = x[i] + "," + y[i]; 
    Short s = counts.get(key); 
    if (s == null) 
     counts.put(key, (short) 1); 
    else 
     counts.put(key, (short) (s + 1)); 
    } 
    long time = System.nanoTime() - start; 
    System.out.printf("Took %.3f seconds to use Map<String, Short>%n", time/1e9); 

    return counts; 
} 

private static TDoubleObjectHashMap<TDoubleIntHashMap> countPointsWithLongIntMap(double[] x, double[] y) { 
    long start = System.nanoTime(); 
    TDoubleObjectHashMap<TDoubleIntHashMap> counts = new TDoubleObjectHashMap<TDoubleIntHashMap>(); 
    for (int i = 0; i < x.length; i++) { 
    TDoubleIntHashMap map = counts.get(x[i]); 
    if (map == null) 
     counts.put(x[i], map = new TDoubleIntHashMap()); 
    map.adjustOrPutValue(y[i], 1, 1); 
    } 
    long time = System.nanoTime() - start; 
    System.out.printf("Took %.3f seconds to use TDoubleObjectHashMap<TDoubleIntHashMap>%n", time/1e9); 
    return counts; 
} 

打印

Took 3.023 seconds to use TDoubleObjectHashMap<TDoubleIntHashMap> 
Took 7.970 seconds to use Map<String, Short>