在 Go 中使用 bitset 位集：从基础操作到高性能集合运算与序列化-北京尧图网络

在 Go 中使用 bitset 位集从基础操作到高性能集合运算与序列化【免费下载链接】lokiLike Prometheus, but for logs.项目地址: https://gitcode.com/GitHub_Trending/lok/loki导读bitset是 Go 语言生态中用于「非负整数 → 布尔值」映射的高性能位集库相比map[uint]bool在内存占用与运算速度上均有数量级优势。本仓库Grafana Loki以依赖形式引入了github.com/bits-and-blooms/bitsetv1.25.0在布隆过滤器、索引与查询的位级过滤等场景中作为底层数据结构使用。阅读本文后你将掌握位集的创建、增删改查、集合运算、遍历、序列化与并发安全边界并能直接在 Go 项目中落地这套方案。位集是什么为什么比map[uint]bool更高效包级文档对位集的定义非常直白Package bitset implements bitsets, a mapping between non-negative integers and boolean values. It should be more efficient than map[uint] bool.其核心思路是把布尔值按位紧凑地存储而不是为每个元素单独分配一个 bool。从源码看BitSet的内部结构只有两个字段vendor/github.com/bits-and-blooms/bitset/bitset.go#L86-L90const wordSize 64 const wordBytes wordSize / 8 type BitSet struct { length uint set []uint64 }即底层是[]uint64数组每个 64 位字word可表示 64 个布尔位length记录当前逻辑位长度。因此「N 位所需内存至少为 N/8 字节」且数组只增长到「最大已设置位的下标 1」对应的字数按需分配extendSet负责扩容。相比map[uint]bool每个条目至少占用一个指针槽位和一个 bool 值通常数十字节位集在密集整型集合场景下内存可缩减一个数量级以上同时得益于math/bits的硬件指令级位运算见popcnt.go中基于bits.OnesCount64的种群计数实现集合基数统计Count与各类集合运算都能以 word 粒度并行推进。Loki 仓库在 go.mod#L185 中以间接依赖形式引入github.com/bits-and-blooms/bitset v1.25.0位集正是这类日志索引/过滤系统中布隆过滤器等位密集型数据结构的常用底层载体。快速上手安装与第一个示例安装方式v1.25.0 对应本仓库 vendor 目录中锁定的版本go get github.com/bits-and-blooms/bitset原文档给出了一个非常经典的「Go Fish」示例——用它模拟抽牌与配对判断同时演示Set、Test、Clear三个最基础的原子操作package main import ( fmt math/rand github.com/bits-and-blooms/bitset ) func main() { fmt.Printf(Hello from BitSet!\n) var b bitset.BitSet // play some Go Fish for i : 0; i 100; i { card1 : uint(rand.Intn(52)) card2 : uint(rand.Intn(52)) b.Set(card1) if b.Test(card2) { fmt.Println(Go Fish!) } b.Clear(card1) } }注意这里var b bitset.BitSet直接使用了零值——文档与源码均明确「零值即长度为 0 的空集合」safeSet会在首次使用时自动将set初始化为非 nilbitset.go#L95-L101。创建带初始容量提示的位集使用bitset.New(length)其实现为make([]uint64, wordsNeeded(length))即按(length63)/64个字预分配避免后续频繁扩容。此外还有MustNewpanic 版本、From/FromWithLength从既有[]uint64字数组直接构造适合高级用户零拷贝复用内存等构造函数。核心操作速查设置、清除、翻转与测试位集对单个整数提供四类最基础的原子方法且Set、Clear、Flip返回*BitSet支持链式调用方法行为返回值Set(i uint)将第 i 位置 1*BitSet可链式Clear(i uint)将第 i 位清 0*BitSet可链式SetTo(i uint, value bool)按布尔值设置第 i 位*BitSetFlip(i uint)翻转第 i 位*BitSet可链式Test(i uint)测试第 i 位是否为 1boolLen()返回当前位集长度最大下标1uintCount()返回置 1 的位数基数uint从实现看Test通过wordsIndex(i)定位字、uint64(1) (i wordMask)计算掩码后做与运算Set则先extendSet(i)确保容量足够再对目标字做或运算。链式调用的典型用法b.Set(10).Set(11) // 同时设置第 10、11 位 b.Flip(3).Clear(7) // 翻转第 3 位再清除第 7 位 if b.Test(10) { // 判断第 10 位是否被设置 // ... }此外还有面向区间的SetRange(start, end)、FlipRange(start, end)以及全量操作的SetAll()/ClearAll()。针对长度收缩Shrink(lastbitindex)可以按给定下标裁剪位集Compact()则会裁剪尾部多余的零字——文档明确位集「从不自动收缩」在高频增删场景下这两个方法用于手动归还内存。遍历置 1 的位有两种方式。经典写法配合NextSet从指定起点向后扫描for i, e : b.NextSet(0); e; i, e b.NextSet(i1) { fmt.Println(The following bit is set:, i) }如果使用 Go 1.23 及以上则可以直接用 range-over-func 语法for i : range b.EachSet() {}EachSet定义在 vendor/github.com/bits-and-blooms/bitset/bitset_iter.go#L19-L31它以bits.TrailingZeros64逐字跳过连续 0 位按升序 yield 每个置 1 位的下标提前 break 会停止迭代。该文件带有//go:build go1.23构建标签因此只在 Go 1.23 编译环境中生效。反向遍历则可用PreviousSet/PreviousClear。对于需要批量消费的场景NextSetMany(i, buffer)可以一次填充一个[]uint缓冲减少逐位调用开销。集合运算交集、并集、差集、补集与对称差位集真正的价值在于把集合运算转化为 word 级位的按位与/或/异或/取反这是map无法比拟的。完整的方法族如下运算返回新集合返回基数原地修改交集Intersection(other)IntersectionCardinality(other)InPlaceIntersection(other)并集Union(other)UnionCardinality(other)InPlaceUnion(other)差集Difference(other)DifferenceCardinality(other)InPlaceDifference(other)对称差SymmetricDifference(other)SymmetricDifferenceCardinality(other)InPlaceSymmetricDifference(other)补集Complement()——原文档中的示例验证了交集语义if b.Intersection(bitset.New(100).Set(10)).Count() 1 { fmt.Println(Intersection works.) } else { fmt.Println(Intersection doesnt work???) }实现细节上bitset.go#L1010-L1065 附近返回新集合的版本会先按长度对两个操作数排序再以较短的集合为基准进行位运算从而减少遍历字数原地版本则把结果写回调用者。基数版本如IntersectionCardinality不会物化中间结果直接逐字bits.OnesCount64累加适合「只想知道交叠数量」的判断场景——例如布隆过滤器多块之间做存在性验证时只关心交集是否非空。集合查询方法还包括Any()— 是否存在置 1 的位All()— 是否全部位均为 1None()— 是否没有任何置 1 的位IsSuperSet(other)/IsStrictSuperSet(other)— 是否为严格超集Equal(other)— 两个位集是否相等Clone()/Copy(c)/CopyFull(c)— 拷贝Copy返回被复制的位数CopyFull保证长度一致Rank(index)/Select(index)— 前 index 位的置 1 计数 / 第 index 个置 1 位的下标见 bitset.go#L1459-L1498是位集上「双向映射」的经典加速手段DumpAsBits()— 以 0/1 字符串输出全部位便于调试另一个值得一提的高级接口是Words()替代已废弃的Bytes()与SetBitsetFrom(buf []uint64)前者直接暴露内部[]uint64字数组非拷贝改动会影响位集后者可用外部字数组就地填充位集两者均标注「面向高级用户」可用于零拷贝集成其他位级结构。序列化WriteTo / ReadFrom 与编码选项位集可以安全、可移植地序列化为字节流。写入的典型模式原文档示例const length 9585 const oneEvery 97 bs : bitset.New(length) // Add some bits for i : uint(0); i length; i oneEvery { bs bs.Set(i) } var buf bytes.Buffer n, err : bs.WriteTo(buf) if err ! nil { // failure } // Here n buf.Len()读取回来// Read back from buf bs bitset.New() n, err bs.ReadFrom(buf) if err ! nil { // error } // n is the number of bytes read从实现看bitset.go#L1332-L1405WriteTo的流格式为先写一个uint64长度按当前字节序随后写wordCount()个 64 位字ReadFrom反向读取若当前实例容量不足会自动扩展extendSetMaybe并且尽力复用既有实例的内存以减少分配——这正是ReadFrom设计为方法而非构造函数的原因。返回值是写入/读取的字节数。关于字节序与编码包提供了全局配置函数BigEndian()/LittleEndian()/BinaryOrder()— 二进制序列化字节序默认binary.BigEndianBase64StdEncoding()— 切换 JSON 编解码的 base64 编码方式默认base64.URLEncoding这两个开关分别由包级变量binaryOrder与base64Encoding控制bitset.go#L67-L71注意它们是包级全局状态修改会影响包内所有实例的序列化行为。除io.Writer/io.Reader流接口外位集还实现了标准接口encoding.BinaryMarshalerMarshalBinary/UnmarshalBinary与encoding/jsonMarshalJSON/UnmarshalJSONJSON 形式为 base64 字符串可直接用于json.Marshal与gob等场景。BinaryStorageSize()可预估二进制存储所需的字节数。性能提示当写入/读取目标是文件或网络连接时建议先用bufio包装减少系统调用次数f, err : os.Create(myfile) w : bufio.NewWriter(f) f, err : os.Open(myfile) r : bufio.NewReader(f)内存模型与压缩位集的选择内存上需要牢记两个约束N 位的位集至少占用 N/8 字节位集长度始终≥「已访问的最大位下标 1」——也就是说Set(131)一次就会触发数 GB 级的扩容。文档明确警告it is possible to run out of memory while using a bitset。因此对「位稀疏」的大整数集合直接使用bitset可能并不划算更合适的选择是压缩位图 Roaring bitmap 及其 Go 实现RoaringBitmap/roaring。两者可相互转换mybitset : roaringbitmap.ToBitSet() // Roaring - 常规位集 newroaringbitmap : roaring.FromBitSet(mybitset) // 常规位集 - Roaringroaring库以分段压缩方式表达稀疏集合在保留集合运算能力的同时大幅降低稀疏场景的内存占用。选型建议位域较密集或下标范围紧凑时用bitset直接获得最大吞吐位域稀疏、跨度极大时用 Roaring需要两者结合时通过上述 API 在运行时互转。关于 Goroutine 安全文档明确位集默认不做任何同步跨 goroutine 并发访问同一实例是不安全的they are unsynchronized for performance。如果确实需要多 goroutine 共享两种官方建议通道传递所有权遵循 Go 惯例通过 channel 把*BitSet在 goroutine 间传递保证任意时刻只有一个持有者sync.Mutex串行化用互斥锁包裹所有对位集的操作牺牲并发换取安全。从源码看set []uint64的读写、extendSet的扩容均未加锁因此任何形式的并发读写包括并发Test都可能造成数据竞争。需要频繁共享时应优先考虑「每 goroutine 私有位集周期性合并」的分治模式例如并行分段计算后InPlaceUnion汇总既规避锁竞争又保留位集运算的高吞吐。测试与验证原文档要求提交前运行测试与覆盖率检查go test go test -cover本仓库 vendor 目录下的位集源码vendor/github.com/bits-and-blooms/bitset包含bitset.go核心实现约 1800 行、bitset_iter.goGo 1.23 迭代器、select.goRank/Select 支持、popcnt.go种群计数以及pext.gen.go生成的位抽取指令封装等文件配合仓库根目录 go.mod 中锁定的v1.25.0版本即可复现文档所述全部行为。位集相关功能在 Loki 中通常位于布隆过滤器、索引结构等存储路径如 pkg/storage 下的 bloom/tsdb 相关实现可作为位集在真实大规模日志系统中的应用参考。小结围绕「非负整数 ↔ 布尔值」这一核心抽象bitset提供了完整的方法矩阵单点操作的Set/Clear/Flip/Test/SetTo区间与全量的SetRange/FlipRange/SetAll/ClearAll集合层面的交集/并集/差集/补集/对称差及其基数与原地变体迭代层面的NextSet/NextSetMany/PreviousSet/EachSet序列化层面的WriteTo/ReadFrom/MarshalBinary/MarshalJSON以及内存管理层面的Shrink/Compact/Clone/Copy。将其内化到自己的工具箱你可以在布隆过滤器、位图索引、权限标记、IP 分配、去重标记等大量位密集型场景中以远低于map[uint]bool的内存与时间成本完成集合建模与运算。【免费下载链接】lokiLike Prometheus, but for logs.项目地址: https://gitcode.com/GitHub_Trending/lok/loki创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考

