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

今天来聊一下 go 如何使用 set，本文将会涉及 set 和 bitset 两种数据结构。

go 的数据结构

go 内置的数据结构并不多。工作中，我们最常用的两种数据结构分别是 slice 和 map，即切片和映射。其实，go 中也有数组，切片的底层就是数组，只不过因为切片的存在，我们平时很少使用它。

除了 go 内置的数据结构，还有一些数据结构是由 go 的官方 container 包提供，如 heap 堆、list 双向链表和ring 回环链表。但今天我们不讲它们，这些数据结构，对于熟手来说，看看文档就会使用了。

我们今天将来聊的是 set 和 bitset。据我所知，其他一些语言，比如 java，是有这两种数据结构。但 go 当前还没有以任何形式提供。

实现思路

先来看一篇文章，访问地址 2 basic set implementations[1] 阅读。文中介绍了两种 go 实现 set 的思路， 分别是 map 和 bitset。

有兴趣可以读读这篇文章，我们接下来具体介绍下。

map

我们知道，map 的 key 肯定是唯一的，而这恰好与 set 的特性一致，天然保证 set 中成员的唯一性。而且通过 map 实现 set，在检查是否存在某个元素时可直接使用 _, ok := m[key] 的语法，效率高。

先来看一个简单的实现，如下：

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

通过创建 map[string]bool 来存储 string 的集合，比较容易理解。但这里还有个问题，map 的 value 是布尔类型，这会导致 set 多占一定内存空间，而 set 不该有这个问题。

怎么解决这个问题？

设置 value 为空结构体，在 go 中，空结构体不占任何内存。当然，如果不确定，也可以来证明下这个结论。

unsafe.sizeof(struct{}{}) // 结果为 0

优化后的代码，如下：

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

之前在网上看到有人按这个思路做了封装，还写了一篇文章[2]，可以去读一下。

其实，github 上已经有个成熟的包，名为 golang-set，它也是采用这个思路实现的。访问地址 golang-set[3]，描述中说 docker 用的也是它。包中提供了两种 set 实现，线程安全的 set 和非线程安全的 set。

演示一个简单的案例。

package main

import (
 "fmt"

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

func main() {
 // 默认创建的线程安全的，如果无需线程安全
 // 可以使用 newthreadunsafeset 创建，使用方法都是一样的。
 s1 := mapset.newset(1, 2, 3, 4)
 fmt.println("s1 contains 3: ", s1.contains(3))
 fmt.println("s1 contains 5: ", s1.contains(5))

 // interface 参数，可以传递任意类型
 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}

例子中演示了简单的使用方式，如果有不明白的，看下源码，这些数据结构的操作方法名都是很常见的，比如交集 intersect、差集 difference 等，一看就懂。

bitset

继续聊聊 bitset，bitset 中每个数子用一个 bit 即能表示，对于一个 int8 的数字，我们可以用它表示 8 个数字，能帮助我们大大节省数据的存储空间。

bitset 最常见的应用有 bitmap 和 flag，即位图和标志位。这里，我们先尝试用它表示一些操作的标志位。比如某个场景，我们需要三个 flag 分别表示权限1、权限2和权限3，而且几个权限可以共存。我们可以分别用三个常量 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))
 }
}

例子中，我们本来需要三个数才能表示这三个标志，但现在通过一个 uint8 就可以。bitset 的一些操作，如设置 set、清除 clear、切换 toggle、检查 has 通过位运算就可以实现，而且非常高效。

bitset 对集合操作有着天然的优势，直接通过位运算符便可实现。比如交集、并集、和差集，示例如下：

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

底层的语言、库、框架常会使用这种方式设置标志位。

以上的例子中只展示了少量数据的处理方式，uint8 占 8 bit 空间，只能表示 8 个数字。那大数据场景能否可以使用这套思路呢？

我们可以把 bitset 和 go 中的切片结合起来，重新定义 bits 类型，如下：

type bitset struct {
 data []int64
}

但如此也会产生一些问题，设置 bit，我们怎么知道它在哪里呢？仔细想想，这个位置信息包含两部分，即保存该 bit 的数在切片索引位置和该 bit 在数字中的哪位，分别将它们命名为 index 和 position。那怎么获取？

index 可以通过整除获取，比如我们想知道表示 65 的 bit 在切片的哪个 index，通过 65 / 64 即可获得，如果为了高效，也可以用位运算实现，即用移位替换除法，比如 65 >> 6，6 表示移位偏移，即 2^n = 64 的 n。

postion 是除法的余数，我们可以通过模运算获得，比如 65 % 64 = 1，同样为了效率，也有相应的位运算实现，比如 65 & 0b00111111，即 65 & 63。

一个简单例子，如下：

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),
 }

 // 根据 n 设置 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))
}

输出结果

set contains 65 true
set contains 64 false

以上的例子功能很简单，只是为了演示，只有创建 bitset 和 contains 两个功能，其他诸如添加、删除、不同 bitset 间的交、并、差还没有实现。有兴趣的朋友可以继续尝试。

其实，bitset 包也有人实现了，github地址 bit[5]。可以读读它的源码，实现思路和上面介绍差不多。

下面是一个使用案例。

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 表示终止遍历
 })
}

执行结果：

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 的区别，bitset 的成员只能是 int 整型，没有 set 灵活。平时的使用场景也比较少，主要用在对效率和存储空间要求较高的场景。

总结

本文介绍了go 中两种 set 的实现原理，并在此基础介绍了对应于它们的两个包简单使用。我觉得，通过这篇文章，go 中 set 的使用，基本都可以搞定了。

除这两个包，再补充两个，zoumo/goset[6] 和 github.com/willf/bitset[7]。

参考资料

[1]2 basic set implementations:

[2]一篇文章:

[3]golang-set:

[4]bitmasks, bitsets and flags:

[5]bit:

[6]zoumo/goset:

[7]github.com/willf/bitset:

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持。