Go Map 实现 Set 集合

在 Python、Java、C++ 等编程语言中,通常都内置了一种叫做 “集合(Set)” 的数据结构,专门用来保存互不重复的元素。

Go 语言标准库虽然没有单独提供 Set 类型,但同一个 Map 中的键(Key)天生就是唯一的、不能重复的。因此在实际开发中,我们都是把元素存放在键的位置上,直接借助 Map 来实现 Set 集合。

常用的实现方式一般分为 2 种:一种是将值类型设为布尔型 bool,另一种是将值类型设为空结构体 struct{}。

使用 bool 作为值实现 Set(推荐)

在 Go 语言中,实现 Set 集合最直观、最常用的方式,就是把键类型设为要存放的元素类型(如 string 或 int),把值类型设为布尔型 bool。

使用 map[KeyType]bool 当作集合时,我们只关心键是什么,把存入的元素值统一设为 true 即可。以集合变量 set 和元素 key 为例,常用操作如下表所示。

Set 集合常用操作
操作 语法 说明
添加元素 set[key] = true 向集合存入不重复的元素
判断存在 set[key] 存在为 true,否则为 false
删除元素 delete(set, key) 从集合中移除指定元素
元素个数 len(set) 获取集合中元素的总个数

下面我们通过一个例子,演示如何创建集合并完成添加、判断与删除操作。

示例 1:Set 集合的基本操作

package main

import "fmt"

func main() {
    // 创建一个保存字符串的 Set 集合
    set := make(map[string]bool)

    // 添加元素
    set["Go"] = true
    set["Python"] = true
    set["Go"] = true
    fmt.Println(len(set))

    // 判断元素是否存在
    if set["Go"] {
        fmt.Println("集合中包含 Go")
    }

    // 删除元素后再查询
    delete(set, "Python")
    fmt.Println(set["Python"])
}

运行结果如下。

2
集合中包含 Go
false

分析:

在这个例子中,我们向 set 集合中连续添加了两次 "Go" 和一次 "Python"。由于 Map 的键不能重复,第 2 次执行 set["Go"] = true 只是覆盖了原来的值,集合里最终只有两个元素,因此 len(set) 输出为 2。

判断元素是否存在时,我们直接写了 if set["Go"]:如果元素在集合中,读取结果就是 true;如果不在集合中,则会自动返回默认零值 false。最后调用 delete() 函数将 "Python" 移除后,再次查询 set["Python"] 就变成了 false。

这里小伙伴们要特别注意:从集合中移除元素必须使用 delete(),千万不要写成把值改为 false。如果只是把值改成 false,这个键依然留在 Map 里。不仅会导致 len(set) 统计个数出错,后面遍历集合时也会把 "Python" 重新取出来。

// 正确方式
delete(set, "Python")

// 错误方式
set["Python"] = false

提示: 因为 bool 类型的默认零值恰好是 false,把值设为 bool 类型时,我们不需要写 _, ok := set[key]。直接把 set[key] 放进 if 条件里就能判断元素存不存在,写起来非常方便。

如果我们想把 Set 集合里的所有元素逐个打印出来,只需要使用 for range 循环遍历它的键即可。

示例 2:遍历 Set 集合

package main

import "fmt"

func main() {
    set := map[string]bool{
        "Go":     true,
        "Python": true,
        "Java":   true,
    }

    for item := range set {
        fmt.Println(item)
    }
}

运行结果如下。

Go
Python
Java

分析:

由于集合的元素全部保存在键上,我们在遍历集合时不需要关心后面的布尔值 true。直接在 range 左边只写一个变量 item,就能依次取出集合里的每一个元素。

需要注意的是,因为底层使用的是 Map,这种 Set 集合同样是无序的。每次运行程序时,打印出来的先后顺序都可能不一样。

Set 集合的常见应用

在日常开发中,使用 slices.Contains() 配合循环来做切片去重时,如果切片数据量很大(比如有几万个元素),每次从头到尾查找一遍会比较慢。而在 Map 中查找某个键是否存在几乎是瞬间完成的。

因此,遇到需要保留原有顺序的切片去重,或者找出两组数据的共同元素(求交集)这类场景时,我们通常会直接借助 map[int]bool 或 map[string]bool 来实现。

示例 3:利用 Set 对切片去重

package main

import "fmt"

func main() {
    nums := []int{10, 20, 20, 30, 10, 40}

    // 记录已经出现过的数字
    seen := make(map[int]bool)
    var unique []int

    for _, v := range nums {
        if !seen[v] {
            seen[v] = true
            unique = append(unique, v)
        }
    }

    fmt.Println(unique)
}

运行结果如下。

