Idiomatic Go Set

Go Set 数据结构的地道写法

@ Go

前言

记录近期从 JavaScript 迁移到 Go 的过程中实践 Set 数据结构的方式。之前的代码使用 JavaScript Set🔗 来实现不重复的数据定义，但在 Go 语言中并没有内建 Set 数据结构，我们可以通过改造 map 来实现。

Set 定義

一种「元素唯一」的数据结构，用于表示不重复值的集合
  • 元素不可重复
  • 通常可以快速查找内容（例如：set.has('foobar')，O(1)）
  • 通常不强调顺序索引

Map 實踐 Set

要对数据去重，最简单的方式是把它们都放到 Map 中，重复写入也不用担心：

s := map[int]bool{5: true, 2: true}
_, ok := s[6] // 检查是否存在
s[8] = true   // 添加
delete(s, 2)  // 删除

利用空 struct 不佔空間的特性

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

原因是 struct 不占用任何内存空间，而 bool 仍需 1 byte。當 Set 儲存大量元素時，使用 struct 可以有效節省記憶體。

泛型版本

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


func NewSet[T comparable]() *Set[T] {
    return &Set[T]{m: make(map[T]struct{})}
}


func (s *Set[T]) Add(v T) {
    s.m[v] = struct{}{}
}


func (s *Set[T]) Has(v T) bool {
    _, ok := s.m[v]
    return ok
}


func (s *Set[T]) Remove(v T) {
    delete(s.m, v)
}


func (s *Set[T]) Len() int {
    return len(s.m)
}

延伸閱讀