Go实现低性能集合Set_Golang

前言

从去年校招入职至今，Java转Go已经有大半年了，在开发过程中发现Go还是有一些痛点的，它的基本数据结构主要是数组、切片、Map，像我们常用到的集合Set其实是没有的，需要自己实现一套。Set表示一个集合，Set里的元素不能重复，实现方式有：

利用Map的Key是唯一的来实现直接用别人写好的Set，比较成熟的包是https://github.com/deckarep/golang-set

作为一名Bytedancer，当然要享受造轮子的过程，那么现在我们来自己动手写实现一个Set

线程不安全Set实现

我目前使用的是Go 1.16版本，还不支持范型，由于开发中常用string这一基本类型，那么我们就以string为例造一个存string的集合～

首先构造存String的Set

package hashset

type StringSet map[string]struct{}

func NewStringSet() StringSet {
   return make(map[string]struct{})
}

新增元素

func (set StringSet) Add(element string) string {
   set[element] = struct{}{}
   return element
}

把元素塞到Map里的Key中，Value是什么我们不关心

删除元素

func (set StringSet) Remove(element string) string {
   delete(set, element)
   return element
}

调用Go语言提供的一个内置函数 delete()，用于删除Map内键值对

判断一个元素是否存在Set中

func (set StringSet) Contain(element string) bool {
   if _, ok := set[element]; ok {
      return true
   }
   return false
}

这个没啥好说的，利用Map的属性，查看Map中是否存在以element为Key的元素

计算Set中的所有元素

func (set StringSet) Length() int {
   return len(set)
}

这个也没啥好说的，用内置函数len()就可以解决

UT验证

package hashset

import (
   "fmt"
   "testing"
)

func TestAdd(t *testing.T) {
   set := NewStringSet()
   addElem := set.Add("hello")
   fmt.Printf("add element = %v \n", addElem)
   fmt.Printf("set is %v \n", set)
}

func TestRemove(t *testing.T) {
   set := NewStringSet()
   addElem := set.Add("hello")
   fmt.Printf("add element = %v \n", addElem)
   fmt.Printf("set is %v \n", set)

   removeElem := set.Remove("hello")
   fmt.Printf("remove element = %v \n", removeElem)
   fmt.Printf("set is %v \n", set)
}

func TestContain(t *testing.T) {
   set := NewStringSet()
   addElem := set.Add("hello")
   fmt.Printf("add element = %v \n", addElem)
   fmt.Printf("set is %v \n", set)

   contain := set.Contain("hello")
   fmt.Printf("contain hello element ? %v \n", contain)
   contain = set.Contain("hello golang")
   fmt.Printf("contain hello golang element ? %v \n", contain)

}

func TestLength(t *testing.T) {
   set := NewStringSet()
   set.Add("hello")
   set.Add("hello2")
   set.Add("hello2")
   set.Add("hello3")
   fmt.Printf("set element length is %v \n", set.Length())
}

看起来一切都很美好，但美好的前提却是在单线程的情况下的，那么如果是多线程的情况下，会不会出现线程安全呢？写个UT看看就知道了

func TestConcurrentAdd(t *testing.T) {
   set := NewStringSet()
   for i := 0; i < 100; i++ {
      elem := fmt.Sprintf("%v", i)
      go set.Add(elem)
   }
}

这里开启了100个go协程去给Set添加元素，跑一波就直接panic了

错误信息就是fatal error: concurrent map writes

可见我们实现的这个Set，是基于非线程安全的Map上的，所以这自然是一个非线程安全的Set。

线程安全Set实现首先构造存String的Set

import "sync"

type SyncStringSet struct {
   m map[string]struct{}
   sync.RWMutex
}

func NewSyncStringSet() *SyncStringSet {
   return &SyncStringSet{
      m: map[string]struct{}{},
   }
}

这里采用了sync包下的RWMutex读写锁来解决并发问题，后续每一个对Map的 *** 作都需要在修改元素前加锁，完成 *** 作后需要释放锁

新增元素

func (set *SyncStringSet) Add(element string) string {
   set.Lock()
   defer set.Unlock()
   set.m[element] = struct{}{}
   return element
}

删除元素

func (set *SyncStringSet) Remove(element string) string {
   set.Lock()
   defer set.Unlock()
   delete(set.m, element)
   return element
}

判断一个元素是否存在Set中

func (set *SyncStringSet) Contain(element string) bool {
   set.Lock()
   defer set.Unlock()
   if _, ok := set.m[element]; ok {
      return true
   }
   return false
}

计算Set中的所有元素

func (set *SyncStringSet) Length() int {
   set.Lock()
   defer set.Unlock()
   return len(set.m)
}

UT验证

package hashset

import (
   "fmt"
   "testing"
)

func TestSyncAdd(t *testing.T) {
   set := NewSyncStringSet()
   for i := 0; i < 100; i++ {
      elem := fmt.Sprintf("%v", i)
      go set.Add(elem)
   }
}

func TestSyncRemove(t *testing.T) {
   set := NewSyncStringSet()
   for i := 0; i < 100; i++ {
      elem := fmt.Sprintf("%v", i)
      go set.Add(elem)
   }

   for i := 0; i < 100; i++ {
      elem := fmt.Sprintf("%v", i)
      go set.Remove(elem)
   }
}

func TestSyncContain(t *testing.T) {
   set := NewSyncStringSet()
   for i := 0; i < 100; i++ {
      elem := fmt.Sprintf("%v", i)
      go set.Add(elem)
   }

   for i := 0; i < 100; i++ {
      elem := fmt.Sprintf("%v", i)
      go set.Contain(elem)
   }
}

func TestSyncLength(t *testing.T) {
   set := NewSyncStringSet()
   for i := 0; i < 100; i++ {
      elem := fmt.Sprintf("%v", i)
      go set.Add(elem)
      go set.Length()
   }
}