Golang实现set

背景

Golang语言本身未实现set，但是实现了map
golang的map是一种无序的键值对的集合，其中键是唯一的
而set是键的不重复的集合，因此可以用map来实现set
Empty

由于map是key-value集合，如果使用map来实现set，则不需要关注value的具体类型和值
struct{}是具有零个元素的struct，struct{}的大小为0，不占用空间，因此十分适合作为value使用

1. type Empty struct{}

复制代码

Int64HashSet

Golang是静态强类型语言，对于int8、uint8、int64、uint64、 string基础数据类型的set，均需要实现类似的代码
定义

1. type Int8HashSet map[int8]Empty
2. type UintHashSet map[uint8]Empty
3. type Int64HashSet map[int64]Empty
4. type Uint64HashSet map[uint64]Empty
5. type Int64HashSet map[string]Empty　　

复制代码

以int64为例，实现set的基本操作
初始化

1. func NewInt64HashSet(cap ...int) Int64HashSet {
2.         var set Int64HashSet
3.         if len(cap) == 0 {
4.                 set = make(Int64HashSet)
5.         } else {
6.                 set = make(Int64HashSet, cap[0])
7.         }
8.         return set
9. }

复制代码

插入

1. func (set Int64HashSet) Insert(items ...int64) {
2.         for _, item := range items {
3.                 set[item] = Empty{}
4.         }
5. }

复制代码

删除

1. func (set Int64HashSet) Delete(items ...int64) {
2.         for _, item := range items {
3.                 delete(set, item)
4.         }
5. }

复制代码

列表

1. func (set Int64HashSet) List() []int64 {
2.         list := make([]int64, 0, len(set))
3.         for item := range set {
4.                 list = append(list, item)
5.         }
6.         return list
7. }

复制代码

弊端

采用上面的方法实现，会充斥着大量重复代码，对于其它类型如int8，uint8，string等类型，需要单独实现，尽管逻辑基本一致。
在Go 1.18版本之前，我们可以使用反射来避免这个问题，
使用反射在运行时推断具体的类型，虽然有性能上的损耗，但是单次纳秒级别的操作，基本可以忽略不计。
HashSet

interface{}是没有方法的空接口，所有类型都实现了空接口
通过反射可以从interface获取对象的值和类型
定义

1. type HashSet map[interface{}]Empty

复制代码

初始化

1. func NewHashSet(cap ...int) HashSet {
2.         var set HashSet
3.         if len(cap) == 0 {
4.                 set = make(HashSet)
5.         } else {
6.                 set = make(HashSet, cap[0])
7.         }
8.         return set
9. }

复制代码

插入

1. func (set HashSet) Insert(items ...interface{}) {
2.         for _, item := range items {
3.                 set[item] = Empty{}
4.         }
5. }

复制代码

删除

1. func (set HashSet) Delete(items ...interface{}) {
2.         for _, item := range items {
3.                 delete(set, item)
4.         }
5. }

复制代码

列表

1. // 通过反射获取到具体的类型
2. // 可以将int64替换为其它类型，如uint8, string等
3. func (set HashSet) ListInt64() []int64 {
4.         list := make([]int64, 0, len(set))
5.         for item := range set {
6.                 if val, ok := item.(int64); ok {
7.                         list = append(list, val)
8.                 }
9.         }
10.         return list
11. }
13. func (set HashSet) ListString() []string {
14.         list := make([]string, 0, len(set))
15.         for item := range set {
16.                 if val, ok := item.(string); ok {
17.                         list = append(list, val)
18.                 }
19.         }
20.         return list
21. }

复制代码

GenericHashSet

反射在编译时缺少类型检查，比如对于同一个set，先后插入int类型和string类型数据，在编译和运行阶段均不会报错。

1. hash := NewHashSet(8)
2. // 插入int类型
3. hash.Insert(111)
4. // 插入string类型
5. hash.Insert("string")

复制代码

使用反射在一定程度上避免了大量的重复代码，但是将set转换为slice还是会存在重复的相似逻辑的代码
并且需要在运行时获取/判断对象的类型和值，存在一定的性能损耗
在Go 1.18版本提供了范型（Generics）的支持，
范型可以在编译期间进行类型检查和类型推断，相对于反射机制而言，性能有所提升
定义

1. type GenericHashSet[T comparable] map[T]Empty

复制代码

初始化

1. func NewGenericHashSet[T comparable](cap ...int) *GenericHashSet[T] {
2.         var set GenericHashSet[T]
3.         if len(cap) == 0 {
4.                 set = make(GenericHashSet[T])
5.         } else {
6.                 set = make(GenericHashSet[T], cap[0])
7.         }
8.         return &set
9. }

复制代码

插入

1. func (set *GenericHashSet[T]) Insert(items ...T) {
2.         for _, item := range items {
3.                 (*set)[item] = Empty{}
4.         }
5. }

复制代码

删除

1. func (set *GenericHashSet[T]) Delete(items ...T) {
2.         for _, item := range items {
3.                 delete(*set, item)
4.         }
5. }

复制代码

列表

1. func (set *GenericHashSet[T]) List() []T {
2.         list := make([]T, 0, len(*set))
3.         for item := range *set {
4.                 list = append(list, item)
5.         }
6.         return list
7. }

复制代码

性能对比

插入操作测试代码

1. func BenchmarkInt64HashSetInsert(b *testing.B) {
2.         intHashSet := NewInt64HashSet()
3.         rand.Seed(time.Now().UnixNano())
4.         for i := 0; i < b.N; i++ {
5.                 intHashSet.Insert(rand.Int63())
6.         }
7. }
9. func BenchmarkGenericHashSetInsert(b *testing.B) {
10.         gHashSet := NewGenericHashSet[int64]()
11.         rand.Seed(time.Now().UnixNano())
12.         for i := 0; i < b.N; i++ {
13.                 gHashSet.Insert(rand.Int63())
14.         }
15. }
17. func BenchmarkHashSetInsert(b *testing.B) {
18.         hashSet := NewHashSet()
19.         rand.Seed(time.Now().UnixNano())
20.         for i := 0; i < b.N; i++ {
21.                 hashSet.Insert(rand.Int63())
22.         }
23. }

复制代码

 插入操作测试结果

1. zbwdeAir:set zbw$ go test -bench="BenchmarkInt64HashSetInsert|BenchmarkGenericHashSetInsert|BenchmarkHashSetInsert" -benchmem
2. goos: darwin
3. goarch: arm64
4. pkg: set/set
5. BenchmarkInt64HashSetInsert-8           10051916               119.2 ns/op            40 B/op          0 allocs/op
6. BenchmarkGenericHashSetInsert-8         13957741               123.7 ns/op            57 B/op          0 allocs/op
7. BenchmarkHashSetInsert-8                 6526810               188.9 ns/op            63 B/op          1 allocs/op
8. PASS
9. ok      set/set 4.897s

复制代码

可以看出来，Int64HashSet性能最优，GenericHashSet次之，HashSet性能最差。
从实际使用角度看
对于Go < 1.18版本，使用HashSet即可。如果追求性能的极致，不介意大量重复代码，那还是使用Int64HashSet
对于单次操作的时间在ns级别，对于大部分业务场景，反射带来的性能损耗基本可以忽略，性能的瓶颈并不在这里。
对于Go >= 1.18版本，可以使用GenericHashSet
其它

如果需要实现有序set，则需要链表辅助实现
详细代码，见github


如果你觉得还可以，点一下Star
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！