Set di Golang: map[T]struct{}, Operasi Set, dan Set Generic

Idiomnya: map dengan nilai kosong

Go tidak punya kata kunci set dan tidak ada set di standard library. Map yang key-nya adalah elemen dan nilainya tidak membawa apa pun sudah cukup untuk tugas ini.

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{} adalah tipe struct kosong dan struct{}{} adalah satu-satunya nilainya. Ukurannya nol byte, jadi map hanya menyimpan key dan tidak ada yang lain.

Semua aturan map berlaku: key harus bisa dibandingkan, urutan iterasinya acak, map nil memicu panic saat ditulis, dan penulisan concurrent butuh lock. Halaman map membahas masing-masing aturan itu.

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

Cara penulisan lain yang umum adalah map[T]bool. Bentuk ini lebih enak dibaca karena key yang tidak ada mengembalikan false:

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

Untung ruginya:

Baris ketiga adalah alasan sebenarnya banyak codebase lebih memilih struct kosong: dengan bool, suatu saat ada yang menulis s[k] = false dan len(s) tidak lagi sama dengan jumlah anggota. Untuk set yang kecil, perbedaan memorinya tidak berarti.

Menghapus duplikat dari slice

Pemakaian set yang paling umum adalah menghilangkan duplikat. Kode ini mempertahankan kemunculan pertama setiap nilai dan menjaga urutannya:

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

Output:

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

Union, intersection, difference

Aljabar set hanya butuh beberapa perulangan. Lakukan iterasi pada set yang lebih kecil saat menguji keanggotaan di set lainnya, karena setiap pencarian rata-rata berwaktu konstan.

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 hanya ada supaya output-nya stabil. Mencetak set dengan range di atasnya memberikan urutan berbeda setiap kali dijalankan. maps.Keys dan slices.Sorted butuh Go 1.23.

Named type seperti type set map[string]struct{} tetap sebuah map: kamu mengaksesnya dengan indeks, melakukan range, dan delete dengan cara yang sama, dan kamu bisa menambahkan method padanya.

Set generic yang kecil

Dengan generics (Go 1.18), satu tipe mencakup setiap tipe elemen yang comparable. Ini sudah cukup untuk kebanyakan program:

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

Membungkus map di dalam struct menyembunyikan kerumitan struct{}{} dan menjamin map dibuat oleh constructor, sehingga panic karena map nil hilang. Sorted tidak bisa menjadi method: method tidak bisa mendeklarasikan type parameter sendiri atau memperketat constraint comparable milik tipenya, sedangkan pengurutan butuh cmp.Ordered. Halaman generics menjelaskan constraint.

Kalau kamu butuh set yang lengkap fiturnya (varian yang thread-safe, banyak operasi), ada package pihak ketiga seperti github.com/deckarep/golang-set. Untuk kebanyakan kode, idiom map atau tipe sepanjang 30 baris seperti ini sudah menjadi pilihan programmer Go.

Set berisi struct

Tipe apa pun yang comparable bisa menjadi elemen, termasuk struct yang field-nya comparable. Ini membuat pemeriksaan "apakah pasangan ini sudah pernah kulihat" menjadi langsung:

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

Slice dan map tidak bisa menjadi elemen set. Untuk mencatat slice yang unik, ubah dulu setiap slice menjadi key yang comparable, misalnya array berukuran tetap, atau string yang disusun dengan fmt.Sprint.

Kesalahan umum

• Lupa menginisialisasi. var s map[string]struct{} bernilai nil; penambahan pertama akan panic.
• Mencetak set dan mengharapkan output yang stabil. Urutkan anggotanya dulu.
• Memakai map[T]bool lalu menyimpan false. Akibatnya len tidak lagi menghitung jumlah anggota. Pakai delete untuk menghapus.