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

今天來聊一下 Go 如何使用 set，本文將會(huì)涉及 set 和 bitset 兩種數(shù)據(jù)結(jié)構(gòu)。

Go 的數(shù)據(jù)結(jié)構(gòu)

Go 內(nèi)置的數(shù)據(jù)結(jié)構(gòu)并不多。工作中，我們最常用的兩種數(shù)據(jù)結(jié)構(gòu)分別是 slice 和 map，即切片和映射。其實(shí)，Go 中也有數(shù)組，切片的底層就是數(shù)組，只不過因?yàn)榍衅拇嬖?，我們平時(shí)很少使用它。

除了 Go 內(nèi)置的數(shù)據(jù)結(jié)構(gòu)，還有一些數(shù)據(jù)結(jié)構(gòu)是由 Go 的官方 container 包提供，如 heap 堆、list 雙向鏈表和ring 回環(huán)鏈表。但今天我們不講它們，這些數(shù)據(jù)結(jié)構(gòu)，對(duì)于熟手來說，看看文檔就會(huì)使用了。

我們今天將來聊的是 set 和 bitset。據(jù)我所知，其他一些語言，比如 Java，是有這兩種數(shù)據(jù)結(jié)構(gòu)。但 Go 當(dāng)前還沒有以任何形式提供。

實(shí)現(xiàn)思路

先來看一篇文章，訪問地址 2 basic set implementations[1] 閱讀。文中介紹了兩種 go 實(shí)現(xiàn) set 的思路， 分別是 map 和 bitset。

有興趣可以讀讀這篇文章，我們接下來具體介紹下。

map

我們知道，map 的 key 肯定是唯一的，而這恰好與 set 的特性一致，天然保證 set 中成員的唯一性。而且通過 map 實(shí)現(xiàn) set，在檢查是否存在某個(gè)元素時(shí)可直接使用 _, ok := m[key] 的語法，效率高。

先來看一個(gè)簡(jiǎn)單的實(shí)現(xiàn)，如下：

set := make(map[string]bool) // New empty set
set["Foo"] = true   // Add
for k := range set {   // Loop
 fmt.Println(k)
}
delete(set, "Foo") // Delete
size := len(set)  // Size
exists := set["Foo"] // Membership

通過創(chuàng)建 map[string]bool 來存儲(chǔ) string 的集合，比較容易理解。但這里還有個(gè)問題，map 的 value 是布爾類型，這會(huì)導(dǎo)致 set 多占一定內(nèi)存空間，而 set 不該有這個(gè)問題。

怎么解決這個(gè)問題？

設(shè)置 value 為空結(jié)構(gòu)體，在 Go 中，空結(jié)構(gòu)體不占任何內(nèi)存。當(dāng)然，如果不確定，也可以來證明下這個(gè)結(jié)論。

unsafe.Sizeof(struct{}{}) // 結(jié)果為 0

優(yōu)化后的代碼，如下：

type void struct{}
var member void

set := make(map[string]void) // New empty set
set["Foo"] = member   // Add
for k := range set {   // Loop
 fmt.Println(k)
}
delete(set, "Foo")  // Delete
size := len(set)  // Size
_, exists := set["Foo"] // Membership

之前在網(wǎng)上看到有人按這個(gè)思路做了封裝，還寫了一篇文章[2]，可以去讀一下。

其實(shí)，github 上已經(jīng)有個(gè)成熟的包，名為 golang-set，它也是采用這個(gè)思路實(shí)現(xiàn)的。訪問地址 golang-set[3]，描述中說 Docker 用的也是它。包中提供了兩種 set 實(shí)現(xiàn)，線程安全的 set 和非線程安全的 set。

演示一個(gè)簡(jiǎn)單的案例。

package main

import (
 "fmt"

 mapset "github.com/deckarep/golang-set"
)

