Go 中 Set 的实现方案，你会吗？

Go 的设计是一种简单哲学，

它摒弃了其他语言一些臃肿的功能和模块，以降低程序员的学习门槛，减少使用中的心智负担。

本文，我们来探讨 Go 中缺失的数据结构：Set，以及它的最佳实现方案。

Set 语义与实现方案

Set 集合是其他语言中常见的数据结构。特性：集合中的对象不按特定的方式排序，并且没有重复对象。

学习 Go ，要记住：Go 没有包含的东西，不代表 Go 真的没有。根据 Set 特性，我们可以很轻松地想到使用 map 的实现方案(因为 map 的 key 是不重复的)：把对象当做 key 存入 map。

使用 map 来实现 Set，意味着我们只关心 key 的存在，其 value 值并不重要。有其他语言编程经验的人也许会选择 bool 来作为 value，因为它是其它语言中内存消耗最少的类型(1个字节)。但是在 Go 中，还有另一种选择：struct{}。

1. fmt.Println(unsafe.Sizeof(struct {}{})) // output: 0 

压测对比

为了探究哪种数据结构是作为 value 的最佳选择。我们选择了以下常用的类型作为 value 进行测试：bool、int、interface{}、struct{}。

1. package main 
2.  
3. import ( 
4.  "testing" 
5. ) 
6.  
7. const num = int(1 << 24) 
8.  
9. // 测试 bool 类型 
10. func Benchmark_SetWithBoolValueWrite(b *testing.B) { 
11.  set := make(map[int]bool) 
12.  for i := 0; i < num; i++ { 
13.   set[i] = true 
14.  } 
15. } 
16.  
17. // 测试 interface{} 类型 
18. func Benchmark_SetWithInterfaceValueWrite(b *testing.B) { 
19.  set := make(map[int]interface{}) 
20.  for i := 0; i < num; i++ { 
21.   set[i] = struct{}{} 
22.  } 
23. } 
24.  
25. // 测试 int 类型 
26. func Benchmark_SetWithIntValueWrite(b *testing.B) { 
27.  set := make(map[int]int) 
28.  for i := 0; i < num; i++ { 
29.   set[i] = 0 
30.  } 
31. } 
32.  
33. // 测试 struct{} 类型 
34. func Benchmark_SetWithStructValueWrite(b *testing.B) { 
35.  set := make(map[int]struct{}) 
36.  for i := 0; i < num; i++ { 
37.   set[i] = struct{}{} 
38.  } 
39. } 

我们运行以下命令，进行测试

1. $ go test -v -bench=. -count=3 -benchmem | tee result.txt 
2. goos: darwin 
3. goarch: amd64 
4. pkg: workspace/example/demoForSet 
5. cpu: Intel(R) Core(TM) i5-8279U CPU @ 2.40GHz 
6. Benchmark_SetWithBoolValueWrite 
7. Benchmark_SetWithBoolValueWrite-8                1 3549312568 ns/op 883610264 B/op   614311 allocs/op 
8. Benchmark_SetWithBoolValueWrite-8                1 3288521519 ns/op 883599440 B/op   614206 allocs/op 
9. Benchmark_SetWithBoolValueWrite-8                1 3264097496 ns/op 883578624 B/op   614003 allocs/op 
10. Benchmark_SetWithInterfaceValueWrite 
11. Benchmark_SetWithInterfaceValueWrite-8           1 4397757645 ns/op 1981619632 B/op   614062 allocs/op 
12. Benchmark_SetWithInterfaceValueWrite-8           1 4088301215 ns/op 1981553392 B/op   613743 allocs/op 
13. Benchmark_SetWithInterfaceValueWrite-8           1 3990698218 ns/op 1981560880 B/op   613773 allocs/op 
14. Benchmark_SetWithIntValueWrite 
15. Benchmark_SetWithIntValueWrite-8                 1 3472910194 ns/op 1412326480 B/op   615131 allocs/op 
16. Benchmark_SetWithIntValueWrite-8                 1 3519755137 ns/op 1412187928 B/op   614294 allocs/op 
17. Benchmark_SetWithIntValueWrite-8                 1 3459182691 ns/op 1412057672 B/op   613390 allocs/op 
18. Benchmark_SetWithStructValueWrite 
19. Benchmark_SetWithStructValueWrite-8              1 3126746088 ns/op 802452368 B/op   614127 allocs/op 
20. Benchmark_SetWithStructValueWrite-8              1 3161650835 ns/op 802431240 B/op   613632 allocs/op 
21. Benchmark_SetWithStructValueWrite-8              1 3160410871 ns/op 802440552 B/op   613748 allocs/op 
22. PASS 
23. ok   workspace/example/demoForSet 42.660s 

此时的结果看起来不太直观，这里推荐一个 benchmark 统计工具：Benchstat。通过以下命令进行安装

1. $ go get -u golang.org/x/perf/cmd/benchstat 

使用 benchstat 分析刚才得到的 benchmark 结果文件

1. $ benchstat result.txt 
2. name                           time/op 
3. _SetWithBoolValueWrite-8        3.37s ± 5% 
4. _SetWithInterfaceValueWrite-8   4.16s ± 6% 
5. _SetWithIntValueWrite-8         3.48s ± 1% 
6. _SetWithStructValueWrite-8      3.15s ± 1% 
7.  
8. name                           alloc/op 
9. _SetWithBoolValueWrite-8        884MB ± 0% 
10. _SetWithInterfaceValueWrite-8  1.98GB ± 0% 
11. _SetWithIntValueWrite-8        1.41GB ± 0% 
12. _SetWithStructValueWrite-8      802MB ± 0% 
13.  
14. name                           allocs/op 
15. _SetWithBoolValueWrite-8         614k ± 0% 
16. _SetWithInterfaceValueWrite-8    614k ± 0% 
17. _SetWithIntValueWrite-8          614k ± 0% 
18. _SetWithStructValueWrite-8       614k ± 0% 

从内存开销而言，struct{} 是最小的，反映在执行时间上也是最少的。由于 bool 类型仅占一个字节，它相较于空结构而言，相差的并不多。但是，如果使用 interface{} 类型，那差距就很明显了。

所以，毫无疑问，在 Set 的实现中， map 值类型应该选 struct{}。

总结

本文虽然讨论的是 Set 的实现方案，但本质是涉及空结构体 struct{}{} 的 零内存特性。

空结构体除了是实现 Set 的 value 值最佳方案，它还可以应用于以下方面：

• 通知信号的 channel：当 channel 只用于通知 goroutine 的执行事件，此时 channel 就不需要发送任何实质性的数据，选择使用 chan struct{} 。
• 没有状态数据的结构体：当对象只拥有方法，而不包含任何的属性字段时，选择使用空结构体定义该对象。

原文链接：https://mp.weixin.qq.com/s/pcwCW7jtr2_CJ_k58He-6Q