Set trong Golang: map[T]struct{}, phép toán và Set generic

Cách viết chuẩn: map với giá trị rỗng

Go không có từ khóa set và thư viện chuẩn cũng không có set. Một map có khóa là các phần tử và giá trị không mang gì là đủ dùng.

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{} là kiểu struct rỗng và struct{}{} là giá trị duy nhất của nó. Nó chiếm 0 byte, nên map chỉ lưu khóa và không gì khác.

Mọi quy tắc của map đều áp dụng: khóa phải so sánh được, thứ tự duyệt là ngẫu nhiên, ghi vào map nil sẽ gây panic, và ghi đồng thời cần khóa (lock). Trang map giải thích từng điểm.

map[T]struct{} hay map[T]bool

Cách viết phổ biến còn lại là map[T]bool. Nó dễ đọc hơn vì khóa không tồn tại trả về false:

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

So sánh hai cách:

Hàng thứ ba mới là lý do thật khiến nhiều codebase chuộng struct rỗng: với bool, sớm muộn sẽ có người viết s[k] = false và len(s) không còn là số phần tử nữa. Với set nhỏ, chênh lệch bộ nhớ không đáng kể.

Xóa phần tử trùng lặp khỏi slice

Công dụng phổ biến nhất của set là loại bỏ trùng lặp. Đoạn code này giữ lần xuất hiện đầu tiên của mỗi giá trị và giữ nguyên thứ tự:

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))
}

Đầu ra:

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

Hợp, giao, hiệu

Các phép toán trên tập hợp chỉ là vài vòng lặp. Khi kiểm tra thành viên trong set còn lại, hãy duyệt set nhỏ hơn, vì mỗi lần tra cứu trung bình tốn thời gian hằng số.

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 chỉ có mặt để đầu ra ổn định. In một set bằng cách duyệt range sẽ cho thứ tự khác nhau sau mỗi lần chạy. maps.Keys và slices.Sorted cần Go 1.23.

Một kiểu đặt tên như type set map[string]struct{} vẫn là map: bạn truy cập theo khóa, range và delete trên nó y như cũ, và có thể gắn phương thức cho nó.

Một kiểu Set generic nhỏ

Với generics (Go 1.18), một kiểu duy nhất dùng được cho mọi kiểu phần tử so sánh được. Như thế này là đủ cho hầu hết chương trình:

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))
}

Bọc map trong một struct giúp giấu đi phần struct{}{} rườm rà và bảo đảm map luôn được hàm khởi tạo tạo ra, nhờ đó loại bỏ panic do map nil. Sorted không thể là phương thức: phương thức không được khai báo tham số kiểu riêng hay siết chặt ràng buộc comparable của kiểu, mà sắp xếp lại cần cmp.Ordered. Trang generics giải thích về ràng buộc.

Nếu cần một set đầy đủ tính năng (phiên bản an toàn luồng, nhiều phép toán), có các package bên thứ ba như github.com/deckarep/golang-set. Với phần lớn code, lập trình viên Go dùng cách viết bằng map hoặc một kiểu khoảng 30 dòng như trên.

Set chứa struct

Kiểu nào so sánh được cũng làm phần tử được, kể cả struct có các trường so sánh được. Nhờ vậy kiểm tra "mình đã gặp cặp này chưa" trở nên đơn giản:

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

Slice và map không thể là phần tử của set. Để theo dõi các slice không trùng nhau, trước hết hãy chuyển mỗi slice thành một khóa so sánh được, ví dụ một mảng có kích thước cố định, hoặc một chuỗi tạo bằng fmt.Sprint.

Lỗi thường gặp

• Quên khởi tạo. var s map[string]struct{} là nil; lần thêm đầu tiên sẽ panic.
• In set và mong đầu ra ổn định. Hãy sắp xếp các phần tử trước.
• Dùng map[T]bool và lưu false. Khi đó len không còn đếm đúng số phần tử. Hãy dùng delete để xóa.