Java HashMap与HashSet性能比较

Question

我有一个由7.6百万行组成的文件。每一行都是形式为: 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 插入，并为该类定义了一个简单的字符串数组splitted。我最初用的是String类的split()方法，但发现上述方法更快。

当我运行以上代码时，解析文件需要12秒的时间，这比我想象中的要慢得多。例如，如果我用字符串向量替换HashMap，并只取每行的第一个条目（即不为其设置关联值，因为这应该是平摊常数），则整个文件可以在不到3秒的时间内读取。

这表明对于这个 HashMap ，可能有很多冲突（我尽量通过预分配大小并相应地设置负载因子来最小化重调整次数），或者 hashCode() 函数某种程度上很慢。 我怀疑是 (ii) 因为如果我使用一个 HashSet ，那么可以在不到4秒钟的时间内读取文件。

我的问题是：为什么HashMap的性能如此之慢？hashCode() 对于这么大的映射不足够吗，还是我忽略了某些根本性的东西？

- user1938803

---

尝试用一些静态常量替换您的0.0虚拟值。 0.0被Double.valueOf替换，每次都会创建一个新对象。在HashSet中只使用一个预分配的虚拟对象。我不确定这是原因，但可能是这样。 - esin88

splitted[] 的最后一个元素总是包含整个行，这不是你想要的。 - user207421

HashSet 内部由 HashMap 支持，因此唯一的区别是您的虚拟 0.0 的自动装箱。 - bashnesnos

你能把io和tokenizing与map插入分开吗，以确保你没有关注错误的事情吗？[微基准测试] (https://dev59.com/hHRB5IYBdhLWcg3wz6UK) - Laurent G

String.split()较慢，因为它在每次调用时都会分配一个新的正则表达式Pattern。尝试创建一个private static final Pattern SPLITTER = Pattern.compile(",");然后使用SPLITTER.split(line)。 - AngerClown

Answer 1

HashMap vs Vector: 在向HashMap中插入元素时，比向Vector中插入要花费更多的成本。尽管两者都是分摊常数时间操作，但HashMap在内部执行了许多其他操作（如生成hashCode、检查冲突、解决冲突等），而Vector仅在末尾插入元素（如果需要，增加结构的大小）。

HashMap vs HashSet: HashSet在内部使用HashMap。因此，如果您将它们用于相同的目的，理论上不应该有任何性能差异。理想情况下，这两个具有不同的目的，因此关于哪个更好的讨论是无意义的。

由于您需要B、C、D作为A的值，因此您应该继续使用HashMap。如果您真的只想比较性能，请将所有键的值替换为"null"（因为这就是HashSet在将键放入其后端HashMap时使用的值）。

更新：HashSet使用虚拟常量值（static final）来插入HashMap，而不是null。对此感到抱歉。您可以将0.0替换为任何常量，性能应与HashSet类似。

- iavanish

Answer 2

您可以使用更节省内存的集合库。

我建议使用Eclipse Collections（https://www.eclipse.org/collections/），它有一个ObjectDoubleMap（https://www.eclipse.org/collections/javadoc/8.0.0/org/eclipse/collections/api/map/primitive/ObjectDoubleMap.html），它是一个对象（在您的情况下为字符串）的映射，具有关联值为double（是原始double）。它在处理内存和性能方面都要好得多。

您可以通过以下方式获取此类的空实例：

ObjectDoubleMaps.mutable.empty();

- Boschi

Answer 3

是的，我已经用 0.0 作为虚拟值和使用静态常量作为虚拟值，以及使用 HashSet 进行了比较。这只是一个粗略的比较，为了更好的准确度，我建议使用 JHM 工具，但是我的 HashSet 性能基本上与静态常量相同。

最有可能的情况是，每行代码都将你的 0.0 虚拟值包装起来（在编译期间被替换为 Double.valueOf()，这会明确地每次创建一个新的 Double 对象）。

这就解释了低性能的原因，因为 HashSet 有预定义的静态常量虚拟对象（它不是 null，顺便说一下）。

- esin88