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
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
网友评论