Swift算法俱乐部
本文是对 Swift Algorithm Club 翻译的一篇文章。
Swift Algorithm Club是 raywenderlich.com网站出品的用Swift实现算法和数据结构的开源项目，目前在GitHub上有18000+⭐️，我初略统计了一下，大概有一百左右个的算法和数据结构，基本上常见的都包含了，是iOSer学习算法和数据结构不错的资源。
🐙andyRon/swift-algorithm-club-cn是我对Swift Algorithm Club，边学习边翻译的项目。由于能力有限，如发现错误或翻译不妥，请指正，欢迎pull request。也欢迎有兴趣、有时间的小伙伴一起参与翻译和学习🤓。当然也欢迎加⭐️，🤩🤩🤩🤨🤪。
本文的翻译原文和代码可以查看🐙swift-algorithm-club-cn/Hash Set
哈希集合（Hash Set）
集合是元素的集合，有点像数组但有两个重要的区别：集合中元素的顺序不重要，每个元素只能出现一次。
如果以下是数组，它们都会有所不同。 但是，它们都代表相同的集合：
[1 ,2, 3]
[2, 1, 3]
[3, 2, 1]
[1, 2, 2, 3, 1]
因为每个元素只能出现一次，所以将元素写入的次数并不重要 —— 只有其中一个元素有效。
注意：当我有一组对象但不关心它们的顺序时，我经常更喜欢使用数组上的集合。使用集合与程序员通信，元素的顺序并不重要。 如果你正在使用数组，那么你不能假设同样的事情。
典型集合操作：
- 插入元素
- 删除元素
- 检查集合是否包含元素
- 与另一组合并
- 与另一组交叉
- 计算与另一组的差异
并集，交集和差集是将两个集合组合成一个集合的方法：
Union, intersection, difference
从Swift 1.2开始，标准库包含一个内置的Set类型，但在这里我将展示如何制作自己的类型。您不会在生产代码中使用它，但了解如何实现集合是有益的。
使用简单数组实现集合是可能的，但这不是最有效的方法。 相反，我们将使用字典。由于Swift的字典是使用哈希表构建的，因此我们自己的集合将是一个哈希集。
代码
以下是Swift中HashSet的开头：
public struct HashSet<T: Hashable> {
fileprivate var dictionary = Dictionary<T, Bool>()
public init() {
}
public mutating func insert(_ element: T) {
dictionary[element] = true
}
public mutating func remove(_ element: T) {
dictionary[element] = nil
}
public func contains(_ element: T) -> Bool {
return dictionary[element] != nil
}
public func allElements() -> [T] {
return Array(dictionary.keys)
}
public var count: Int {
return dictionary.count
}
public var isEmpty: Bool {
return dictionary.isEmpty
}
}
代码非常简单，因为我们依靠Swift的内置Dictionary来完成所有的艰苦工作。 我们使用字典的原因是字典键必须是唯一的，就像集合中的元素一样。 此外，字典在其大多数操作中具有O(1)时间复杂度，使得该集合实现非常快。
因为我们使用的是字典，所以通用类型T必须符合Hashable。 您可以将任何类型的对象放入我们的集合中，只要它可以进行哈希处理即可。 （对于Swift自己的Set也是如此。）
通常，您使用字典将键与值关联，但对于一个集合，我们只关心键。 这就是为什么我们使用Bool作为字典的值类型，即使我们只将它设置为true，而不是false。 （我们本可以选择任何东西，但布尔占用的空间最小。）
将代码复制到 playground 并添加一些测试：
var set = HashSet<String>()
set.insert("one")
set.insert("two")
set.insert("three")
set.allElements() // ["one, "three", "two"]
set.insert("two")
set.allElements() // still ["one, "three", "two"]
set.contains("one") // true
set.remove("one")
set.contains("one") // false
allElements()函数将集合的内容转换为数组。请注意，该数组中元素的顺序可能与添加项目的顺序不同。正如我所说，一个集合并不关心元素的顺序（也不是字典）。
合并集合
集合的很多用处在于如何合并它们。（如果你曾经使用像Sketch或Illustrator这样的矢量绘图程序，你会看到Union，Subtract，Intersect选项来组合形状。这边也是同样的事情。）
这是union操作的代码：
extension HashSet {
public func union(_ otherSet: HashSet<T>) -> HashSet<T> {
var combined = HashSet<T>()
for obj in self.dictionary.keys {
combined.insert(obj)
}
for obj in otherSet.dictionary.keys {
combined.insert(obj)
}
return combined
}
}
两个集合的 union 创建一个新集合，它由集合A中的所有元素加上集合B中的所有元素组成。当然，如果存在重复元素，它们只计算一次。
示例:
var setA = HashSet<Int>()
setA.insert(1)
setA.insert(2)
setA.insert(3)
setA.insert(4)
var setB = HashSet<Int>()
setB.insert(3)
setB.insert(4)
setB.insert(5)
setB.insert(6)
let union = setA.union(setB)
union.allElements() // [5, 6, 2, 3, 1, 4]
如您所见，两个集合的并集现在包含所有元素。 值3和4仍然只出现一次，即使它们都在两组中。
两个集合的intersection仅包含它们共有的元素。 这是代码：
extension HashSet {
public func intersect(_ otherSet: HashSet<T>) -> HashSet<T> {
var common = HashSet<T>()
for obj in dictionary.keys {
if otherSet.contains(obj) {
common.insert(obj)
}
}
return common
}
}
测试:
let intersection = setA.intersect(setB)
intersection.allElements()
这打印 [3, 4] 因为那些是集合A中也是集合B的唯一对象。
最后，两组之间的difference删除了它们共有的元素。 代码如下：
extension HashSet {
public func difference(_ otherSet: HashSet<T>) -> HashSet<T> {
var diff = HashSet<T>()
for obj in dictionary.keys {
if !otherSet.contains(obj) {
diff.insert(obj)
}
}
return diff
}
}
它实际上与intersect()相反。 试试看：
let difference1 = setA.difference(setB)
difference1.allElements() // [2, 1]
let difference2 = setB.difference(setA)
difference2.allElements() // [5, 6]
Where to go from here?
如果你看一下Swift自己的Set的文档，你会发现它有更多的功能。 一个明显的扩展是使HashSet符合SequenceType，这样你就可以用for ...in循环迭代它。
您可以做的另一件事是将Dictionary替换为实际的哈希表，但是只存储键并且不将它们与任何东西相关联。 所以你不再需要Bool值了。
如果您经常需要查找元素是否属于集合并执行并集，那么并查集数据结构可能更合适。它使用树结构而不是字典来使查找和并集操作非常有效。
注意：我想让
HashSet符合ArrayLiteralConvertible，这样你就可以编写let setA: HashSet<Int> = [1, 2, 3, 4]但是目前这会使编译器崩溃。
网友评论