九、Set

发布于 2023-07-17 23:38:22 字数 9900 浏览 0 评论 0 收藏 0

Set 是没有重复元素的 Iterable 。Scala 提供了scala.collection.immutable.Set 和scala.collection.mutable.Set 这两个trait 来分别表示不可变集和可变集。
这里我们称set 为“集”。
可以对Set 调用+方法来添加元素。
- 对于不可变集，该方法返回一个新的、包含了新元素的集。
- 对于可变集，该方法先将元素添加到集中，然后返回集本身。
Scala collection 类库同时提供了可变和不可变两个版本的 Set 和 Map。当写下 Set 或 Map 时，默认为不可变的版本。 Scala 让我们更容易访问不可变版本，这是为了鼓励大家尽量使用不可变的 Set/Map。
这种访问便利是通过 Predef 对象完成的，这个对象的内容在每个 Scala 源文件都会隐式导入：
```
xxxxxxxxxx
object Predef{
  type Map[A, +B] = collection.immutable.Map[A, B]
  type Set[A] = collection.immutable.Set[A]
  val Map = collection.immutable.Map
  val Set = collection.immutable.Set
  // ...
}
```
Predef 利用 Type 关键字定义了 Set 和 Map 这两个别名，分别对应不可变Set 和不可变 Map 的完整名称。
如果希望使用可变版本，则需要显式导入：
```
x
import scala.collection.mutable
val set1 = mutable.Set("1"，"2")  // 可变版本
set1 += "3" // 可以是 val，也可以是 var

var set2 = Set("1"，"2") // 不可变版本
set2 += "3" // 必须是 var
```
- set1 是可变的 Set[String]，经过+= 方法调用之后，set1 仍然指向旧的Set 。
- set2 是不可变的 Set[String]，经过+= 方法调用之后，set2 指向新创建的 Set 。因此set2 必须是 var 。
Set 的关键特性是：以 == 为标准，同一时刻，Set 内的每个对象最多出现一次。
Set特质的操作：
- 测试：
  - xs contains x：测试 x 是否为 xs 的元素。
  - xs(x)：等价于 xs contains x 。
  - xs subsetOf ys：测试 xs 是否为 ys 的子集。
- 添加：
  - xs + x：返回包含 xs 所有元素以及 x 的新Set。
  - xs + (x,y,z)：返回包含 xs 所有元素以及 x,y,z 的新Set。
  - xs ++ ys ：返回包含 xs 和 ys 所有元素的新Set 。
- 移除：
  - xs - x ：返回包含除 x 外 xs 所有元素的新 Set 。
  - xs - (x,y,z) ：返回包含除 x,y,z 外 xs 所有元素的新 Set 。
  - xs -- ys ：返回包含除 ys元素之外 xs 所有元素的新 Set。
  - xs.empty ：返回跟 xs 类型相同的空Set 。
- 二元操作：
  - xs & ys ：返回xs 和 ys 交集。
  - xs | ys ：返回xs 和 ys 并集。
  - xs union ys：等价于 xs | ys 。
  - xs &~ ys：返回xs 和 ys 差集。
  - xs diff ys：等价于 xs &~ ys 。
可变的 mutable.Set 特质的操作：
- 添加：
  - xs += x ：将 x 添加到 xs 并返回 xs 本身。
  - xs += (x,y,z) ：将 x,y,z 添加到 xs 并返回 xs 本身。
  - xs ++= ys ：将 ys 所有元素添加到 xs 并返回 xs 本身。
  - xs add x ：将元素 x 添加到xs 中。如果 x 此前并未包含在 xs 中，则返回 true；否则返回 false 。
- 移除：
  - xs -= x ：将 x 从 xs 中移除并返回 xs 本身。
  - xs -= (x,y,z) ：将 x,y,z 从 xs中移除并返回 xs 本身。
  - xs -- = ys ：将 ys 所有元素从 xs 中移除并返回 xs 本身。
  - xs remove x ：将元素 x 从 xs中移除。如果x 此前包含在 xs 中，则返回 true；否则返回 false 。
  - xs retrain p ：仅保留 xs 中那些满足条件p 的元素。
  - xs.clear() ：从 xs 中移除所有元素。
