【译】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
    }
}

测试:

1
2

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]但是目前这会使编译器崩溃。

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