scala - Scala 如何通过基于大小使用不同的类来实现 Map 和 Set 的性能提升？

Question

我是 Scala 的新手，我刚刚发现 Scala 有 scala.collection.immutable.EmptySet , Set1 , Set2 , Set3 , Set4和 HashSet .与 Map 的情况相同.
提到这有助于提高性能。
它是否通过使用基于索引的小于 5 的元素集合和基于散列的大于 4 的元素集合来提高性能？
如果是这样，是否有任何数学解释说明小于 5 的集合大小对哈希不是很好？

Answer 1

by working with elements collection having a size less than 5 based on Index

不，没有索引。让我们看看 Set最重要的方法:

EmptySet.contains(x) just returns false ，根本没有工作要做。

Set1(elem1).contains(elem) just needs to do a single comparison elem == elem1 ，在比较散列之后，散列集也需要这样做(因为不同值的散列可以相同)。

Set2 , Set3 , 和 Set4也只需要(从 1 到 4)相等比较和 || .

HashSet.contains是 also an one-liner除了所有的工作都是由 get0 完成的和 computeHash , 相当复杂。因此，即使在最好的情况下，它也必须做更多的工作。

除 contains 以外的方法可以类似地专门用于小尺寸。请注意，大小 4 没有什么特别之处，很可能是 Set5 , Set6等也会比 HashSet 快;但最终它们会变得更慢，并且它们的时间点没有固定。此外，添加它们意味着需要加载更多的代码，这使得性能在各处都略有下降。所以它只需要停在某个地方，然后选择了 4。