Java hashmap vs hashset 性能

Question

我有一个包含 760 万行的文件。每行的格式为：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);
}

其中为 "profiling" 目的插入虚拟值 0.0 并拆分为为 class 定义的简单字符串数组。我最初使用 String 的 split() 方法，但发现上面的方法更快。

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

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

我的问题是：HashMap 执行如此缓慢的原因可能是什么？对于这种大小的地图，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.

Answer 2

是的，用 0.0 作为虚拟值 VS 静态最终常量作为虚拟值 VS HashSet 检查了你的例子。这是粗略的比较，为了获得更高的精度，我建议使用 JHM 工具，但我的 HashSet 性能与静态常量作为虚拟性能几乎相同。

所以，最有可能的是，这种低性能是由于为每一行包装了你的 0.0 虚拟值（它在编译期间被 Double.valueOf() 取代，这明确地创建了一个新的 Double每次都反对）。

这可以解释低性能，因为 HashSet 预定义了静态最终虚拟对象（不是 null，顺便说一句）。

Answer 3

您可以使用内存效率更高的集合库。

我建议使用 Eclipse Collections ( https://www.eclipse.org/collections/ ), that has a ObjectDoubleMap ( https://www.eclipse.org/collections/javadoc/8.0.0/org/eclipse/collections/api/map/primitive/ObjectDoubleMap.html )，它是一个对象映射（在你的例子中是字符串），它有一个双精度（是的，原始双精度）作为关联值。它在处理内存和性能方面要好得多。

您可以通过以下操作获得一个空实例：

ObjectDoubleMaps.mutable.empty();

Java hashmap vs hashset 性能

Java hashmap vs hashset performance

java

performance

hashmap

hashcode