Java hashmap vs hashset 性能

Question

我有一个包含 7.6M 行的文件。每行的格式为:A、B、C、D，其中 B、C、D 是用于计算 A 重要性级别的值，A 是每行唯一的字符串标识符。我的做法:

private void read(String filename) throws Throwable {
        BufferedReader br  = new BufferedReader(new FileReader(filename));

        Map<String, Double> mmap = new HashMap<>(10000000,0.8f);
        String line;
        long t0 = System.currentTimeMillis();
        while ((line = br.readLine()) != null) {
            split(line);
            mmap.put(splitted[0], 0.0);
        }
        long t1 = System.currentTimeMillis();
        br.close();
        System.out.println("Completed in " + (t1 - t0)/1000.0 + " seconds");
}

private void split(String line) {
    int idxComma, idxToken = 0, fromIndex = 0;
    while ((idxComma = line.indexOf(delimiter, fromIndex)) != -1) {
        splitted[idxToken++] = line.substring(fromIndex, idxComma);
        fromIndex = idxComma + 1;
    }
    splitted[idxToken] = line.substring(fromIndex);
}

为了“分析”目的而插入虚拟值 0.0 并拆分的是为该类定义的简单字符串数组。我最初使用 String 的 split() 方法，但发现上面的方法更快。

当我运行上面的代码时，解析文件需要 12 秒，这比我想象的要多。例如，如果我用字符串 Vector 替换 HashMap 并只从每一行中取出第一个条目(即我没有在其中放置关联值，因为这应该是摊销常量)，整个文件可以在不到3 秒。

这向我表明 (i) HashMap 中有很多冲突(我试图通过预分配大小并相应地设置加载因子来最小化调整大小的次数)或 (ii) hashCode() 函数不知何故很慢。我怀疑它 (ii)，因为如果我使用 HashSet，文件可以在 4 秒内读取。

我的问题是:HashMap 执行如此缓慢的原因可能是什么？对于这种大小的 map ，hashCode() 是否不够用，还是我忽略了一些根本性的东西？

Answer 1

HashMap 与 Vector:在 HashMap 中插入比在 Vector 中插入成本更高。虽然两者都是摊销常数时间操作，但 HashMap 在内部执行许多其他操作(如生成 hashCode、检查冲突、解决冲突等)，而 Vector 只是在末尾插入元素(增加结构的大小，如果需要的话)。

HashMap 与 HashSet:HashSet 在内部使用 HashMap。因此，如果您将它们用于相同目的，则应该不会有任何性能差异。理想情况下，这两者都有不同的目的，因此讨论哪个更好是没有用的。

既然您需要 B、C、D 作为值，而 A 作为键，您绝对应该坚持使用 HashMap。如果您真的只想比较性能，请将“null”而不是 0.0 作为所有键的值(因为这是 HashSet 在将键放入其支持的 HashMap 时使用的值)。

更新:HashSet 使用虚拟常量值(静态最终值)插入到 HashMap 中，而不是 null。对于那个很抱歉。你可以用任何常量替换你的 0.0，性能应该类似于 HashSet。