golang-set包的用法及源码解析

Set是一种基本的数据结构,它具备确定性、互异性、无序性三个特点。因此，在开发过程中我们通常用它来判断一些数据的集合与另一个数据集合或者元素的包含关系。在大部分开发语言中set都是一种基本的数据结构，但是golang不提供set类型。通常情况下，我们都会用map[interface{}]struct{}{}来代替set实现包含关系的判断。但事实上，我们在github上会发现一些第三方的开源包。例如golang-set就是一个相对成熟的包。截止到2021年3月份已经有1.8k的star和160+的fork。同时这个包本身也已经应用于docker项目中。是一个可用性和可靠性都经过验证的第三方包，大家可以放心使用。

golang-set包本身也是基于map[interface{}]struct{}{}结构实现的，同时golang-set包提供了线程安全和不保证安全的两种set类型，相比于线程安全的set对象，不保证安全的set对象执行效率会更高一点。

2、使用方法

golang-set的使用也非常简单，只需导入该包然后创建set对象即可开始使用。

import mapset "github.com/deckarep/golang-set"

set := mapset.NewSet(1, 2, 3, 4)
set.Add(6)

set.Contains(5)
set.Remove(1)

golang 提供了两种set类型，一种是普通的集合对象，一种是线程安全的集合对象，通过结构嵌套的方式为普通集合对象新增了一个全局锁，实现了线程安全。具体如下：

type threadSafeSet struct {
    s threadUnsafeSet
    sync.RWMutex
}

func newThreadSafeSet() threadSafeSet {
    return threadSafeSet{s: newThreadUnsafeSet()}
}

golang-set包提供的集合操作方法包含如下23个方法：

type Set interface {
    Add(i interface{}) bool
    Cardinality() int
    Clear()
    Clone() Set
    Contains(i ...interface{}) bool
    Difference(other Set) Set
    Equal(other Set) bool
    Intersect(other Set) Set
    IsProperSubset(other Set) bool
    IsProperSuperset(other Set) bool
    IsSubset(other Set) bool
    IsSuperset(other Set) bool
    Each(func(interface{}) bool)
    Iter() <-chan interface{}
    Iterator() *Iterator
    Remove(i interface{})
    String() string
    SymmetricDifference(other Set) Set
    Union(other Set) Set
    Pop() interface{}
    PowerSet() Set
    CartesianProduct(other Set) Set
    ToSlice() []interface{}
}

具体含义如下：

• Add(i interface{}) bool:用于向集合中添加某些元素

• Cardinality() int ：返回集合元素个数

• Clear() ：清空集合中全部元素，剩下一个空的集合，使用不需要通过NewSet进行初始化

• Clone() Set ：复制一个一模一样的集合对象

• Contains(i ...interface{}) bool ：返回是否参数元素全部包含于集合中

• Difference(other Set) Set ：将返回当前集合与参数集合的全部差异元素，这些元素包含于本集合但是不包含于参数集合。注意：入参的set类型与方法接受者set的类型必须一致，否则将导致panic。

• Equal(other Set) bool ：如果参数集合与当前集合的容量和全部元素是相同的，那么会被然认为是相同的，无需考虑元素的顺序。注意：入参的set类型与方法接受者set的类型必须一致，否则将导致panic。

• Intersect(other Set) Set：将返回两个集合的交集。注意：入参的set类型与方法接受者set的类型必须一致，否则将导致panic。

• IsProperSubset(other Set) bool：判断当前set是否为参数set的真子集（包含但不相等）。注意：入参的set类型与方法接受者set的类型必须一致，否则将导致panic。

• IsProperSuperset(other Set) bool：判断参数set是否为当前set的真子集（包含但不相等）。注意：入参的set类型与方法接受者set的类型必须一致，否则将导致panic。

• IsSubset(other Set) bool：判断当前set是否为参数set的子集（包含，允许相等）。注意：入参的set类型与方法接受者set的类型必须一致，否则将导致panic。

