前言
从去年校招入职至今，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() } }
UT全部跑过，不会出现并发问题了。
总结
造一个低性能的Set就只需要两步：
- 知道Map的使用
- 解决并发问题可以采用sync包下的RWMutex