func main() {
 // 默認(rèn)創(chuàng)建的線程安全的，如果無需線程安全
 // 可以使用 NewThreadUnsafeSet 創(chuàng)建，使用方法都是一樣的。
 s1 := mapset.NewSet(1, 2, 3, 4)
 fmt.Println("s1 contains 3: ", s1.Contains(3))
 fmt.Println("s1 contains 5: ", s1.Contains(5))

 // interface 參數(shù)，可以傳遞任意類型
 s1.Add("poloxue")
 fmt.Println("s1 contains poloxue: ", s1.Contains("poloxue"))
 s1.Remove(3)
 fmt.Println("s1 contains 3: ", s1.Contains(3))

 s2 := mapset.NewSet(1, 3, 4, 5)

 // 并集
 fmt.Println(s1.Union(s2))
}

輸出如下：

s1 contains 3:  true
s1 contains 5:  false
s1 contains poloxue:  true
s1 contains 3:  false
Set{4, polxue, 1, 2, 3, 5}

例子中演示了簡(jiǎn)單的使用方式，如果有不明白的，看下源碼，這些數(shù)據(jù)結(jié)構(gòu)的操作方法名都是很常見的，比如交集 Intersect、差集 Difference 等，一看就懂。

bitset

繼續(xù)聊聊 bitset，bitset 中每個(gè)數(shù)子用一個(gè) bit 即能表示，對(duì)于一個(gè) int8 的數(shù)字，我們可以用它表示 8 個(gè)數(shù)字，能幫助我們大大節(jié)省數(shù)據(jù)的存儲(chǔ)空間。

bitset 最常見的應(yīng)用有 bitmap 和 flag，即位圖和標(biāo)志位。這里，我們先嘗試用它表示一些操作的標(biāo)志位。比如某個(gè)場(chǎng)景，我們需要三個(gè) flag 分別表示權(quán)限1、權(quán)限2和權(quán)限3，而且?guī)讉€(gè)權(quán)限可以共存。我們可以分別用三個(gè)常量 F1、F2、F3 表示位 Mask。

示例代碼如下（引用自文章 Bitmasks, bitsets and flags[4]）：

type Bits uint8

const (
 F0 Bits = 1 << iota
 F1
 F2
)

func Set(b, flag Bits) Bits { return b | flag }
func Clear(b, flag Bits) Bits { return b &^ flag }
func Toggle(b, flag Bits) Bits { return b ^ flag }
func Has(b, flag Bits) bool { return b&flag != 0 }

func main() {
 var b Bits
 b = Set(b, F0)
 b = Toggle(b, F2)
 for i, flag := range []Bits{F0, F1, F2} {
  fmt.Println(i, Has(b, flag))
 }
}

例子中，我們本來需要三個(gè)數(shù)才能表示這三個(gè)標(biāo)志，但現(xiàn)在通過一個(gè) uint8 就可以。bitset 的一些操作，如設(shè)置 Set、清除 Clear、切換 Toggle、檢查 Has 通過位運(yùn)算就可以實(shí)現(xiàn)，而且非常高效。

bitset 對(duì)集合操作有著天然的優(yōu)勢(shì)，直接通過位運(yùn)算符便可實(shí)現(xiàn)。比如交集、并集、和差集，示例如下：

• 交集：a & b
• 并集：a | b
• 差集：a & (~b)

底層的語言、庫、框架常會(huì)使用這種方式設(shè)置標(biāo)志位。

以上的例子中只展示了少量數(shù)據(jù)的處理方式，uint8 占 8 bit 空間，只能表示 8 個(gè)數(shù)字。那大數(shù)據(jù)場(chǎng)景能否可以使用這套思路呢？

我們可以把 bitset 和 Go 中的切片結(jié)合起來，重新定義 Bits 類型，如下：

type Bitset struct {
 data []int64
}

但如此也會(huì)產(chǎn)生一些問題，設(shè)置 bit，我們?cè)趺粗浪谀睦锬兀孔屑?xì)想想，這個(gè)位置信息包含兩部分，即保存該 bit 的數(shù)在切片索引位置和該 bit 在數(shù)字中的哪位，分別將它們命名為 index 和 position。那怎么獲取？

index 可以通過整除獲取，比如我們想知道表示 65 的 bit 在切片的哪個(gè) index，通過 65 / 64 即可獲得，如果為了高效，也可以用位運(yùn)算實(shí)現(xiàn)，即用移位替換除法，比如 65 >> 6，6 表示移位偏移，即 2^n = 64 的 n。

