Hash Set

Set就是我国高中数学所描述的Set~  类似Array,但有两点明显不同: Set里的元素无序;Set里没有相同元素。

下边这4个数据集,如果看作Array,将是完全不同的,如果看作Set,则其实是同一个。

[Swift] 纯文本查看 复制代码
[1 ,2, 3]
[2, 1, 3]
[3, 2, 1]
[1, 2, 2, 3, 1]


因每个元素最多出现一次, 无论你写同一个元素多少次,Set里只会出现一个。

Set支持的主要操作应有:

  • 插入一个元素
  • 移除一个元素
  • 检查是否包含某个元素
  • 和另一个Set求并集
  • 和另一个Set求交集
  • 和另一个Set求差集


并集(Union), 交集(Intersection), 和差集(Difference)就是把两个Set整合成一个新的Set:

数据结构:Hash Set

数据结构:Hash Set - 敏捷大拇指 - 数据结构:Hash Set


Swift有原生的Set类型,但现在我们要建立自己的,就叫HashSet吧。我们不会用它开发产品,但可以帮我们理解Set的实现。

可以用一个数组(Array)来实现HashSet,但那种方式并不高效。我们选用更合适的字典(Dictionary, 在Java等语言称作Map)来做。因Swift的字典建立在哈希表(hash table)上,所以我们自己的HashSet将是一个哈希集合。


先做基本定义:

[Swift] 纯文本查看 复制代码
public struct HashSet<T: Hashable> {
    fileprivate var dictionary = Dictionary<T, Bool>()
    
    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
    }
}


代码是如此简单,只因我们用了内建的字典做了那些困难的部分。使用字典的理由是,字典的键必须是互异的,就像Set里的元素。另外,字典的许多操作都是常数级(O(1))的复杂度,这让我们的HashSet成为一个很高效的类型。

也因我们用了字典,HashSet的元素必须遵循Hashable协议。我们可以把任何遵守了Hashable协议的元素放进集合里(Swift原生的Set也是一样)。

一般,我们用字典来关联键和值,但对于Set而言,只关心键。这就是为什么我们用一个Bool做值的原因,且我们总是设置为true而从不设置为false。(实际上可以用任意类型做值,但Bool类型占用的空间最少)。

[Swift] 纯文本查看 复制代码
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() 函数把Set里的元素放在了一个数组里返回。这个数组里元素的顺序很可能和你之前王Set里添加时候的顺序不一样,就像前面说的,Set并不在乎元素的顺序——当然,字典也是一样。



两个Set的操作

集合最大的用处在于对不同的集合的操作。 (若你在Setch或Illustrator这样的软件里用向量绘制过图表,你一定对交集、并集、差集这些操作深有体会。)

添加下并集操作:

[Swift] 纯文本查看 复制代码
extension HashSet {
    public func union(_ otherSet: HashSet<T>) -> HashSet<T> {
        var combined = HashSet<T>()
        for obj in dictionary.keys {
            combined.insert(obj)
        }
        for obj in otherSet.dictionary.keys {
            combined.insert(obj)
        }
        return combined
    }
}


集合A和集合B的并集就是A和B的所有元素组成的新的集合。当然,如果有重复元素,新集合里只会保留一个。

来点例子:

[Swift] 纯文本查看 复制代码
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]



交集:

[Swift] 纯文本查看 复制代码
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
    }
}


例子:

[Swift] 纯文本查看 复制代码
let intersection = setA.intersect(setB)
intersection.allElements()     // [3, 4]


最后,差集:

[Swift] 纯文本查看 复制代码
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
    }
}


例子:

[Swift] 纯文本查看 复制代码
let difference1 = setA.difference(setB)
difference1.allElements()                // [2, 1]

let difference2 = setB.difference(setA)
difference2.allElements()                // [5, 6]


数据结构:Hash Set

数据结构:Hash Set - 敏捷大拇指 - 数据结构:Hash Set





接下来干嘛?

如果看了Swift原生的Set文档,会注意到那里有更加丰富的方法可用。很明显,HashSet还需扩展。一个明显的扩展是让它遵循SequenceType协议,从而可以用for...in来遍历。

另一件可做的事是把字典用真正的哈希表(Hash Table)替换掉, 只存键而不存值,所以我们连Bool这样的值都可不要了。

如果你经常检查某个元素是否包含在某个集合里,或者经常做并集操作,Union-Find这个数据结构将会更合适。它用了树(tree)而不是字典来做查找元素或者求并集之类的操作,效率上更好。




原作者: Matthijs Hollemans