Go語言中關于set的實現思考分析

更新時間：2024年01月18日 08:12:16 作者：visforest

Go?開發(fā)過程中有時我們需要集合（set）這種容器,但?Go?本身未內置這種數據容器,故常常我們需要自己實現,下面我們就來看看具體有哪些實現方法吧

map[xxx]struct{}

最常用和最容易想到的實現是使用 map，如：

type StrSet struct{
    data map[string]struct{}
}

map 的 value 部分設計為 struct{} 類型是為了節(jié)省內存空間。

map[interface{}]struct{}

上面實現的是 string 的 set，如果要其他類型的 set 就得再定義 Int8Set、IntSet、Float32Set 等等，很是繁瑣。

很多人可能會選擇這樣實現 :

type Set struct {
	data map[interface{}]struct{}
}

// New creates a new Set
func New(v ...interface{}) *Set {
	s := &Set{data: map[interface{}]struct{}{}}
	for _, ele := range v {
		s.data[ele] = struct{}{}
	}
	return s
}

// ...

// ToList returns data slice
func (s *Set) ToList() []interface{} {
	var data = make([]interface{}, len(s.data))
	var i int
	for d := range s.data {
		data[i] = d
		i++
	}
	return data
}

這種方式有幾個問題：

執(zhí)行如下代碼：

func main() {
	var l1 = []int{1, 2, 3}
	var l2 = []int{4, 5, 6}
	var s = NewSet(l1, l2)
	for _, e := range s.ToList() {
		fmt.Println(e)
	}
}

出錯：

panic: runtime error: hash of unhashable type []int

原因很簡單，[]int 是不能被 hash 計算的，即不能作為 map 的 key，讀者可以查閱 map key允許的類型。interface{} 這種“萬金油” 也可能是不合適的。

觀察下面代碼

func main() {
	var s = NewSet("a", "b", "c")
	var tmp []string
	for _, e := range s.ToList() {
		tmp = append(tmp, e.(string))
	}
	test(tmp)
}

test 函數不能直接拿 s.ToList() 作為入參，必須將 s.ToList() 進行轉換為 []string，原因不言自明。

每次都要轉換明顯損失了編碼效率和執(zhí)行效率。

map[T comparable]struct{}

上面的弊端，可以用泛型（generics）解決。

定義：

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

// New creates a new Set
func NewSet[T comparable](v ...T) *Set[T] {
	s := &Set[T]{data: map[T]struct{}{}}
	for _, ele := range v {
		s.data[ele] = struct{}{}
	}
	return s
}

func (s *Set[T]) Add(v ...T) {
	for _, ele := range v {
		s.data[ele] = struct{}{}
	}
}

// ...

// ToList returns data slice
func (s *Set[T]) ToList() []T {
	var data = make([]T, len(s.data))
	var i int
	for d := range s.data {
		data[i] = d
		i++
	}
	return data
}

使用：

func test1(data []string) {
	// ...
}

func test2(data []float64) {
	// ...
}

func main() {
	var s1 = NewSet("a", "b", "c")
	test1(s1.ToList())

	var s2 = NewSet(1.3, 2.2, 3)
	test2(s2.ToList())
}

type IntSet = Set[int]

上面的 Set 是個通用 set，類型混用時自己可能會被誤導。我們可以定義專用數據類型的 set，且代碼不需要很多。

type IntSet = Set[int]

func NewIntSet(v ...int) *IntSet {
	return NewSet[int](v...)
}

使用：

func main() {
	var s = NewIntSet(1, 2, 3)
	test3(s.ToList())

	// 編譯錯誤
	// s.Add("a", "b", "c")
}

fifo set

通常 set 是無序的，上面的實現也都是無序的，但有的場景下我們需要有序的 set，比如fifo set，sorted set。這里以 fifo set 為例，討論下其實現。

為了兼顧查找效率和有序特性，可以使用 map + array / double linkedlist，考慮到數據的添加、刪除以及內存使用，double linkedlist 有比 array 顯著的優(yōu)勢。

type setNode[T comparable] struct {
	val  T
	pre  *setNode[T]
	next *setNode[T]
}

type FifoSet[T comparable] struct {
	head *setNode[T]
	tail *setNode[T]
	data map[T]*setNode[T]
}

// add data, make it first in first out
func (l *FifoSet[T]) Add(v ...T) {
	if len(v) == 0 {
		return
	}

	var i int
	if l.head == nil {
		// first node
		n := &setNode[T]{
			val: v[i],
		}
		l.head = n
		l.tail = n
		l.data[v[i]] = n
		i++
	}
	for ; i < len(v); i++ {
		if _, ok := l.data[v[i]]; !ok {
            // when missing, insert
			n := &setNode[T]{
				val:  v[i],
				pre:  l.tail,
				next: nil,
			}
			l.tail.next = n
			l.tail = n
			l.data[v[i]] = n
		}
	}
}

使用：

func main() {
	var s = NewFifoSet[string]()
	s.Add("e", "a", "b", "a", "c", "b")
	// e
	// a
    // b
	// c
	for _, v := range s.ToList() {
		fmt.Println(v)
	}
}