Golang 中如何实现 Set
在Go编程中,数据结构的选择对解决问题至关重要。本文将探讨如何在 GO 中实现 set 和 bitset 两种数据结构,以及它们在Go中的应用场景。
Go 的数据结构
Go 内置的数据结构并不多。工作中,我们最常用的两种数据结构分别是 slice 和 map,即切片和映射。 其实,Go 中也有数组,切片的底层就是数组,只不过因为切片的存在,我们平时很少使用它。
除了 Go 内置的数据结构,还有一些数据结构是由 Go 的官方 container 包提供,如 heap 堆、list 双向链表和ring 回环链表。但今天我们不讲它们,这些数据结构,对于熟手来说,看看文档就会使用了。
我们今天将来聊的是 set 和 bitset。据我所知,其他一些语言,比如 Java,是有这两种数据结构。但 Go 当前还没有以任何形式提供。
实现思路
先来看一篇文章,访问地址 2 basic set implementations 阅读。文中介绍了两种 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 { // Loopfmt.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 voidset := make(map[string]void) // New empty set
set["Foo"] = member // Add
for k := range set { // Loopfmt.Println(k)
}
delete(set, "Foo") // Delete
size := len(set) // Size
_, exists := set["Foo"] // Membership
之前在网上看到有人按这个思路做了封装,还写了一篇文章,可以去读一下。
其实,github 上已经有个成熟的包,名为 golang-set,它也是采用这个思路实现的。访问地址 golang-set,描述中说 Docker 用的也是它。包中提供了两种 set 实现,线程安全的 set 和非线程安全的 set。
演示一个简单的案例。
package mainimport ("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):
type Bits uint8const (F0 Bits = 1 << iotaF1F2
)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 Bitsb = 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 mainimport ("fmt"
)const (shift = 6mask = 0x3f // 即0b00111111
)type Bitset struct {data []int64
}func NewBitSet(n int) *Bitset {// 获取位置信息index := n >> shiftset := &Bitset{data: make([]int64, index+1),}// 根据 n 设置 bitsetset.data[index] |= 1 << uint(n&mask)return set
}func (set *Bitset) Contains(n int) bool {// 获取位置信息index := n >> shiftreturn 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。可以读读它的源码,实现思路和上面介绍差不多。
下面是一个使用案例。
package mainimport ("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 和 github.com/willf/bitset。
博文地址:Golang 中如何实现 Set
相关文章:

Golang 中如何实现 Set
在Go编程中,数据结构的选择对解决问题至关重要。本文将探讨如何在 GO 中实现 set 和 bitset 两种数据结构,以及它们在Go中的应用场景。 Go 的数据结构 Go 内置的数据结构并不多。工作中,我们最常用的两种数据结构分别是 slice 和 map&#…...

记录一下uniapp 集成腾讯im特别卡(已解决)
uniapp的项目运行在微信小程序 , 安卓 , ios手机三端 , 之前这个项目集成过im,不过版本太老了,0.x的版本, 现在需要添加客服功能,所以就升级了 由于是二开 , 也为了方便 , 沿用之前的webview嵌套腾讯IM的方案 , 选用uniapp集成ui ,升级之后所有安卓用户反馈点击进去特别卡,几…...
React16源码: React中的updateHostRoot的源码实现
HostRoot 的更新 1 )概述 HostRoot 是一个比较特殊的节点, 因为在一个react应用当中它只会有一个 HostRoot, 它对应的 Fiber 对象是我们的 RootFiber 对象重点在于它的更新过程 2 )源码 定位到 packages/react-reconciler/src/ReactFiberBeginWork.js…...
Template -- React
React 版本 Node 21.6.0Npm 10.2.4 项目 创建 npm init vite 项目名称reactjsnpm inpm run dev 依赖 npm i axios # 网络 npm i antd --save # UI npm i ant-design/icons npm i react-router-dom # 路由npm i sass -D # …...

HTML 入门手册(一)
目录 HTML 1-基础语法 单标签 双标签 整体结构 2-标题和水平线 标题 水平线 3-段落和换行 段落 换行 4-列表 无序列表 有序列表 嵌套列表 5-div和span div span 6-格式化标签 粗体 斜体 下划线中划线 上标和下标 7-超链接(a标签) 链接到URL 链接到本…...
GPT帮我快速解决工作上的问题案例
Python入门容易,但精通不易。自从跟着郭老师学Python后,工作中也想偷点懒,之前排班表的问题一直困扰着我,福音来了,现在随着郭老师的小蜜蜂AI出来,说干就干。马上来到郭老师为我们提供的AI网站:…...
Day32- 贪心算法part06
一、单调递增的数字 题目一:738. 单调递增的数字 738. 单调递增的数字 当且仅当每个相邻位数上的数字 x 和 y 满足 x < y 时,我们称这个整数是单调递增的。 给定一个整数 n ,返回 小于或等于 n 的最大数字,且数字呈 单调递…...

.NetCore Flurl.Http 升级到4.0后 https 无法建立SSL连接
Flurl.Http-3.2.4 升级到 4.0.0 版本后,https请求异常:Call failed. The SSL connection could not be established. 如下图: Flurl.Http-3.2.4版本绕过https的代码,对于 Flurl.Http-4.0.0 版本来说方法不再适用,3.2.…...

【每周AI简讯】GPT-5将有指数级提升,GPT Store正式上线
AI7 - Chat中文版最强人工智能 OpenAI的CEO奥特曼表示GPT-5将有指数级提升 GPT奥特曼参加Y-Combinator W24启动会上表示,我们已经非常接近AGI。GPT-5将具有更好的推理能力、更高的准确性和视频支持。 GPT Store正式上线 OpenAI正式推出GPT store,目前…...

QT上位机开发(MFC vs QT)
【 声明:版权所有,欢迎转载,请勿用于商业用途。 联系信箱:feixiaoxing @163.com】 在qt之前,上位机开发的主要方法就是mfc。后来出现了c#语言之后,上位机的开发就有一部分人转成了c#。这些开发都是在windows平台完成的,而linux上面的界面,则都是通过各种小众库…...

线性代数:矩阵的定义
目录 一、定义 二、方阵 三、对角阵 四、单位阵 五、数量阵 六、行(列)矩阵 七、同型矩阵 八、矩阵相等 九、零矩阵 十、方阵的行列式 一、定义 二、方阵 三、对角阵 四、单位阵 五、数量阵 六、行(列)矩阵 七、同型矩…...

k8s 使用cert-manager证书管理自签
个人建议使用安装更快,比helm快,还要等待安装crd kubectl apply -f https://github.com/cert-manager/cert-manager/releases/download/v1.13.3/cert-manager.yaml#官网 https://cert-manager.io/docs/installation/kubectl/#创建自签的ClusterIssuer c…...

SpringSecurity+JWT前后端分离架构登录认证
目录 1. 数据库设计 2. 代码设计 登录认证过滤器 认证成功处理器AuthenticationSuccessHandler 认证失败处理器AuthenticationFailureHandler AuthenticationEntryPoint配置 AccessDeniedHandler配置 UserDetailsService配置 Token校验过滤器 登录认证过滤器接口配置…...

笔试面试题——二叉树进阶(一)
📘北尘_:个人主页 🌎个人专栏:《Linux操作系统》《经典算法试题 》《C》 《数据结构与算法》 ☀️走在路上,不忘来时的初心 文章目录 一、根据二叉树创建字符串1、题目讲解2、思路讲解3、代码实现 二、二叉树的分层遍历1、题目讲…...
Java反射示例
Java反射示例 创建数据类型ReflectPoint.java package com.reflection;import java.util.Date;public class ReflectPoint {private Date birthday new Date();private int x;public int y;public String str1 "ball";public String str2 "basketball"…...
【WinForm.NET开发】实现使用后台操作的窗体
本文内容 创建使用后台操作的窗体使用设计器创建 BackgroundWorker添加异步事件处理程序添加进度报告和取消支持Checkpoint 如果某项操作需要很长的时间才能完成,并且不希望用户界面 (UI) 停止响应或阻塞,则可以使用 BackgroundWorker 类在另一个线程上…...

【操作系统和计网从入门到深入】(四)基础IO和文件系统
前言 这个专栏其实是博主在复习操作系统和计算机网络时候的笔记,所以如果是博主比较熟悉的知识点,博主可能就直接跳过了,但是所有重要的知识点,在这个专栏里面都会提到!而且我也一定会保证这个专栏知识点的完整性&…...

四.Winform使用Webview2加载本地HTML页面并互相通信
Winform使用Webview2加载本地HTML页面并互相通信 往期目录本节目标核心代码实现HTML代码实现的窗体Demo2代码效果图 往期目录 往期相关文章目录 专栏目录 本节目标 实现刷新按钮点击 C# winform按钮可以调用C# winform代码显示到html上点击HTML按钮可以调用C# winform代码更…...
如何有效清理您的Python环境:清除Pip缓存
Python是一个广泛使用的高级编程语言,以其强大的库和框架而闻名。然而,随着时间的推移和不断安装新的包,Python环境可能会变得混乱不堪,尤其是pip缓存可能占用大量的磁盘空间。本文将向您展示如何有效地清理pip缓存,保…...

Jira 母公司全面停服 Server 产品,用户如何迁移至极狐GitLab
Jira 母公司即将全面停服旗下部分 Server 端产品的销售和服务支持! Jira 母公司 Atlassian 在几年前确定了公司的战略为“全面上云”,为此做出了停止 Server 产品的销售和支持。整个时间线从 2021 年 2 月 2 日开始,直到今年 2 月 15 日&…...

Spark 之 入门讲解详细版(1)
1、简介 1.1 Spark简介 Spark是加州大学伯克利分校AMP实验室(Algorithms, Machines, and People Lab)开发通用内存并行计算框架。Spark在2013年6月进入Apache成为孵化项目,8个月后成为Apache顶级项目,速度之快足见过人之处&…...
在HarmonyOS ArkTS ArkUI-X 5.0及以上版本中,手势开发全攻略:
在 HarmonyOS 应用开发中,手势交互是连接用户与设备的核心纽带。ArkTS 框架提供了丰富的手势处理能力,既支持点击、长按、拖拽等基础单一手势的精细控制,也能通过多种绑定策略解决父子组件的手势竞争问题。本文将结合官方开发文档,…...

高频面试之3Zookeeper
高频面试之3Zookeeper 文章目录 高频面试之3Zookeeper3.1 常用命令3.2 选举机制3.3 Zookeeper符合法则中哪两个?3.4 Zookeeper脑裂3.5 Zookeeper用来干嘛了 3.1 常用命令 ls、get、create、delete、deleteall3.2 选举机制 半数机制(过半机制࿰…...

Vue2 第一节_Vue2上手_插值表达式{{}}_访问数据和修改数据_Vue开发者工具
文章目录 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染2. 插值表达式{{}}3. 访问数据和修改数据4. vue响应式5. Vue开发者工具--方便调试 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染 准备容器引包创建Vue实例 new Vue()指定配置项 ->渲染数据 准备一个容器,例如: …...

令牌桶 滑动窗口->限流 分布式信号量->限并发的原理 lua脚本分析介绍
文章目录 前言限流限制并发的实际理解限流令牌桶代码实现结果分析令牌桶lua的模拟实现原理总结: 滑动窗口代码实现结果分析lua脚本原理解析 限并发分布式信号量代码实现结果分析lua脚本实现原理 双注解去实现限流 并发结果分析: 实际业务去理解体会统一注…...

华为云Flexus+DeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建
华为云FlexusDeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建 前言 如今大模型其性能出色,华为云 ModelArts Studio_MaaS大模型即服务平台华为云内置了大模型,能助力我们轻松驾驭 DeepSeek-V3/R1,本文中将分享如何…...

Springboot社区养老保险系统小程序
一、前言 随着我国经济迅速发展,人们对手机的需求越来越大,各种手机软件也都在被广泛应用,但是对于手机进行数据信息管理,对于手机的各种软件也是备受用户的喜爱,社区养老保险系统小程序被用户普遍使用,为方…...
CSS设置元素的宽度根据其内容自动调整
width: fit-content 是 CSS 中的一个属性值,用于设置元素的宽度根据其内容自动调整,确保宽度刚好容纳内容而不会超出。 效果对比 默认情况(width: auto): 块级元素(如 <div>)会占满父容器…...

安全突围:重塑内生安全体系:齐向东在2025年BCS大会的演讲
文章目录 前言第一部分:体系力量是突围之钥第一重困境是体系思想落地不畅。第二重困境是大小体系融合瓶颈。第三重困境是“小体系”运营梗阻。 第二部分:体系矛盾是突围之障一是数据孤岛的障碍。二是投入不足的障碍。三是新旧兼容难的障碍。 第三部分&am…...
C#中的CLR属性、依赖属性与附加属性
CLR属性的主要特征 封装性: 隐藏字段的实现细节 提供对字段的受控访问 访问控制: 可单独设置get/set访问器的可见性 可创建只读或只写属性 计算属性: 可以在getter中执行计算逻辑 不需要直接对应一个字段 验证逻辑: 可以…...