本篇主要講述如何利用Go語言的語法特性實現Set類型的數據結構。
需求
對于Set類型的數據結構，其實本質上跟List沒什么多大的區別。無非是Set不能含有重復的Item的特性，Set有初始化、Add、Clear、Remove、Contains等操作。接下來看具體的實現方式分析吧。
實現
仍然按照已有的編程經驗來聯想如何實現基本Set功能，在Java中很容易知道HashSet的底層實現是HashMap，核心的就是用一個常量來填充Map鍵值對中的Value選項。除此之外，重點關注Go中Map的數據結構，Key是不允許重復的，如下所示：
|
1
2
3
4
5
6
7
|
m := map[string]string{ "1": "one", "2": "two", "1": "one", "3": "three", } fmt.Println(m) |
程序會直接報錯，提示重復Key值，這樣就非常符合Set的特性需求了。
定義
前面分析出Set的Value為固定的值，用一個常量替代即可。但是筆者分析的實現源碼，用的是一個空結構體來實現的，如下所示：
|
1
2
3
4
5
6
7
|
// 空結構體var Exists = struct{}{}// Set is the main interfacetype Set struct { // struct為結構體類型的變量 m map[interface{}]struct{}} |
為了解決上面為什么用空結構體來做常量Value，先看下面的是測試：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
import ( "fmt" "unsafe")// 定義非空結構體type S struct { a uint16 b uint32}func main() { var s S fmt.Println(unsafe.Sizeof(s)) // prints 8, not 6 var s2 struct{} fmt.Println(unsafe.Sizeof(s2)) // prints 0} |
打印出空結構體變量的內存占用大小為0，再看看下面這個測試：
|
1
2
3
4
|
a := struct{}{}b := struct{}{}fmt.Println(a == b) // truefmt.Printf("%p, %p\n", &a, &b) // 0x55a988, 0x55a988 |
很有趣，a和b竟然相等，并且a和b的地址也是一樣的。現在各位應該明白了為什么會有：
|
1
|
var Exists = struct{}{} |
這樣的常量也來填充所有Map的Value了吧，Go真是精彩！！！
初始化
Set類型數據結構的初始化操作，在聲明的同時可以選擇傳入或者不傳入進去。聲明Map切片的時候，Key可以為任意類型的數據，用空接口來實現即可。Value的話按照上面的分析，用空結構體即可：
|
1
2
3
4
5
6
7
8
|
func New(items ...interface{}) *Set { // 獲取Set的地址 s := &Set{} // 聲明map類型的數據結構 s.m = make(map[interface{}]struct{}) s.Add(items...) return s} |
添加
簡化操作可以添加不定個數的元素進入到Set中，用變長參數的特性來實現這個需求即可，因為Map不允許Key值相同，所以不必有排重操作。同時將Value數值指定為空結構體類型。
|
1
2
3
4
5
6
|
func (s *Set) Add(items ...interface{}) error { for _, item := range items { s.m[item] = Exists } return nil} |
包含
Contains操作其實就是查詢操作，看看有沒有對應的Item存在，可以利用Map的特性來實現，但是由于不需要Value的數值，所以可以用 _,ok來達到目的：
|
1
2
3
4
|
func (s *Set) Contains(item interface{}) bool { _, ok := s.m[item] return ok} |
長度和清除
獲取Set長度很簡單，只需要獲取底層實現的Map的長度即可：
|
1
2
3
|
func (s *Set) Size() int { return len(s.m)} |
清除操作的話，可以通過重新初始化Set來實現，如下即為實現過程：
|
1
2
3
|
func (s *Set) Clear() { s.m = make(map[interface{}]struct{})} |
相等
判斷兩個Set是否相等，可以通過循環遍歷來實現，即將A中的每一個元素，查詢在B中是否存在，只要有一個不存在，A和B就不相等，實現方式如下所示：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
func (s *Set) Equal(other *Set) bool { // 如果兩者Size不相等，就不用比較了 if s.Size() != other.Size() { return false } // 迭代查詢遍歷 for key := range s.m { // 只要有一個不存在就返回false if !other.Contains(key) { return false } } return true} |
子集
判斷A是不是B的子集，也是循環遍歷的過程，具體分析在上面已經講述過，實現方式如下所示：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
func (s *Set) IsSubset(other *Set) bool { // s的size長于other，不用說了 if s.Size() > other.Size() { return false } // 迭代遍歷 for key := range s.m { if !other.Contains(key) { return false } } return true} |
Ok，以上就是Go中Set的主要函數實現方式，還是很有意思的。繼續加油。也希望大家多多支持服務器之家。
原文鏈接：https://allenwu.itscoder.com/set-in-go