- 更新：
  - xs(x) = b ：如果布尔参数 b 为 true ，则将 x 添加到 xs; 否则将 x 从 xs 移除。
  - xs.update(x，b)：等价于 xs(x) = b 。
- 拷贝：
  - xs.clone：返回与xs 有相同元素的新的可变Set 。
Set 的交、并、差集有两种形式：字母的和符号的。字母的版本有 intersect、union、diff ，符号的版本有 & 、| 、&~ 。
Set 从 Traversable 继承的 ++ 可以视为 union 或者 | 的一个别名，只不过 ++ 接受Traversable 类型的参数，而 union 和 | 接受 Set 类型的参数。
Set 的 .apply 方法等价于 .contains 方法，因此 Set 可以被用做测试函数：对于那些它包含的元素返回 true 。
```
xxxxxxxxxx
val s = Set[Int](1,3,5,7,9)
s(1) // 返回 true
```
通常不可变 Set 的 +, ++, -, -- 等操作用的不多，因为它们会拷贝整个Set 来构建一个新的 Set。相比之下，可变 Set 的 +=, ++=, -=, --= 使用得更多。
对于不可变Set ， += 等操作可以配合 var 使用：
```
xxxxxxxxxx
var s  = Set(1,2,3)
s += 4 // 新的 Set (1,2,3,4)
s -= 2 // 新的 Set(1,3,4)

val s2 = mutable.Set(1,2,3)
s2 += 4 // 旧的 Set(1,2,3,4)
s2 -= 2 // 旧的 Set(1,3,4)
```
因此可以看到有一个重要原则：可以用一个 var 的不可变 Set 替换一个 val 的可变 Set ，或者相反。
可变Set 还提供了 add/remove 作为 += 和 -= 的变种。区别在于：前者返回的是表示该 Set 是否发生改变的布尔值结果。
目前可变 Set 默认实现采用了使用Hash 表来保存Set 的元素。不可变 Set 默认实现使用了一个跟 Set 元素数量相匹配的底层表示：
- 空 Set 为单例对象。
- 四个元素以内的 Set 也是由单个以字段保存所有元素的对象。
- 超出四个元素的不可变 Set 实现为哈希字典树hash trie 。
因此，对于四个元素以内的小型Set 而言，不可变 Set 比可变 Set 更加紧凑和高效。因此，如果你预期用到的 Set 比较小，则尽量使用不可变 Set 。

创建空Set 的方法：


xxxxxxxxxx
Set.empty         // 不可变集
mutable.Set.empty // 可变集

初始化collection 最常见方法是将初始元素传入对应collection 的伴生对象的工厂方法。编译器将会将其转换成对伴生对象的 apply 方法的调用。


xxxxxxxxxx
List(1,2,3) // 等价于 List.apply(1,2,3)

你也可以显示的指定类型：


xxxxxxxxxx
List[Long](1,2,3)

如果希望用另一种类型的collection 来初始化，则可以使用 ++ 操作符：


xxxxxxxxxx
val treeSet1 = TreeSet[Long]() ++ List[Long](1,2,3) // 类型为 TreeSet[Long]
val treeSet2 = TreeSet[Long]() ++ List(1,2,3)       // 类型为 TreeSet[Any]

如果希望将其它collection 转换为 Array，则直接调用其 .toArray 方法；如果希望将其它collection 转换为 List，则直接调用其 .toList 方法。
- 调用 toList/toArray 方法时会进行所有元素的拷贝，因此对于大型 collection 来说可能比较费时。
- 对于 Set/Map 等 collection 来说，将它们转化为Array/List 时，转换后的元素顺序等于原始collection 进行迭代的顺序。
  如：TreeSet[Long] 的迭代器会按照数字大小的顺序产生元素，因此对 TreeSet[Long] 调用 toList 是按照大小有序排列的列表。