21 Set的定义和创建

Set的定义和创建

Set的概念

• Set是指具有某种特定性质的具体的或抽象的对象汇总而成的集体。其中，构成Set的这些对象则称为Set的元素

集合的三个特性

• 确定性：给定一个集合，任给一个元素，该元素或者属于或者不属于该集合，二者必居其一
• 互斥性：一个集合中，任何两个元素都认为是不相同的，即每个元素只能出现一次
• 无序性：一个集合中，每个元素的地位都是相同的，元素之间是无序的

Swift里面的集合

• Swift的集合类型写做Set<Element>,这里的Element是Set要储存的类型。不同与数组，集合没有等价的简写

创建Set

• 使用初始化器语法来创建一个确定类型的空Set
• 使用数组字面量创建Set

image-20230224220454067.png

Set类型的哈希值

• 为了能让类型储存在Set当中，他必须是可哈希的--就是说类型必须提供计算它自身哈希值的方法
• 所有Swift的基础类型（比如String，Int，Double，和Bool）默认都是可哈希的，并且可以用于Set或者Dictionary的键

image-20230224220800751.png

• 自定义类型需要实现Hashable协议

image-20230224220855076.png

访问和修改

Set的遍历

• 可以使用For-In遍历Set
• 因为Set是无序的，如果要顺序遍历Set，使用sorted()方法

image-20230224221325862.png

访问Set

• 使用count获取Set里元素个数
• 使用isEmpty判断Set是否为空

image-20230224221523899.png

添加元素

• insert(_:)添加一个元素到Set
• update(with:)如果已经有相等的元素，替换为新元素。如果Set中没有，则插入

image-20230224221651276.png

移除元素

• filter(_:)返回一个新的Set，新Set的元素是原始Set符合条件的元素

image-20230224222318610.png

• remove(_:)从Set当中移除一个元素，如果元素是Set的成员就移除它，并且返回移除的值，如果合集没有这个成员就返回nil
• removeAll()移除所有元素

image-20230224222525522.png

• removeFirst()移除Set的第一个元素，因为Set是无序的， 所以第一个元素并不是放入的第一个元素

image-20230224222658228.png

执行Set计算和判断

基本Set操作

image-20230224223206220.png

基本Set操作的定义

• intersection(_:)交集，由属于A且属于B的相同元素组成的集合，记作A∩B（或B∩A）
• union(_:)并集，由所有属于集合A或属于集合B的元素所组成的集合，记作A∪B（或B∪A）
• symmetricDifference(_:)对称差集，集合A与集合B的对称差集定义为集合A与集合B中所有不属于A∩B的元素的集合
• subtracting(_:)相对补集，由属于A而不属于B的元素组成的集合，称为B关于A的相对补集，记作A-B或A\B

image-20230225145708014.png

Set判断方法

• isSubset(of:)判断是否是另一个Set或者Sequence的子集
• isSuperset(of:)判断是否是另一个Set或者Sequence的超集
• isStrictSubset(of:)和isStrictSuperset(of:)判断是否是另一个Set的子集或者超集，但是又不等于另一个Set
• isDisjoint(with:)判断两个Set是否有公共元素，如果没有返回true，如果有返回false

image-20230225150247261.png

实现自己的集合算法

• 给定一个集合，返回这个集合所有的子集
  • 思路：解这道题的思想本质上就是元素选与不选的问题，于是我们就可以想到用二进制来代表选与不选的情况。”1“代表这个元素已经选择，而”0“代表这个元素没有选择。假如三个元素A B C，那么101就代表B没有选择，所以101代表的子集为AC

image-20230225151748975.png

//上方的方法名定义应为
func getSubsetsOfSet<T>(_ set: Set<T>) -> Array<Set<T>> {}

//上面方法的限制， set.count如果超出64位
//则就超出所以平台限制

• 思路：如果只有一个元素，那么它的子集有两个，分别是本身和空集，然后在已经有一个元素的子集的基础上，第二个元素有两种选法，那就是加入到前面的子集里面或者不加入到前面的子集里面，也就是选与不选的问题。而前面的子集一共有两个，对每一个子集都有来自于下一个元素的加入和不加入两种选法。那么就可以得出两个元素的子集一共有四个。以此类推，就可以得出n的元素所有子集（这里n个元素的子集一共有2n个，非空子集一共有2n-1个）

image-20230225203020179.png

//上面方法名修正
func getSubsets2<T>(_ set: Set<T>) -> Array<Set<T>> {}

func getSubsets3<T>(_ elements: Array<T>, index: Int, count： Int) -> Array<Set<T>>{}

练习

• 将思路二的递归改成迭代

底层实现探究

从Set的insert说起

image-20230225211247027.png

_NativeSet的find方法

image-20230225211421478.png

HashTable

image-20230225211512680.png image-20230225211638405.png

线性探测的开放寻址法

image-20230225211826112.png

_NativeSet的insertNew

image-20230225212027885.png

HashTable的insertNew

image-20230225212110912.png

_NativeSet的uncheckedInitialize

image-20230225212216063.png