本篇主要講述如何利用Go語言的語法特性實現(xiàn)Set類型的數(shù)據(jù)結(jié)構(gòu)。
需求
對于Set類型的數(shù)據(jù)結(jié)構(gòu)，其實本質(zhì)上跟List沒什么多大的區(qū)別。無非是Set不能含有重復(fù)的Item的特性，Set有初始化、Add、Clear、Remove、Contains等操作。接下來看具體的實現(xiàn)方式分析吧。
實現(xiàn)
仍然按照已有的編程經(jīng)驗來聯(lián)想如何實現(xiàn)基本Set功能，在Java中很容易知道HashSet的底層實現(xiàn)是HashMap，核心的就是用一個常量來填充Map鍵值對中的Value選項。除此之外，重點關(guān)注Go中Map的數(shù)據(jù)結(jié)構(gòu)，Key是不允許重復(fù)的，如下所示：
m := map[string]string{
"1": "one",
"2": "two",
"1": "one",
"3": "three",
}
fmt.Println(m)
程序會直接報錯，提示重復(fù)Key值，這樣就非常符合Set的特性需求了。
定義
前面分析出Set的Value為固定的值，用一個常量替代即可。但是筆者分析的實現(xiàn)源碼，用的是一個空結(jié)構(gòu)體來實現(xiàn)的，如下所示：
// 空結(jié)構(gòu)體
var Exists = struct{}{}
// Set is the main interface
type Set struct {
// struct為結(jié)構(gòu)體類型的變量
m map[interface{}]struct{}
}
為了解決上面為什么用空結(jié)構(gòu)體來做常量Value，先看下面的是測試：
import (
"fmt"
"unsafe"
)
// 定義非空結(jié)構(gòu)體
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
}
打印出空結(jié)構(gòu)體變量的內(nèi)存占用大小為0，再看看下面這個測試：
a := struct{}{}
b := struct{}{}
fmt.Println(a == b) // true
fmt.Printf("%p, %p\n", a, b) // 0x55a988, 0x55a988
很有趣，a和b竟然相等，并且a和b的地址也是一樣的。現(xiàn)在各位應(yīng)該明白了為什么會有：
這樣的常量也來填充所有Map的Value了吧，Go真是精彩?。?！
初始化
Set類型數(shù)據(jù)結(jié)構(gòu)的初始化操作，在聲明的同時可以選擇傳入或者不傳入進去。聲明Map切片的時候，Key可以為任意類型的數(shù)據(jù)，用空接口來實現(xiàn)即可。Value的話按照上面的分析，用空結(jié)構(gòu)體即可：
func New(items ...interface{}) *Set {
// 獲取Set的地址
s := Set{}
// 聲明map類型的數(shù)據(jù)結(jié)構(gòu)
s.m = make(map[interface{}]struct{})
s.Add(items...)
return s
}
添加
簡化操作可以添加不定個數(shù)的元素進入到Set中，用變長參數(shù)的特性來實現(xiàn)這個需求即可，因為Map不允許Key值相同，所以不必有排重操作。同時將Value數(shù)值指定為空結(jié)構(gòu)體類型。
func (s *Set) Add(items ...interface{}) error {
for _, item := range items {
s.m[item] = Exists
}
return nil
}
包含
Contains操作其實就是查詢操作，看看有沒有對應(yīng)的Item存在，可以利用Map的特性來實現(xiàn)，但是由于不需要Value的數(shù)值，所以可以用 _,ok來達到目的：
func (s *Set) Contains(item interface{}) bool {
_, ok := s.m[item]
return ok
}
長度和清除
獲取Set長度很簡單，只需要獲取底層實現(xiàn)的Map的長度即可：
func (s *Set) Size() int {
return len(s.m)
}
清除操作的話，可以通過重新初始化Set來實現(xiàn)，如下即為實現(xiàn)過程：
func (s *Set) Clear() {
s.m = make(map[interface{}]struct{})
}
相等
判斷兩個Set是否相等，可以通過循環(huán)遍歷來實現(xiàn)，即將A中的每一個元素，查詢在B中是否存在，只要有一個不存在，A和B就不相等，實現(xiàn)方式如下所示：
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的子集，也是循環(huán)遍歷的過程，具體分析在上面已經(jīng)講述過，實現(xiàn)方式如下所示：
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的主要函數(shù)實現(xiàn)方式，還是很有意思的。繼續(xù)加油。也希望大家多多支持腳本之家。
您可能感興趣的文章:- Go語言中的Array、Slice、Map和Set使用詳解
