Fork me on GitHub

【译】Swift算法俱乐部-哈希集合

本文是对 Swift Algorithm Club 翻译的一篇文章。
Swift Algorithm Clubraywenderlich.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
4
[1 ,2, 3]
[2, 1, 3]
[3, 2, 1]
[1, 2, 2, 3, 1]

因为每个元素只能出现一次,所以将元素写入的次数并不重要 —— 只有其中一个元素有效。

注意:当我有一组对象但不关心它们的顺序时,我经常更喜欢使用数组上的集合。使用集合与程序员通信,元素的顺序并不重要。 如果你正在使用数组,那么你不能假设同样的事情。

典型集合操作:

  • 插入元素
  • 删除元素
  • 检查集合是否包含元素
  • 与另一组合并
  • 与另一组交叉
  • 计算与另一组的差异

并集,交集和差集是将两个集合组合成一个集合的方法:

Union, intersection, difference

从Swift 1.2开始,标准库包含一个内置的Set类型,但在这里我将展示如何制作自己的类型。您不会在生产代码中使用它,但了解如何实现集合是有益的。

使用简单数组实现集合是可能的,但这不是最有效的方法。 相反,我们将使用字典。由于Swift的字典是使用哈希表构建的,因此我们自己的集合将是一个哈希集。

代码

以下是Swift中HashSet的开头:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
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 并添加一些测试:

1
2
3
4
5
6
7
8
9
10
11
12
13
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操作的代码:

1
2
3
4
5
6
7
8
9
10
11
12
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中的所有元素组成。当然,如果存在重复元素,它们只计算一次。

示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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]

如您所见,两个集合的并集现在包含所有元素。 值34仍然只出现一次,即使它们都在两组中。

两个集合的intersection仅包含它们共有的元素。 这是代码:

1
2
3
4
5
6
7
8
9
10
11
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
}
}

测试:

1
2
let intersection = setA.intersect(setB)
intersection.allElements()

这打印 [3, 4] 因为那些是集合A中也是集合B的唯一对象。

最后,两组之间的difference删除了它们共有的元素。 代码如下:

1
2
3
4
5
6
7
8
9
10
11
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()相反。 试试看:

1
2
3
4
5
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,这样你就可以用forin循环迭代它。

您可以做的另一件事是将Dictionary替换为实际的哈希表,但是只存储键并且不将它们与任何东西相关联。 所以你不再需要Bool值了。

如果您经常需要查找元素是否属于集合并执行并集,那么并查集数据结构可能更合适。它使用树结构而不是字典来使查找和并集操作非常有效。

注意:我想让HashSet符合ArrayLiteralConvertible,这样你就可以编写let setA: HashSet<Int> = [1, 2, 3, 4]但是目前这会使编译器崩溃。

作者:Matthijs Hollemans
翻译:Andy Ron
校对:Andy Ron

坚持原创技术分享,您的支持将鼓励我继续创作!
0%