ConcurrentHashMap的实现和限制

Question

我有一个相当大的项目要完成，我遇到了一些死胡同。我想看看这里伟大的社区是否有任何建议。

我有一个大的数据集，我正试图建立一个社会图。该数据包含超过950万个到Short值的坐标映射。对于ConcurrentHashMap中的键值，我使用String，即在坐标之间连接一个'，'。

本质上，我在寻找用户之间共有的组的数量。我有一个很容易构建的初始hashmap，它将GroupID映射到AvatarID的Vector。这部分运行良好。然后，我有12个线程，它们负责自己的一组groupID和处理(每个groupID中的用户之间的计数加上+ 1)，所有访问都来自ConcurrentHashMap。

在处理了大约8000个组之后，出现了访问问题。一次只有一个线程看起来是活动的，我不确定这是因为太大的大小还是其他因素。这是一个问题，因为我总共需要处理30万个组(并且要及时)。

是否有任何建议，我如何实现这一点，我可以使用任何快捷方式?我认为读和写同样重要，因为如果值存在(如果没有创建它)，我必须读取一个坐标，然后在值上加1并回写。

我愿意根据需要提供代码，我只是不知道哪些部分将与讨论相关。

谢谢你的时间，-mojavestorm

进一步解释:

两种实现及其限制:

1)我有一个HashMap(Integer, Vector(Integer)) preMap，它包含一个GroupID作为键和一个userid的Vector。线程将groupid彼此分开并使用返回的每个Vector(Integer)，每个线程根据坐标(表示UserID x和UserID y一起属于(short) n组)将短值存储到TLongShortHashMap threadMap中，并且每个线程拥有自己的threadMap。坐标被映射为长值。在每个线程完成后，每个threadmap中对应键的值被添加到一个combinedMap中的相同键中，这将显示UserID x和UserID y在整个系统中共属于多少组。

这个实现的问题是线程之间有很高的重叠，因此创建了过多的短值。例如:用户1和用户2属于不同的组。线程A和线程B负责它们自己的组范围，包括用户1和用户2所属的组，因此线程A和线程B都在它们的threadMap副本中存储坐标(1,2)的长值和短值。如果出现过多的重叠，那么内存需求可能会很突出。在我的例子中，我分配给Java的所有46GB内存都用完了，而且很快。

2)在这个实现中使用相同的preMap，每个线程被赋予它们负责的用户坐标范围。每个线程运行，获取它拥有的每个坐标并遍历preMap，检查每个groupID并查看UserID x和UserID y是否属于从preMap返回的向量。这个实现消除了threadmap之间的重叠。

问题是时间。现在，这个项目正在以惊人的1400年的速度完成。使用的内存在4GB到15GB之间波动，但似乎一直很低。不能完全确定它会保持在限制之内，但是，我想它会的。在我看来没有明显的改进。

希望这些描述是清楚的，将有助于给我的问题的洞察力。谢谢。

Answer 1

我会让每个线程处理自己的Map。这意味着每个线程可以相互依赖地工作。线程完成后，可以合并所有结果。(或者可能在完成时将结果合并，但这可能会增加复杂性，而没有多少优势)

如果你正在使用一个短的，我会使用在一个集合，如TObjectIntHashMap，这是更有效的处理原语。

---

在简单的情况下，你有short坐标public static void main(字符串)args)抛出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>