• IsSuperset(other Set) bool：判断参数set是否为当前set的子集（包含，允许相等）。注意：入参的set类型与方法接受者set的类型必须一致，否则将导致panic。

• Each(func(interface{}) bool)：遍历元素，并对每个元素执行传递的func。如果传递的func返回true，则此时停止迭代。

  //clone a
  b := NewSet()
  a.Each(func(elem interface{}) bool {
      b.Add(elem)
      return false
  })
  

• Iter() <-chan interface{}：返回一个可以遍历set的channel

  b := NewSet()
  for val := range a.Iter() {
      b.Add(val)
  }
  

• Iterator() *Iterator：返回一个Iterator对象，用于遍历set的全部参数。

  b := NewThreadUnsafeSet()
  for val := range a.Iterator().C {
      b.Add(val)
  }
  

• Remove(i interface{}) :从当前集合中移除某个元素

• String() string：返回集合的string格式，set:{}用于查看该集合。

• SymmetricDifference(other Set) Set：返回当前集合与参数集合的对称差集（对称差集中的元素要么包含于本集合，要么包含于参数集合，但是不能属于两者的交集）。注意：入参的set类型与方法接受者set的类型必须一致，否则将导致panic。

• Union(other Set) Set：返回当前集合与参数集合的并集。注意：入参的set类型与方法接受者set的类型必须一致，否则将导致panic。

• Pop() interface{}：移除并返回一个随机的元素

• PowerSet() Set：返回当前集合的全部子集

• CartesianProduct(other Set) Set：返回当前集合与参数集合的笛卡尔积结果集合

• ToSlice() []interface{}：返回当前集合的切片对象。

3、源码解析

由上文可知，golang-set提供了普通和线程安全两种类型的集合对象。其中线程安全的集合对象，通过结构嵌套的方式为普通集合对象新增了一个全局锁，实现了线程安全。因此针对方法的实现主要通过普通集合对象的实现来介绍。

golang-set包的具体实现其实非常简单，基于golang-set原生的map结构作为基本的存储结构，value以一个不占用内存空间的struct{}{}为值。其中一个我认为值得我们借鉴的开发技巧就是golang-set的遍历方法，具体源码如下所示：

func (set *threadUnsafeSet) Iter() <-chan interface{} {
    ch := make(chan interface{})
    go func() {
        for elem := range *set {
            ch <- elem
        }
        close(ch)
    }()

    return ch
}

它通过创建一个协程去遍历set对象，同时返回一个channel 由用户去读取set的遍历结果，是的读取较大set对象时，用户无需等待，而直接读取，具有较高的效率，但是他的缺点也十分明显，那就是这个方式无法中途退出，也就是说，在使用该方法遍历时，用户必须保证会执行完全部的遍历结果。否则，由于返回的channel是无缓冲的channel,用户不读取时，Iterator()方法中的遍历协程将阻塞，而无法退出，就会发生内存泄漏，具体案例参考goleng-set错误使用导致的内存泄漏。

为了方便遍历方法的中途退出，golang-set又提供了另外一个遍历方法，通过返回一个美枚举对象来实现set对象的异步遍历。具体源码如下：

type Iterator struct {
    C    <-chan interface{}
    stop chan struct{}
}

func newIterator() (*Iterator, chan<- interface{}, <-chan struct{}) {
    itemChan := make(chan interface{})
    stopChan := make(chan struct{})
    return &Iterator{
        C:    itemChan,
        stop: stopChan,
    }, itemChan, stopChan
}


func (set *threadUnsafeSet) Iterator() *Iterator {
    iterator, ch, stopCh := newIterator()

    go func() {
    L:
        for elem := range *set {
            select {
            case <-stopCh:
                break L
            case ch <- elem:
            }
        }
        close(ch)
    }()

    return iterator
}

其中枚举对象Iterator中的C channel用于异步读取遍历结果，stop channel用于主动停止遍历协程，从而避免内存泄漏。具体的使用方法如下：

it := a.Iterator()

for v := range it.C {
    //退出条件
    if (v == 10){
        it.stop()
    }
}