使用 org.javatuples.Pair 和 HashMap 创建密集矩阵太慢

Question

我有一个大小约为 30000 X 30000 的密集对称矩阵，其中包含字符串之间的距离。由于距离是对称的，矩阵的上三角存储在制表符分隔的 3 列文件中，格式为

stringA<tab>stringB<tab>distance

我正在使用 HashMap 和 org.javatuples.Pair 创建地图以快速查找给定字符串对的距离，如下所示：

import org.javatuples.Pair;

HashMap<Pair<String,String>,Double> pairScores = new HashMap<Pair<String,String>,Double>();

BufferedReader bufferedReader = new BufferedReader(new FileReader("data.txt"));
String line = null;

while((line = bufferedReader.readLine()) != null) {
    String [] parts = line.split("\t");
    String d1 = parts[0];
    String d2 = parts[1];
    Double score = Double.parseDouble(parts[2]);
    Pair<String,String> p12 = new Pair<String,String>(d1,d2);
    Pair<String,String> p21 = new Pair<String,String>(d2,d1);
    pairScores.put(p12, score);
    pairScores.put(p21, score);
}

data.txt 非常大（约 400M 行）并且该过程最终减慢到爬行，大部分时间花在 java.util.HashMap.put.

中

我认为成对不应该有 (m) 任何散列码冲突，但我可能是错的。我如何验证这一点？仅仅看一下 p12.hashCode() 和 p12.hashCode() 有多独特就够了吗？

如果没有碰撞，还有什么可能导致减速？

有没有更好的方法来构造这个矩阵以便快速查找？

Answer 1

我现在正在使用 Guava's Table<Integer, Integer, Double>，因为我也意识到我的字符串足够独特，我可以使用它们的散列而不是字符串本身作为键，以减少内存需求。 table 的创建在合理的时间内运行，但是，序列化和反序列化生成的对象存在问题：我运行进入内存不足错误，即使从 String 移动到 Integer。在我决定不存储 a-b 和 b-a 对之后，它似乎可以正常工作，但我可能正在平衡我的机器可以处理的边缘

使用 org.javatuples.Pair 和 HashMap 创建密集矩阵太慢

Creating dense matrix using org.javatuples.Pair and HashMap is too slow

java

hashmap

matrix

collision