go語言中數據接口set集合的實現

更新時間：2024年10月21日 11:24:46 作者：SRExianxian

set集合是一種常見的數據結構,它代表了一個唯一元素的集合,本文主要介紹了set的基本特性,包括唯一性、無序性、可變性和集合運算,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧

概述

set 是一種常用的數據結構，它表示一組唯一元素的集合。在不同的編程語言和庫中，set 可能有不同的實現方式和特性。

set 集合數據結構具有以下特性：

唯一性：set 中的元素是唯一的，不允許重復。這意味著在 set 中添加重復的元素不會產生任何變化。
無序性：set 中的元素沒有順序。不能通過索引訪問 set 中的元素，也不能對 set 中的元素進行排序。
可變性：set 通常是可變的，這意味著你可以添加或刪除元素。
集合運算：set 支持多種集合運算，如并集、交集和差集。

在這里插入圖片描述

Go語言中最常用的兩種數據結構分別是 slice 和 map。除了 Go 內置的數據結構，還有一些數據結構是由 Go 的官方 container 包提供，如 heap 堆、list 雙向鏈表和ring 回環(huán)鏈表。但Go語言中并沒有內置set這種數據結構。本文聊聊go語言中set的實現方式。

我們知道 map 的鍵是具有唯一性，所以可以用 map 來實現數據結構 set。

set的實現

使用map使用一個set集合，意味著我們只關心 key 的存在，其 value 值并不重要，直接將vlaue設置為空接口。

package main

import (
	"errors"
	"fmt"
	"sync"
)

/*
用map實現一個線程安全的set
*/

type void struct{}

var member void

type IData interface{}

type Set struct {
	mapset map[IData]struct{}
	mutex  sync.Mutex
}

func NewSet() *Set {
	return &Set{
		mapset: make(map[IData]struct{}),
		mutex:  sync.Mutex{},
	}
}

func (s *Set) Add(data IData) bool {
	s.mutex.Lock()
	defer s.mutex.Unlock()
	s.mapset[data] = member
	return true
}

func (s *Set) Remove(data IData) error {
	s.mutex.Lock()
	defer s.mutex.Unlock()
	for k, _ := range s.mapset {
		if k == data {
			delete(s.mapset, k)
			return nil
		}
	}
	return errors.New("not found")
}

func (s *Set) Pop() IData {
	s.mutex.Lock()
	defer s.mutex.Unlock()
	if len(s.mapset) <= 0 {
		return nil
	}
	for k, _ := range s.mapset {
		return s.mapset[k]
	}
	return nil
}

func (s *Set) Size() int {
	s.mutex.Lock()
	defer s.mutex.Unlock()
	return len(s.mapset)

}

func (s *Set) All() []IData {
	s.mutex.Lock()
	defer s.mutex.Unlock()
	datas := make([]IData, 0)
	for k, _ := range s.mapset {
		datas = append(datas, k)
	}
	return datas
}

func main() {
	// test
	myset := NewSet()
	myset.Add(1)
	myset.Add(2)
	myset.Add(1)
	fmt.Println(myset.All()) // [1 2]

	myset.Add(3)
	fmt.Println(myset.Size()) //3
	fmt.Println(myset.All())  // [1 2 3]

	myset.Remove(2)
	fmt.Println(myset.All()) // [1 2 3]

}

set的三方庫

在kubernetes中也實現了stirng,int32,int43,byte等幾種基本類型為值的set集合。接下來我們分析下源碼實現。找到源碼為位置k8s.io/apimachinery/pkg/util/sets

// sets.String is a set of strings, implemented via map[string]struct{} for minimal memory consumption.
// String類型定義，使用map來實現set集合，集合的元素是string
type String map[string]Empty

// NewString creates a String from a list of values.
// 構造一個set，set集合存放的值是string類型
func NewString(items ...string) String {
	ss := String{}
	ss.Insert(items...)
	return ss
}


// Insert adds items to the set.
// 插入元素到集合
func (s String) Insert(items ...string) String {
	for _, item := range items {
		s[item] = Empty{}
	}
	return s
}

// Delete removes all items from the set.
// 從set中刪除指定string
func (s String) Delete(items ...string) String {
	for _, item := range items {
		delete(s, item)
	}
	return s
}

// Has returns true if and only if item is contained in the set.
// 判斷set是否包含指定的string
func (s String) Has(item string) bool {
	_, contained := s[item]
	return contained
}

// HasAll returns true if and only if all items are contained in the set.
// 判斷set是否包括一組所有的字符串
func (s String) HasAll(items ...string) bool {
	for _, item := range items {
		if !s.Has(item) {
			return false
		}
	}
	return true
}

// HasAny returns true if any items are contained in the set.
// 判斷一組字符串是否有包括在set中
func (s String) HasAny(items ...string) bool {
	for _, item := range items {
		if s.Has(item) {
			return true
		}
	}
	return false
}