java - ConcurrentHashMap 实现和限制

Question

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

我有一个大数据集，我正在尝试构建一个社交图谱。数据包含超过 950 万个坐标到 Short 值的映射。对于 ConcurrentHashMap 中的键值，我使用的是字符串，它是在中间用“,”连接的坐标。

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

在处理了大约 8000 个组后，访问出现问题。一次似乎只有一个线程处于 Activity 状态，我不确定这是因为它太大还是其他因素。这是一个问题，因为我总共有 300,000 个组需要处理(并且需要及时处理)。

关于我如何实现它，是否有任何建议，以及我可以使用的任何快捷方式？我认为读取和写入同样重要，因为如果值存在(如果不创建)我必须读取坐标，然后将值加一并写回。

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

谢谢你的时间， -mojavestorm

进一步说明:

两种实现及其限制:

1) 我有一个 HashMap(Integer, Vector(Integer)) preMap，它包含一个 GroupID 作为键和一个 userID vector 。线程在彼此之间拆分 GroupID 并使用返回的每个 Vector(Integer)，每个线程根据坐标将短值存储到 TLongShortHashMap threadMap 中(表示 UserID x 和 UserID y 属于(短)n 组)，并且每个线程都拥有自己的 threadMap。坐标映射到长值。每个线程完成后，将每个threadMap中对应key的值加到一个combinedMap中的同一个key上，即表示UserID x和UserID y在整个系统中一共属于多少组。

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

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

问题是时间。现在该计划正在以惊人的速度运行 1400 年才能完成。使用的内存在 4GB 到 15GB 之间波动，但似乎保持“低”。不完全确定它会保持在限制范围内，但是，我想它会。对我来说没有明显的改进。

希望这些描述清楚，有助于深入了解我的问题。谢谢。

Answer 1

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

如果您使用的是短裤，我会在像 TObjectIntHashMap 这样的系列中使用这对于处理原语更有效。

---

在简单的情况下，您有短坐标 public static void main(String... args) 抛出 IOException { 整数长度 = 10 * 1000 * 1000； int[] x = new int[长度]; int[] y = new int[长度];

  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>

---

如果您有双坐标，则需要使用双层 map 。

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>