java - 为什么 map.values().stream() 比 Array.stream(array) 慢得多

Question

为大学第二学期计算机科学创建两个结构来计算文本中的单词数。一种实现使用带有 Word-Objects 的数组，它将单词保存为字符串，并将其频率保存为 int。另一个使用作为 HashMap，以 Word 作为键，频率作为值。现在他们是一个函数“totalWords”，它应该返回所有频率的总和。

在 HashMap 变体中:

return _map.values().stream().reduce(0, (a, b) -> a + b);

在数组变体中:

return Arrays.stream(_words)
            .map((word) -> word != null ? word.count() : 0)
            .reduce(0, (a, b) -> a + b);

我的问题是:在测试文本非常短的 JUnit 测试中，Array 变体确实需要大约 0.001s，而 map 变体需要 0.040s，我不明白为什么 map 确实需要这么多时间。有人有解释和更好的解决方案吗？

Answer 1

其中一个原因是 HashMap 的迭代可能比 Array 慢得多，原因是 locality。现代处理器的计算瓶颈主要是内存访问，这就是使用 cache 的原因。 Array 将数据存储在连续的内存块中，这意味着当您将该内存块交换到缓存中时，您更有可能使用缓存中的所有内容，或者您​​获得 缓存命中，所以缓存喜欢数据的连续内存。另一方面，HashMap 的每个元素都存储在内存中的不同位置，因此当您遍历 HashMap 时，您会得到很多缓存未命中，你最终会一直在缓存中交换数据，这会大大降低你的编程速度。

虽然HashMap的实际实现是以优化的方式将内存中的数据聚集在一起，但即使在这种情况下，(@Radiodef)因为HashMap 使用某种链表，HashMap 的每个元素都包含额外的指针，因此 HashMap 比 Array< 消耗更多的内存，更多内存意味着更多缓存未命中和更多页面错误，因此HashMap通常比Array慢>.