postion 是除法的余數(shù)，我們可以通過模運(yùn)算獲得，比如 65 % 64 = 1，同樣為了效率，也有相應(yīng)的位運(yùn)算實(shí)現(xiàn)，比如 65 & 0b00111111，即 65 & 63。

一個(gè)簡(jiǎn)單例子，如下：

package main

import (
 "fmt"
)

const (
 shift = 6
 mask = 0x3f // 即0b00111111
)

type Bitset struct {
 data []int64
}

func NewBitSet(n int) *Bitset {
 // 獲取位置信息
 index := n >> shift

 set := &Bitset{
 data: make([]int64, index+1),
 }

 // 根據(jù) n 設(shè)置 bitset
 set.data[index] |= 1 << uint(n&mask)

 return set
}

func (set *Bitset) Contains(n int) bool {
 // 獲取位置信息
 index := n >> shift
 return set.data[index]&(1<<uint(n&mask)) != 0
}

func main() {
 set := NewBitSet(65)
 fmt.Println("set contains 65", set.Contains(65))
 fmt.Println("set contains 64", set.Contains(64))
}

輸出結(jié)果

set contains 65 true
set contains 64 false

以上的例子功能很簡(jiǎn)單，只是為了演示，只有創(chuàng)建 bitset 和 contains 兩個(gè)功能，其他諸如添加、刪除、不同 bitset 間的交、并、差還沒有實(shí)現(xiàn)。有興趣的朋友可以繼續(xù)嘗試。

其實(shí)，bitset 包也有人實(shí)現(xiàn)了，github地址 bit[5]?？梢宰x讀它的源碼，實(shí)現(xiàn)思路和上面介紹差不多。

下面是一個(gè)使用案例。

package main

import (
 "fmt"

 "github.com/yourbasic/bit"
)

func main() {
 s := bit.New(2, 3, 4, 65, 128)
 fmt.Println("s contains 65", s.Contains(65))
 fmt.Println("s contains 15", s.Contains(15))

 s.Add(15)
 fmt.Println("s contains 15", s.Contains(15))

 fmt.Println("next 20 is ", s.Next(20))
 fmt.Println("prev 20 is ", s.Prev(20))

 s2 := bit.New(10, 22, 30)

 s3 := s.Or(s2)
 fmt.Println("next 20 is ", s3.Next(20))

 s3.Visit(func(n int) bool {
 fmt.Println(n)
 return false // 返回 true 表示終止遍歷
 })
}

執(zhí)行結(jié)果：

s contains 65 true
s contains 15 false
s contains 15 true
next 20 is 65
prev 20 is 15
next 20 is 22
2
3
4
10
15
22
30
65
128

代碼的意思很好理解，就是一些增刪改查和集合的操作。要注意的是，bitset 和前面的 set 的區(qū)別，bitset 的成員只能是 int 整型，沒有 set 靈活。平時(shí)的使用場(chǎng)景也比較少，主要用在對(duì)效率和存儲(chǔ)空間要求較高的場(chǎng)景。

總結(jié)

本文介紹了Go 中兩種 set 的實(shí)現(xiàn)原理，并在此基礎(chǔ)介紹了對(duì)應(yīng)于它們的兩個(gè)包簡(jiǎn)單使用。我覺得，通過這篇文章，Go 中 set 的使用，基本都可以搞定了。

除這兩個(gè)包，再補(bǔ)充兩個(gè)，zoumo/goset[6] 和 github.com/willf/bitset[7]。

參考資料

[1]2 basic set implementations: https://yourbasic.org/golang/implement-set/

[2]一篇文章: https://www.jb51.net/article/170043.htm

[3]golang-set: https://github.com/deckarep/golang-set

[4]Bitmasks, bitsets and flags: https://yourbasic.org/golang/bitmask-flag-set-clear/

[5]bit: https://github.com/yourbasic/bit

[6]zoumo/goset: https://github.com/zoumo/goset

[7]github.com/willf/bitset: https://github.com/willf/bitset

以上就是本文的全部內(nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持億速云。