需求


對于Set類型的數據結構,其實本質上跟List沒什么多大的區別。無非是Set不能含有重復的Item的" />

詳解Go中Set的實現方式

 更新時間:2020-01-15 16:01:56   作者:佚名   我要評論(0)

本篇主要講述如何利用Go語言的語法特性實現Set類型的數據結構。
需求


對于Set類型的數據結構,其實本質上跟List沒什么多大的區別。無非是Set不能含有重復的Item的

本篇主要講述如何利用Go語言的語法特性實現Set類型的數據結構。

需求

對于Set類型的數據結構,其實本質上跟List沒什么多大的區別。無非是Set不能含有重復的Item的特性,Set有初始化、Add、Clear、Remove、Contains等操作。接下來看具體的實現方式分析吧。

實現

仍然按照已有的編程經驗來聯想如何實現基本Set功能,在Java中很容易知道HashSet的底層實現是HashMap,核心的就是用一個常量來填充Map鍵值對中的Value選項。除此之外,重點關注Go中Map的數據結構,Key是不允許重復的,如下所示:

m := map[string]string{
 "1": "one",
 "2": "two",
 "1": "one",
 "3": "three",
 }
 fmt.Println(m)

程序會直接報錯,提示重復Key值,這樣就非常符合Set的特性需求了。

定義

前面分析出Set的Value為固定的值,用一個常量替代即可。但是筆者分析的實現源碼,用的是一個空結構體來實現的,如下所示:

// 空結構體
var Exists = struct{}{}
// Set is the main interface
type Set struct {
 // struct為結構體類型的變量
 m map[interface{}]struct{}
}

為了解決上面為什么用空結構體來做常量Value,先看下面的是測試:

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,再看看下面這個測試:

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

很有趣,a和b竟然相等,并且a和b的地址也是一樣的。現在各位應該明白了為什么會有:

var Exists = struct{}{}

這樣的常量也來填充所有Map的Value了吧,Go真是精彩!!!

初始化

Set類型數據結構的初始化操作,在聲明的同時可以選擇傳入或者不傳入進去。聲明Map切片的時候,Key可以為任意類型的數據,用空接口來實現即可。Value的話按照上面的分析,用空結構體即可:

func New(items ...interface{}) *Set {
  // 獲取Set的地址
 s := &Set{}
 // 聲明map類型的數據結構
 s.m = make(map[interface{}]struct{})
 s.Add(items...)
 return s
}

添加

簡化操作可以添加不定個數的元素進入到Set中,用變長參數的特性來實現這個需求即可,因為Map不允許Key值相同,所以不必有排重操作。同時將Value數值指定為空結構體類型。

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

包含

Contains操作其實就是查詢操作,看看有沒有對應的Item存在,可以利用Map的特性來實現,但是由于不需要Value的數值,所以可以用 _,ok來達到目的:

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

長度和清除

獲取Set長度很簡單,只需要獲取底層實現的Map的長度即可:

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

清除操作的話,可以通過重新初始化Set來實現,如下即為實現過程:

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

相等

判斷兩個Set是否相等,可以通過循環遍歷來實現,即將A中的每一個元素,查詢在B中是否存在,只要有一個不存在,A和B就不相等,實現方式如下所示:

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的子集,也是循環遍歷的過程,具體分析在上面已經講述過,實現方式如下所示:

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的主要函數實現方式,還是很有意思的。繼續加油。也希望大家多多支持腳本之家。

您可能感興趣的文章:

  • Go語言中的Array、Slice、Map和Set使用詳解

相關文章

  • 詳解Go中Set的實現方式

    詳解Go中Set的實現方式

    本篇主要講述如何利用Go語言的語法特性實現Set類型的數據結構。 需求 對于Set類型的數據結構,其實本質上跟List沒什么多大的區別。無非是Set不能含有重復的Item的
    2020-01-15
  • Go中如何使用set的方法示例

    Go中如何使用set的方法示例

    今天來聊一下 Go 如何使用 set,本文將會涉及 set 和 bitset 兩種數據結構。 Go 的數據結構 Go 內置的數據結構并不多。工作中,我們最常用的兩種數據結構分別是
    2020-01-15
  • ./ 和 sh 的使用區別詳解

    ./ 和 sh 的使用區別詳解

    ./ 和 sh的使用區別 1、使用“./”執行腳本,對應的xxx.sh腳本必須要有執行權限; 2、使用“sh” 執行腳本,對應的xxx.sh沒有執行權限,亦可執行; 3
    2020-01-15
  • win10下如何運行.sh文件的實現步驟

    win10下如何運行.sh文件的實現步驟

    確保您使用至少是Windows10的14316版本。 這種方法只適用于64位版本的Windows 10 今天居然驚奇地發現原來win10的功能簡直強大到沒話說,居然在更新后有一個Linux的子
    2020-01-15
  • Shell腳本之Expect免交互的實現

    Shell腳本之Expect免交互的實現

    Expext概述 Expect是建立在tcl基礎上的一個工具,Expect是用來自動化控制和測試的工具。主要解決shell腳本中不可交互的問題。有助于大規模的系統運維工作。在日常
    2020-01-15
  • Shell腳本實戰之DNS主從同步腳本實例

    Shell腳本實戰之DNS主從同步腳本實例

    DNS主從同步腳本實例 PS:兩個服務器起好后最好兩個服務都重啟一下 主服務器配置 #!/bin/bash #DNS主從同步——主服務器 rpm -q bind if [ $? -ne
    2020-01-15
  • shell之分離解析腳本的實現方法

    shell之分離解析腳本的實現方法

    分離解析腳本 在運行腳本之前,需要VM虛擬機,Centos7,兩臺主機一臺win10 -1 作為廣域網的主機, 一臺win10 -2作為區域網的主機。 之前我的博客有教程 #!/bin/ba
    2020-01-15
  • shell之正向解析腳本的實現方法

    shell之正向解析腳本的實現方法

    正向解析腳本 #!/bin/bash yum install bind -y //安裝解析工具包 //修改主配置文件 sed -i '13s/127.0.0.1/192.168.17.156/' /etc/named.conf //把解析主配
    2020-01-15
  • 淺談用Go構建不可變的數據結構的方法

    淺談用Go構建不可變的數據結構的方法

    共享狀態是比較容易理解和使用的,但是可能產生隱晦以至于很難追蹤的 bugs。尤其是在我們的數據結構只有部分是通過引用傳遞的。切片就是這么一個很好的例子。后續我
    2020-01-15
  • Go 防止 goroutine 泄露的方法

    Go 防止 goroutine 泄露的方法

    概述 Go 的并發模型與其他語言不同,雖說它簡化了并發程序的開發難度,但如果不了解使用方法,常常會遇到 goroutine 泄露的問題。雖然 goroutine 是輕量級的線程,占
    2020-01-15

最新評論

老快3投注技巧