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

延伸閱讀