前言

本篇主要給大家講述了如何利用Go語(yǔ)言的語(yǔ)法特性實(shí)現(xiàn)Set類型的數(shù)據(jù)結(jié)構(gòu)，分享出來(lái)供大家參考學(xué)習(xí)，話不多說(shuō)了，來(lái)一起看看詳細(xì)的介紹吧。

需求

對(duì)于Set類型的數(shù)據(jù)結(jié)構(gòu)，其實(shí)本質(zhì)上跟List沒(méi)什么多大的區(qū)別。無(wú)非是Set不能含有重復(fù)的Item的特性，Set有初始化、Add、Clear、Remove、Contains等操作。接下來(lái)看具體的實(shí)現(xiàn)方式分析吧。

實(shí)現(xiàn)

仍然按照已有的編程經(jīng)驗(yàn)來(lái)聯(lián)想如何實(shí)現(xiàn)基本Set功能，在Java中很容易知道HashSet的底層實(shí)現(xiàn)是HashMap，核心的就是用一個(gè)常量來(lái)填充Map鍵值對(duì)中的Value選項(xiàng)。除此之外，重點(diǎn)關(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)

程序會(huì)直接報(bào)錯(cuò)，提示重復(fù)Key值，這樣就非常符合Set的特性需求了。

定義

前面分析出Set的Value為固定的值，用一個(gè)常量替代即可。但是筆者分析的實(shí)現(xiàn)源碼，用的是一個(gè)空結(jié)構(gòu)體來(lái)實(shí)現(xiàn)的，如下所示：

// 空結(jié)構(gòu)體var Exists = struct{}{}// Set is the main interfacetype Set struct { // struct為結(jié)構(gòu)體類型的變量 m map[interface{}]struct{}}

為了解決上面為什么用空結(jié)構(gòu)體來(lái)做常量Value，先看下面的是測(cè)試：

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，再看看下面這個(gè)測(cè)試：

a := struct{}{}b := struct{}{}fmt.Println(a == b) // truefmt.Printf("%p, %p/n", &a, &b) // 0x55a988, 0x55a988

很有趣，a和b竟然相等，并且a和b的地址也是一樣的。現(xiàn)在各位應(yīng)該明白了為什么會(huì)有：

var Exists = struct{}{}

這樣的常量也來(lái)填充所有Map的Value了吧，Go真是精彩！！！

初始化

Set類型數(shù)據(jù)結(jié)構(gòu)的初始化操作，在聲明的同時(shí)可以選擇傳入或者不傳入進(jìn)去。聲明Map切片的時(shí)候，Key可以為任意類型的數(shù)據(jù)，用空接口來(lái)實(shí)現(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}

添加

簡(jiǎn)化操作可以添加不定個(gè)數(shù)的元素進(jìn)入到Set中，用變長(zhǎng)參數(shù)的特性來(lái)實(shí)現(xiàn)這個(gè)需求即可，因?yàn)镸ap不允許Key值相同，所以不必有排重操作。同時(shí)將Value數(shù)值指定為空結(jié)構(gòu)體類型。

func (s *Set) Add(items ...interface{}) error { for _, item := range items { s.m[item] = Exists } return nil}

包含

Contains操作其實(shí)就是查詢操作，看看有沒(méi)有對(duì)應(yīng)的Item存在，可以利用Map的特性來(lái)實(shí)現(xiàn)，但是由于不需要Value的數(shù)值，所以可以用 _,ok來(lái)達(dá)到目的：

func (s *Set) Contains(item interface{}) bool { _, ok := s.m[item] return ok}

長(zhǎng)度和清除

獲取Set長(zhǎng)度很簡(jiǎn)單，只需要獲取底層實(shí)現(xiàn)的Map的長(zhǎng)度即可：

func (s *Set) Size() int { return len(s.m)}

清除操作的話，可以通過(guò)重新初始化Set來(lái)實(shí)現(xiàn)，如下即為實(shí)現(xiàn)過(guò)程：

func (s *Set) Clear() { s.m = make(map[interface{}]struct{})}

相等

判斷兩個(gè)Set是否相等，可以通過(guò)循環(huán)遍歷來(lái)實(shí)現(xiàn)，即將A中的每一個(gè)元素，查詢?cè)贐中是否存在，只要有一個(gè)不存在，A和B就不相等，實(shí)現(xiàn)方式如下所示：

func (s *Set) Equal(other *Set) bool { // 如果兩者Size不相等，就不用比較了 if s.Size() != other.Size() { return false }  // 迭代查詢遍歷 for key := range s.m {  // 只要有一個(gè)不存在就返回false if !other.Contains(key) { return false } } return true}

子集

判斷A是不是B的子集，也是循環(huán)遍歷的過(guò)程，具體分析在上面已經(jīng)講述過(guò)，實(shí)現(xiàn)方式如下所示：

func (s *Set) IsSubset(other *Set) bool { // s的size長(zhǎng)于other，不用說(shuō)了 if s.Size() > other.Size() { return false } // 迭代遍歷 for key := range s.m { if !other.Contains(key) { return false } } return true}

Ok，以上就是Go中Set的主要函數(shù)實(shí)現(xiàn)方式，還是很有意思的。繼續(xù)加油。

總結(jié)

以上就是這篇文章的全部?jī)?nèi)容了，希望本文的內(nèi)容對(duì)大家的學(xué)習(xí)或者工作能帶來(lái)一定的幫助，如果有疑問(wèn)大家可以留言交流，謝謝大家對(duì)VEVB武林網(wǎng)的支持。