欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

详解Go中Set的实现方式

程序员文章站 2022-08-30 12:18:00
本篇主要讲述如何利用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的主要函数实现方式,还是很有意思的。继续加油。也希望大家多多支持。