[10 20 30 40]

分析:

你可以把上面代码中的 seen 集合看成一本签到簿。我们在遍历 nums 切片时,每拿到一个数字 v,就通过 if !seen[v] 检查它是不是第一次出现。

借助 Map 对切片去重并保留原序

如果 v 之前还没出现过,seen[v] 会返回默认零值 false,前面加上 ! 取反后条件 !seen[v] 就变成了 true(即尚未登记)。此时程序会先执行 seen[v] = true 做好登记,再把 v 追加到结果切片 unique 中。

当后面再次遇到重复的 20 和 10 时,由于 seen[v] 已经是 true,取反后条件不成立,程序就会直接跳过。这样一来,我们既去掉了重复元素,又保留了各个数字原本出现的先后顺序。

除了给单个切片去重,Set 集合还经常用来对比两组数据,快速找出两边共同拥有的元素(也就是求交集)。

示例 4:求两个集合的交集

package main

import "fmt"

func main() {
    groupA := []string{"Go", "Python", "Java"}
    groupB := []string{"Python", "C++", "Go"}

    // 将第 1 组元素存入 Set
    set := make(map[string]bool)
    for _, item := range groupA {
        set[item] = true
    }

    // 遍历第 2 组,筛选出共同元素
    var common []string
    for _, item := range groupB {
        if set[item] {
            common = append(common, item)
        }
    }

    fmt.Println(common)
}

运行结果如下。

[Python Go]

分析:

在这个例子中,我们先把 groupA 的元素全部登记进 set 集合,再去遍历 groupB。每拿到一个元素 item,只要 set[item] 为 true,就说明它在两组数据里都出现过,直接追加到结果切片 common 中即可。

这种写法比两层嵌套 for 循环逐个比对要快得多。如果 groupB 中本身可能包含重复元素,我们在追加到 common 之后调用 delete(set, item) 把已匹配的元素移除,就能避免结果切片里出现重复值。

顺着同样的思路,如果想找出 “只在 groupB 里出现、不在 groupA 里出现” 的元素(求差集),把判断条件改成 if !set[item] 就可以了,小伙伴们可以自己动手试一下。

使用空结构体实现 Set(了解)

虽然把值设为 bool 类型用起来很方便,但每个布尔值在内存中仍然要占用 1 个字节的空间。如果一个集合需要存放几百万个元素,这些用不上的布尔值也会额外消耗几兆内存。

为了节省这部分空间,有时我们也会把 Map 的值类型换成空结构体 struct{}。关于结构体的完整语法我们会在后面章节详细介绍,这里小伙伴们只需要了解一点:struct{} 表示内部没有任何字段的空结构体类型,它在 Go 语言中占用的内存空间是 0 字节。

向 map[string]struct{} 存入元素时,等号右边需要连写两对花括号 struct{}{},很多初学的小伙伴第一次看到容易看花眼。

其实我们可以对照空切片 []int{} 来拆开看:左边第 1 对花括号所在的 struct{} 是类型名,右边紧跟的第 2 对花括号 {} 表示创建一个该类型的空值。

示例 5:使用空结构体实现 Set

package main

import "fmt"

func main() {
    set := make(map[string]struct{})

    // 存入空结构体值 struct{}{}
    set["Go"] = struct{}{}
    set["Rust"] = struct{}{}

    // 判断 "Go" 是否在集合中
    if _, ok := set["Go"]; ok {
        fmt.Println("集合中包含 Go")
    }
}

运行结果如下。

集合中包含 Go

分析:

set := make(map[string]struct{}) 表示创建一个值类型为空结构体的集合。因为空结构体类型的值不是布尔值,不能直接写 if set["Go"],所以在检查元素是否存在时,我们需要配合 if _, ok := set["Go"]; ok 双返回值语法来判断键是否存在。

注意: 在给 map[string]struct{} 赋值时,struct{}{} 的两对花括号缺一不可。如果少写一对花括号写成 set["Go"] = struct{},编译时就会直接报错。

在实际开发中,对于这两种实现 Set 集合的方式,小伙伴们记住一个简单的选择原则即可。平时数据量不大时,我们优先使用 map[string]bool,代码更加简洁直观。只有当集合需要长期存放几十万甚至上百万条数据、对内存占用要求很严格时,才考虑使用 map[string]struct{}。

上一篇:

下一篇:

给站长反馈

绿叶网正在不断完善中,小伙伴们如果发现任何问题,还望多多给站长反馈,谢谢!

邮箱:lvyenet@vip.qq.com

「绿叶网」服务号
绿叶网服务号放大
关注服务号,微信也能看教程。
绿叶网服务号