scala - 为什么最多 4 个元素的集合是有序的，而更大的则不是？

Question

给定

val xs1 = Set(3, 2, 1, 4, 5, 6, 7)
val ys1 = Set(7, 2, 1, 4, 5, 6, 3)

xs1并且ys1都导致scala.collection.immutable.Set[Int] = Set(5, 1, 6, 2, 7, 3, 4)

但下面有更小的套装

val xt1 = Set(1, 2, 3)
val yt1 = Set(3, 2, 1)

生产

xt1: scala.collection.immutable.Set[Int] = Set(1, 2, 3)
yt1: scala.collection.immutable.Set[Int] = Set(3, 2, 1)

为什么前者没有被订购，而后者似乎被订购？

标签： scalaset

Answer 1

行为差异是由于对最多 4 个元素的集合进行了优化

不可变集合的默认实现使用适应集合元素数量的表示。一个空集仅由一个单例对象表示。最多四个大小的集合由一个对象表示，该对象将所有元素存储为字段。超出该大小，不可变集合被实现为Compressed Hash-Array Mapped Prefix-tree。

Ben James类似地解释道：

Set 也是一个带有 apply** 方法的伴生对象*。当你调用 Set(...) 时，你正在调用这个工厂方法并获得一个返回值，它是某种 Set。它可能是一个 HashSet，但也可能是其他一些实现。根据 2，不可变集的默认实现对空集具有特殊表示，并将大小设置为 4。不可变集大小为 5 及以上，可变集都使用 hashSet。

由于 size ofSet(3, 2, 1, 4, 5, 6, 7)大于 4，那么其具体实现为HashSet

Set(3, 2, 1, 4, 5, 6, 7).getClass
class scala.collection.immutable.HashSet

这不能保证插入顺序。另一方面，具体实现Set(1, 2, 3)是专用类Set3

Set(1,2,3).getClass
class scala.collection.immutable.Set$Set3

它将三个元素存储在相应的三个字段中

final class Set3[A] private[collection] (elem1: A, elem2: A, elem3: A) extends AbstractSet[A] ...