Go 集合 Set：map[T]struct{}、集合运算与泛型 Set

惯用写法：值为空的 map

Go 没有 set 关键字，标准库中也没有集合。一个以元素为键、值不携带任何内容的 map 就能完成这项工作。

package main

import "fmt"

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

	// add
	tags["go"] = struct{}{}
	tags["backend"] = struct{}{}
	tags["go"] = struct{}{} // adding again changes nothing

	// has
	_, ok := tags["go"]
	fmt.Println("has go:", ok)

	// remove
	delete(tags, "backend")

	// size
	fmt.Println("size:", len(tags))

	for t := range tags {
		fmt.Println("member:", t)
	}
}

struct{} 是空结构体类型，struct{}{} 是它唯一的值。它占零字节，所以这个 map 只存储键，别的什么都不存。

map 的所有规则在这里都适用：键必须是可比较的，遍历顺序是随机的，向 nil map 写入会 panic，并发写入需要加锁。map 页面逐一介绍了这些规则。

map[T]struct{} 还是 map[T]bool

另一种常见写法是 map[T]bool。它读起来更顺，因为不存在的键会返回 false：

seen := map[string]bool{}
seen["a"] = true
if seen["a"] { ... }

两者的取舍：

第三行才是很多代码库偏爱空结构体的真正原因：用 bool 的话，迟早会有人写出 s[k] = false，于是 len(s) 就不再是成员的数量。对于小集合，内存上的差别无关紧要。

去除 slice 中的重复元素

集合最常见的用途就是去重。下面的写法保留每个值第一次出现的位置，并保持原有顺序：

package main

import (
	"fmt"
	"slices"
)

func unique[T comparable](in []T) []T {
	seen := make(map[T]struct{}, len(in))
	out := make([]T, 0, len(in))
	for _, v := range in {
		if _, ok := seen[v]; ok {
			continue
		}
		seen[v] = struct{}{}
		out = append(out, v)
	}
	return out
}

func main() {
	fmt.Println(unique([]string{"b", "a", "b", "c", "a"}))
	fmt.Println(unique([]int{3, 1, 3, 3, 2}))

	// If order does not matter: sort, then drop adjacent duplicates.
	s := []int{3, 1, 3, 3, 2}
	slices.Sort(s)
	fmt.Println(slices.Compact(s))
}

输出：

[b a c]
[3 1 2]
[1 2 3]

并集、交集、差集

集合运算只需要几个循环。在另一个集合中判断是否存在时，遍历较小的那个集合，因为每次查找平均都是常数时间。

package main

import (
	"fmt"
	"maps"
	"slices"
)

type set map[string]struct{}

func of(items ...string) set {
	s := make(set, len(items))
	for _, it := range items {
		s[it] = struct{}{}
	}
	return s
}

func union(a, b set) set {
	out := maps.Clone(a)
	for k := range b {
		out[k] = struct{}{}
	}
	return out
}

func intersect(a, b set) set {
	if len(a) > len(b) {
		a, b = b, a
	}
	out := set{}
	for k := range a {
		if _, ok := b[k]; ok {
			out[k] = struct{}{}
		}
	}
	return out
}

func difference(a, b set) set {
	out := set{}
	for k := range a {
		if _, ok := b[k]; !ok {
			out[k] = struct{}{}
		}
	}
	return out
}

func sorted(s set) []string {
	return slices.Sorted(maps.Keys(s))
}

func main() {
	backend := of("go", "sql", "docker", "linux")
	devops := of("docker", "linux", "terraform")

	fmt.Println("union:     ", sorted(union(backend, devops)))
	fmt.Println("intersect: ", sorted(intersect(backend, devops)))
	fmt.Println("backend-only:", sorted(difference(backend, devops)))
}

sorted 只是为了让输出稳定。通过 range 遍历来打印集合，每次运行的顺序都不同。maps.Keys 和 slices.Sorted 需要 Go 1.23。

像 type set map[string]struct{} 这样的命名类型仍然是 map：你可以用同样的方式对它索引、range 遍历和 delete，还可以给它定义方法。

一个小巧的泛型 Set

有了泛型（Go 1.18），一个类型就能覆盖所有可比较的元素类型。对大多数程序来说，这已经足够了：

package main

import (
	"cmp"
	"fmt"
	"maps"
	"slices"
)

type Set[T comparable] struct {
	m map[T]struct{}
}

func NewSet[T comparable](items ...T) *Set[T] {
	s := &Set[T]{m: make(map[T]struct{}, len(items))}
	for _, it := range items {
		s.Add(it)
	}
	return s
}

func (s *Set[T]) Add(v T)    { s.m[v] = struct{}{} }
func (s *Set[T]) Remove(v T) { delete(s.m, v) }
func (s *Set[T]) Len() int   { return len(s.m) }
func (s *Set[T]) Has(v T) bool {
	_, ok := s.m[v]
	return ok
}

func (s *Set[T]) Union(o *Set[T]) *Set[T] {
	out := &Set[T]{m: maps.Clone(s.m)}
	for v := range o.m {
		out.Add(v)
	}
	return out
}

// Sorted is a free function because it needs a stricter constraint than the type.
func Sorted[T cmp.Ordered](s *Set[T]) []T {
	return slices.Sorted(maps.Keys(s.m))
}

func main() {
	a := NewSet(1, 2, 3)
	b := NewSet(3, 4)
	a.Add(2)
	fmt.Println(a.Len(), a.Has(2), a.Has(9))

	u := a.Union(b)
	fmt.Println(Sorted(u))

	words := NewSet("go", "rust")
	words.Remove("rust")
	fmt.Println(Sorted(words))
}

把 map 包装在结构体中，可以隐藏 struct{}{} 这样的噪音，并保证 map 由构造函数创建，从而避免 nil map 引发的 panic。Sorted 不能是方法：方法不能声明自己的类型参数，也不能收紧类型的 comparable 约束，而排序需要 cmp.Ordered。泛型页面讲解了约束。

如果你需要功能完整的集合（线程安全的版本、丰富的操作），可以使用 github.com/deckarep/golang-set 这样的第三方包。对于大多数代码，Go 程序员用的就是 map 惯用写法，或者像这样一个 30 行左右的类型。

结构体集合

任何可比较的类型都可以作为元素，包括字段都可比较的结构体。这让“我是否见过这一对”这类检查变得很直接：

type edge struct{ from, to string }
visited := map[edge]struct{}{}
visited[edge{"a", "b"}] = struct{}{}

slice 和 map 不能作为集合元素。要跟踪不重复的 slice，先把每个 slice 转换成可比较的键，例如固定大小的数组，或用 fmt.Sprint 构建的字符串。

常见错误

• 忘记初始化。 var s map[string]struct{} 是 nil；第一次添加就会 panic。
• 打印集合并期望输出稳定。 先对成员排序。
• 使用 map[T]bool 并存入 false。 这样 len 就不再是成员的数量。删除元素要用 delete。