即使使用 TLongObjectHashMap 也非常慢

Question

我需要将大约 2000 万个条目放入一个 HashMap 中。我根据 :Why is Java HashMap slowing down?

选择了 TLongObjectHashMap

代码如下：

StringBuilder sb = new StringBuilder("");
StringBuilder value = new StringBuilder("");
TLongObjectHashMap<String> map = new TLongObjectHashMap<String>();

in = new FileInputStream(new File(inputFile));
br = new BufferedReader(new InputStreamReader(in), 102400);
for (String inLine; (inLine = br.readLine()) != null;) {
    sb.setLength(0);
    for (i = 0; i < 2; i++) {
                for (j = 1; j < 12; j++) {
                    sb.append(record.charAt(j));
                }
            }

            for (k = 2; k < 4; k++) {
                value.append(record.charAt(k));
            }
            for (k = 7; k < 11; k++) {
                value.append(record.charAt(k));
            }
    map.put(Long.parseLong(sb.toString()), value.toString());
    value.delete(0, value.length());
}

我用的是 GNU Trove。仍然，变得非常缓慢，几乎停在大约 1500 万个条目。目前还没有 OutOfMemoryError。有什么问题？

我没有为此使用数据库的选项。

注意：1、12、2、4等值是在这个循环之前计算出来的，存储在一个变量中，这里又会用到。我现在只是用一些值替换了它们

Answer 1

我不相信JDK内置的HashMap不能处理这个。我发现有 2 个问题

随着地图的增长不断重新散列地图
非必要的字符串生成器对象

当底层存储阵列负载系数达到 75% 时，将进行重新哈希处理

DEFAULT_INITIAL_CAPACITY = 16;  
DEFAULT_LOAD_FACTOR = 0.75;  
THRESHOLD = DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR;

我假设下面的工作量呈指数级减少并且做同样的事情

double expected_maximal_number_of_data = 30000000d;
int capacity = (int) ((expected_maximal_number_of_data)/0.75+1);
HashMap<Long, String> map = new HashMap<Long, String>(capacity);
for (String inLine; (inLine = br.readLine()) != null;) {
    Long key = Long.parseLong(record.substring(1, 12));
    String value = record.substring(2, 4) + record.substring(7, 11);
    map.put(key, value);
}

如果您的计算机有 2gb 内存，则应该没有问题，预计完成时间为 <16 秒。

Answer 2

I used the GNU Trove. Still, becomes extremely slow and almost stops at about 15 million entries. There is no OutOfMemoryError yet. What is the problem?

问题是你在做假设而不是验证它们。

并且您没有分析您的代码。您的真实代码，而不是您在此处发布的半编辑内容（提示：当变量名称不匹配时，很明显它不是真实代码）。

是的，您正在编写低效的代码。那些用于复制字符的循环，例如，duplicate String.substring()。你已经被告知了。但它被埋没在大量评论中，你可能错过了它。另一个好的评论是使用这些子字符串的简单连接，而不是乱用 StringBuilder.

但真正的问题是假设您的地图效率低下，基于您在 Internet 上阅读的内容，并且没有采取任何措施来挑战该假设。我可以保证从磁盘读取记录所花费的时间远远大于为每条记录在映射中插入一个值所花费的时间。

你需要做的就是向自己证明这一点。分析您的代码是执行此操作的最佳方法，但您也可以分离出程序的各个部分。使用如下所示的简单循环来了解地图的实际速度（我使用 HashMap 因为我没有安装 Trove 库；用 100,000,000 个条目填充地图大约需要 2 分钟） .我将留给您编写一个类似的测试来从您的文件中读取数据。

private static Map<Long,String> fillMap(int items)
{
    Map<Long,String> map = new HashMap<Long,String>(items);
    Random rnd = new Random();

    long start = System.currentTimeMillis();

    for (int ii = 0 ; ii < items ; ii++)
    {
        map.put(new Long(rnd.nextLong()), new String("123456789012345678901234567890"));
    }

    long finish = System.currentTimeMillis();
    double elapsed = ((finish - start) / 1000.0);
    System.out.format("time to produce %d items: %8.3f seconds (map size = %d)\n", items, elapsed, map.size());
    return map;
}

即使使用 TLongObjectHashMap 也非常慢

Extremely slow even with TLongObjectHashMap

java

dictionary