数据结构:Hash Set

分享到:  QQ好友和群QQ好友和群 QQ空间QQ空间 腾讯微博腾讯微博 腾讯朋友腾讯朋友 微信微信
查看查看177 回复回复2 收藏收藏 分享淘帖 转播转播 分享分享 微信
查看: 177|回复: 2
收起左侧

数据结构:Hash Set

[复制链接]
Ding 发表于 2016-11-3 13:47:42 | 显示全部楼层 |阅读模式
快来登录
获取最新的苹果动态资讯
收藏热门的iOS等技术干货
拷贝下载Swift Demo源代码
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

都看到这里了,就把这篇资料推荐给您的好朋友吧,让他们也感受一下。

回帖是一种美德,也是对楼主发帖的尊重和支持。

*声明:敏捷大拇指是全球最大的Swift开发者社区、苹果粉丝家园、智能移动门户,所载内容仅限于传递更多最新信息,并不意味赞同其观点或证实其描述;内容仅供参考,并非绝对正确的建议。本站不对上述信息的真实性、合法性、完整性做出保证;转载请注明来源并加上本站链接,敏捷大拇指将保留所有法律权益。如有疑问或建议,邮件至marketing@swifthumb.com

*联系:微信公众平台:“swifthumb” / 腾讯微博:@swifthumb / 新浪微博:@swifthumb / 官方QQ一群:343549891(满) / 官方QQ二群:245285613 ,需要报上用户名才会被同意进群,请先注册敏捷大拇指

嗯,不错!期待更多好内容,支持一把:
支持敏捷大拇指,用支付宝支付10.24元 支持敏捷大拇指,用微信支付10.24元

评分

参与人数 1金钱 +10 贡献 +10 专家分 +10 收起 理由
Anewczs + 10 + 10 + 10 32个赞!专家给力!

查看全部评分

本帖被以下淘专辑推荐:

买定离手 发表于 2016-11-3 23:43:20 | 显示全部楼层
Hash + Set 么?
 楼主| Ding 发表于 2016-11-4 07:57:25 | 显示全部楼层

就是Set,只是因为内部用了基于hash table的dictionary,所以叫HashSet了。
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

做任务,领红包。
我要发帖

分享扩散

都看到这里了,就把这资料推荐给您的好朋友吧,让他们也感受一下。
您的每一位朋友访问此永久链接后,您都将获得相应的金钱积分奖励
热门推荐

合作伙伴

Swift小苹果

  • 北京治世天下科技有限公司
  • ©2014-2016 敏捷大拇指
  • 京ICP备14029482号
  • Powered by Discuz! X3.1 Licensed
  • swifthumb Wechat Code
  •   
快速回复 返回顶部 返回列表