为什么最多 4 个元素的集合是有序的，而较大的则不是? [英] Why are Sets of up to 4 elements ordered but larger ones are not?

问题描述

给定

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)

为什么前者没有排序，而后者似乎有排序?

Why are former not ordered whilst latter seem to be ordered?

推荐答案

行为差异是由于 优化 最多 4 个元素

不可变集合的默认实现使用表示适应集合中元素的数量.空集是仅由单例对象表示.最多四个的集合是由将所有元素存储为字段的单个对象表示.超出这个大小，不可变集实现为 压缩哈希数组映射前缀树.

The default implementation of an immutable set uses a representation that adapts to the number of elements of the set. An empty set is represented by just a singleton object. Sets of sizes up to four are represented by a single object that stores all elements as fields. Beyond that size, immutable sets are implemented as Compressed Hash-Array Mapped Prefix-tree.

由 Ben James 类似地解释:

Set 也是一个带有 apply** 方法的伴生对象*.你打电话的时候Set(...)，你正在调用这个工厂方法并得到一个回报值是某种集合.它可能是一个 HashSet，但也可能是其他一些实现.根据2，默认实现对于不可变集具有空集和集的特殊表示size 最大为 4. 大小为 5 及以上的不可变集和可变集都使用哈希集.

Set is also a companion object* with an apply** method. When you call Set(...), you're calling this factory method and getting a return value which is some kind of Set. It might be a HashSet, but could be some other implementation. According to 2, the default implementation for an immutable set has special representation for empty set and sets size up to 4. Immutable sets size 5 and above and mutable sets all use hashSet.

既然Set(3, 2, 1, 4, 5, 6, 7)的size大于4，那么它的具体实现就是HashSet

Since size of Set(3, 2, 1, 4, 5, 6, 7) is greater than 4, then its concrete implementation is HashSet

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

不保证广告订单.另一方面，Set(1, 2, 3) 的具体实现是专用的类 Set3

which does not guarantee insertion order. On the other hand, concrete implementation of Set(1, 2, 3) is dedicated class Set3

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

将三个元素存储在对应的三个字段

which stores the three elements in corresponding three fields

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

这篇关于为什么最多 4 个元素的集合是有序的，而较大的则不是?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！