在 Go 中使用 bitset 位集：从基础操作到高性能集合运算与序列化

相关推荐

NSF 基金申请 Broader Impacts 写作全指南：从五大支柱到可执行策略

SAP HANA 迁移到 SAP HANA Cloud 前，为什么必须把 Migration User 这道权限关设计好

林伽一 · AI科技日报｜ 2026年09月11日

更多资讯

DO-160G 工作冲击与坠撞安全试验有什么区别

Java后端转型Agent开发：3个梯度实战项目助你轻松入门，收藏这份完整学习体系！

使用 Refine v5 与 @refinedev/react-table 构建高级 TanStack Table：行内编辑、批量删除与服务端筛选实战

在 AIRI 中配置 OpenAI 兼容 TTS：从 API Key 到语音发声的完整实战指南

小白程序员轻松入门大模型：构建稳定Coding Agent的秘诀

10款AI内容检测与优化工具实测推荐

今日更新

SpacetimeDB C++ 模块库实战：用 C++20 在数据库内构建 WebAssembly 模块

别踩雷！不是所有 AI 写作工具都靠谱，2026 高校认可工具精选

SSM+MySQL幼儿园管理系统源码解析：从部署到优化

本周精选

超人会飞不算本事：系统稳定依赖清晰规则与边界设计

超人VS蜘蛛侠：拆解超级IP的影响力与传播方法论

基于CNN的调制信号识别：MATLAB实现时频图分类实战

本月热门

基于YOLO的焊缝缺陷检测：从数据标注到工业部署全流程实践

分布式服务的决策记录

创业产品的首版范围

读完文章，想聊聊您的网站？