开发工具【免费下载链接】go-datastructuresA collection of useful, performant, and threadsafe Go datastructures.项目地址https://gitcode.com/gh_mirrors/go/go-datastructures点击查看免费下载go-datastructures 是一个收集了多种常用、高性能且面向并发threadsafeGo 数据结构的开源库覆盖区间树、位数组、队列、范围树、斐波那契堆、集合、切片扩展等十余个模块。本文以 documentation.md 为纲结合仓库源码逐一剖析各数据结构的核心设计、适用场景与底层实现帮助读者在选型时快速判断该用哪个包、为什么、怎么用。项目定位与设计目标正如 documentation.md 开头所述这个库的目标有两层移植把其他语言中一些常见数据结构的成熟实现移植到 Go改进在已有数据结构之上做出针对 Go 语言特性的优化。这些结构被设计为社区可复用的公共组件希望借助开源汇集更多人的工程经验来持续打磨 Go 侧的实现。仓库根目录的 datastructures.go 用一个空导入包统一导入了全部子包方便 depman 等依赖管理工具只导入这一个包即可获得所有子包go.mod声明模块为github.com/Workiva/go-datastructuresgo.mod。获取、测试与上手从 README.md 的 Installation/Testing 小节可以确认标准的获取与验证方式要求 Go 1.3仓库go.mod当前声明go 1.15# 获取全部子包 go get github.com/Workiva/go-datastructures/... # 首次拉取测试依赖并运行全部单元测试 go get -t -u ./... go test ./... # 之后每次只需 go test ./...下文每一节给出的源码路径都对应仓库中真实存在的文件读者可直接对照阅读。Augmented Treen 维区间相交查询区间增广树Augmented Tree专门用于判定区间之间的相交关系。文档给出的典型场景是电子表格把单元格 A1 表示为半开区间 A1:B2然后遍历图去查找精确或近似的相交关系。仓库包注释则用二维平面举例由(0,0)与(10,10)围成的平面是否与(-5,-5)与(5,5)围成的平面重叠答案是重叠——把点查询也建模成长度为零或极小的小区间即可统一处理。接口与实现要点Interval 接口任何要放入树中的元素都必须实现 Interval 接口提供LowAtDimension(uint64) int64、HighAtDimension(uint64) int64、OverlapsAtDimension(Interval, uint64) bool和唯一ID() uint64。注释明确要求区间不可变——返回值一旦变化会导致未定义行为。Tree 接口Tree 提供Add(...Interval)、Delete(...Interval)、Query(Interval) Intervals与Traverse(func(Interval))。用接口而非具体类型返回是因为构造出的树可能是单维或多维的。构造器augmentedtree.New(dimensions uint64) Treeatree.go。从 atree.go 的实现看底层是一棵自顶向下的红黑二叉搜索树node结构体带red标志位旋转/双旋转逻辑见 rotate / doubleRotate。每个节点额外维护子树内所有区间的min/max边界setMin / setMax查询时据此剪枝插入路径上的节点会同步更新max/minadd保证 O(log n) 级别的单维操作删除后通过adjustRanges自底向上重算边界Delete查询沿树下行时先用overlaps(n.children[i].max, high, n.children[i].min, low)判断子树是否有相交可能再逐节点调用intervalOverlapsquery。多维相交判定正是依赖Interval.OverlapsAtDimension在维度 2..maxDimension 上逐一比对intervalOverlaps。维度代价与未来方向文档明确指出当前实现支持 n 维但最快的查询是能在第一维上完成过滤的查询如果查询只能靠第一维以外的维度过滤速度会明显变慢。因此使用时尽量把主过滤维度放在第一维。Query返回的Intervals结果列表复用了sync.Pool缓冲并支持Dispose()归还intervals.go高频查询场景记得调用Dispose以减少分配。文档中的 TODO 是补充自底向上版本以更好地处理重复区间。Bit Array用位运算加速集合比较位数组bitarray/bitmap适用于数据可表示为整数 ID的集合比较场景。文档举的例子是集合{1, 3, 5}与{3, 5, 7}各自编码进位数组后一次按位与即可完成交集计算不计算编码/解码开销而不必逐个元素比较。包内还提供把位数组还原为整数列表的能力。两种密度实现仓库的 BitArray 接口 定义了SetBit/GetBit/ClearBit/Reset/Capacity/Count/Intersects/Or/And/Nand/ToNums等方法接口背后有两种实现稠密实现densebitArray以[]block为底层存储bitarray.go 同包文件 bitarray.go位操作直接在整型块上完成速度最快稀疏实现sparse借鉴线性代数中压缩行稀疏矩阵CSR的思想把大范围稀疏的位图压缩存储。代价是插入与存在性检查退化为 O(log n)但求交集时仍保有速度优势文档原话retains some speed advantages when checking for intersections。两种实现都要求元素拥有uint64唯一标识因此它很适合知道 ID 但不想用哈希表判存在的场景——这一点在 README.md 的 Bitarray 小节有更直白的描述。常量长度 Bitmap此外包内还有 Bitmap32 / Bitmap64分别把 32/64 个布尔值直接塞进一个uint32/uint64所有操作都是 O(1) 的纯位运算SetBit/ClearBit/GetBit/PopCount无需数组、无需哈希。文档还顺带点明位数组加上 B 树是构建原生 Go 数据库的两块基石之一这个Going Forward的线索在文档结尾再次出现。Futures一次完成、全员广播的结果Futures 解决的是一个 goroutine 开始某项操作后希望多个等待方都能收到同一个结果的问题。用缓冲 channel 也能做但对同一结果要反复发送给每个等待者显得有些冗余。仓库包注释futures.go说得更直白channel 在多个监听者同时监听时只会随机挑选一个消费者而 Future 会把结果广播给所有监听者并缓存结果后来的监听者立刻拿到。核心 API 与实现// Completer 是一个只读 channelFuture 只从上面收结果 type Completer -chan interface{} // 构造监听 completer超时后所有等待者收到 error func New(completer Completer, timeout time.Duration) *Future // 阻塞直到结果就绪然后返回 (item, err) func (f *Future) GetResult() (interface{}, error) // 非阻塞地判断结果是否已产生 func (f *Future) HasResult() bool实现上Future结构体futures.go用sync.Mutex保护triggered/item/err用sync.WaitGroup挂起所有等待者listenForResult在select中同时监听 completer channel 与time.Timer超时则把所有监听者以timeout after %f seconds错误唤醒listenForResult。由于只完成一次、wg.Done()只调一次天然满足广播语义且结果被缓存后GetResult直接返回、不再阻塞。行为上它类似于 GAE 中 ndb 的 futures可被理解为一种广播 channel。使用注意点每个 Future 只能完成一次不要在同一个 completer 上重复调用New。Queue队列、优先队列与无锁环形缓冲queue 包内含三种队列文档与包注释queue.go说明其共同特性是发送永不阻塞、按需无限增长且对已Dispose的队列继续 Put 会返回 error 而不是像向已关闭 channel 发送那样 panic——这更贴合 Go 官方用 error 表达失败的设计理念。普通队列与 waitgroup 协调普通队列用waiters []*sema挂起等待者waiters空队列上等待的 goroutine 会在收到消息时被唤醒调用Dispose会立刻让所有等待线程带着 error 返回可用于优雅地通知消费者退出。文档特别指出只要给出合理的构造 hint容量提示普通队列在向 goroutine 发送数据时比 channel 更快。包注释中附有当时环境的基准测试BenchmarkQueue-8 671 ns/op对比BenchmarkChannel-8 2083 ns/op可作为参考而非绝对结论。优先队列priority_queue.go 要求元素实现Item接口的Compare(other Item) int返回 1/0/-1 表达大于/等于/小于Item。内部是一个用切片实现的二叉堆pop把末叶换到根后逐层下沉恢复堆序priorityItems.pop。文档提示当前优先队列速度一般理想替代是斐波那契堆仓库中已有 fibheap 可对照。MPMC 无锁环形缓冲queue 包最近还加入了多生产者多消费者MPMC环形缓冲RingBuffer容量向上取整到 2 的幂roundUpring.go并用 padding 隔离queue/dequeue计数器避免伪共享。满时 Put、空时 Get 会阻塞但Dispose会让所有被阻塞的线程带着 error 返回——这正是文档强调的同步并安全退出 goroutine便于对象被 GC 回收的用法。线程安全完全依靠CAS 原子操作因此速度很快包注释基准BenchmarkRBPut-8 58.1 ns/op、BenchmarkRBGet-8 26.8 ns/op。其设计参考了 1024cores 的 bounded MPMC queue。文档列出的 Future 计划是进一步实现无锁环形缓冲。Range Treen 维点数据的区间查询范围树用于以对数级复杂度存储并查询n 维整数点通常建模为笛卡尔坐标。注意两点查询区间含端点inclusive虽然名字里有 Tree但从包注释rangetree/interface.go和实现看仓库实际采用的是稀疏 n 维有序数组而非传统 BBST——文档说明这是因为 n 维场景下稀疏数组实现更简单、更高维时更省空间。两种实现可变版本orderedTreeorderedtree.go以顶层有序节点列表逐维下钻插入复杂度为 O(log n^d)d 为维度README 给出。速度快但若消费者需要线程安全写入侧会有锁竞争不可变版本immutableRangeTreeimmutable.go是写时复制copy-on-write结构——写操作只复制路径上的那部分节点其余子树被共享。如 Add 所示每次添加返回一棵新树旧树保持不变因此多线程读写互不阻塞。代价是单次操作更慢且批量写入时性价比最高。两者都通过Entry.ValueAtDimension(uint64) int64定位点在每一维的值并通过Interval描述查询范围Entry / Interval / RangeTree。RangeTree 接口还提供了Apply按序迭代命中项、可提前取消、Get按地址批量取回与InsertAtDimension批量平移某维度上的元素并返回被移动/被删除的条目等实用操作。文档的 TODO 是统一两套实现到同一接口并进一步优化性能。Fibonacci Heap摊销 O(1) 的 decrease-key斐波那契堆fibheap是标准实现键为浮点优先级。它的价值在于decrease-key 操作摊销 O(1)因此非常适合作为 Dijkstra 最短路径与 Prim 最小生成树算法的底层优先队列达到理论最优复杂度。包注释fibheap.go给出了经典结论insert/peek/merge 为常数级decrease-key 摊销 O(1)dequeueMin/delete 摊销 O(log n)以 Dijkstra 为例用斐波那契堆可做到 O(m n log n)优于二叉堆/二项堆的 O(m log n)。实现上堆以满足最小堆性质的环形双向链表组织多棵树的森林每个节点记录父指针、任意一个子指针、度数孩子数与标记位堆本身持有最小值指针dequeueMin在弹出最小根后把其子节点并入根表再按度数合并树保证根表中每种度数至多一棵树decreaseKey通过剪切-上浮-级联标记恢复堆性质delete则退化为把键降到 -∞ 再 dequeueMin。实践提醒README 亦有说明斐波那契堆常数因子较大实际性能未必优于配对堆且未针对线程安全设计——单线程/单 goroutine 使用为宜。文档的 Future 计划包括为每个节点挂一个interface{}值指针以携带用户数据、用本堆写出快速 Dijkstra/Prim 实现、以及分析并设计线程安全变体。Set基于 map 的线程安全无序集合文档对集合模块着墨不多这是一个由 Go map 支撑的无序集合且是线程安全的——加锁对性能略有影响但读操作可以并行。查看 set/dict.go内部是items map[interface{}]struct{}加sync.RWMutexSetAdd/Remove走写锁Exists/Len/All走读锁因此并发读不互斥Flatten会把元素摊平成切片并缓存下次 Flatten 直接返回缓存构造器New(items ...interface{})从sync.Pool取对象复用内存initDispose会清空并归还池子。用法上元素类型是interface{}方法集较小Add/Remove/Exists/Flatten/Len/Clear/All/Dispose。文档的 Future 方向是基于标准库hash/fnv非常快的非加密哈希从零实现哈希表并尝试无锁哈希表。SliceInt64 版的有序切片Go 标准库sort包自带IntSlice[]int的排序/搜索辅助但由于早期 Go 没有泛型int64 版本必须单开包。slice 包就是标准库IntSlice的int64 对位实现slice/int64.go并且额外增加了一个Insert方法。Int64Slice实现sort.InterfaceLen/Less/Swap并提供Sort()原地排序Search(x int64) int二分查找返回不低于 x 的最小下标调用方需自行判断该位置是否恰为 xSearchExists(x)基于 Search 的判存在未排序时行为未定义Insert(x)把 x 插入已排序切片中的正确位置并返回新切片若已存在则原样返回Insert。Int64Slice还被 rangetree 内部用作维度坐标缓存见 immutable.go 的newCache是库内复用度较高的基础件。Threadsafe锁包装的线程安全组件threadsafe 包的思路很直接给一些常见接口加锁使其可被多 goroutine 并发访问。文档为此辩护道虽然 Go 官方建议忘掉锁、用 channel但 channel 本质上是锁的高级抽象且在某些多 goroutine 共同写一块内存的场景里channel 既丑又慢又没必要。目前包内唯一的实现是 threadsafe/err 的Error结构用sync.RWMutex保护一个error字段提供Set(err error)与Get() error方便多 goroutine 并发地向同一个错误变量写入比如并行任务的第一个错误。注意该包注释已标记Deprecated建议改用golang.org/x/sync/errgroup或atomic.Pointer[error]——新代码可优先考虑这些替代方案。结语与未来方向Going Forward文档结尾勾勒了作者的长期规划仓库已存在 B 树相关 PR本仓库 btree 目录下已有 palm、plus、immutable 等变体B 树 位数组这两块拼图齐备后就有条件写一个原生的 Go 数据库。这也是为什么文档中位数组是构建原生 Go 数据库所需的两件东西之一的伏笔在这里回收。对使用者的建议同样写在文档里这些数据结构是大量程序与算法即使它们常被上层库抽象隐藏的地基欢迎任何人提交优化与 bug 修复。阅读完本文后你可以按需深入各子包源码——例如区间查询场景看 augmentedtree、集合运算看 bitarray、并发广播看 futures、goroutine 间协调看 queue、n 维点查询看 rangetree、图算法底层层看 fibheap——每处都有对应的_test.go测试文件可以对照验证行为。赞分享开发工具【免费下载链接】go-datastructuresA collection of useful, performant, and threadsafe Go datastructures.项目地址https://gitcode.com/gh_mirrors/go/go-datastructures点击查看免费下载相关推荐二叉堆与斐波那契堆性能对比数据结构选择的终极指南二叉堆与斐波那契堆性能对比数据结构选择的终极指南 在算法和数据结构的世界中堆与优先队列是实现高效操作的关键工具。今天我们将深入探讨两种重要的堆实现二叉堆和示例工程Floccus跨浏览器书签同步完整操作手册打造你的私有书签云Floccus跨浏览器书签同步完整操作手册打造你的私有书签云 在当今多设备、多浏览器的数字生活中书签同步已成为现代互联网用户的核心需求。Floccus作为一前端移动开发数据同步《程序员数学斐波那契》——为什么不能用斐波那契散列做数据库路由算法《程序员数学斐波那契》——为什么不能用斐波那契散列做数据库路由算法 导读斐波那契数列不只是面试题里的递归经典案例它在 JDK 源码中催生了 Thread文档教程后端上一篇FcaNet频率通道注意力网络如何用离散余弦变换提升深度学习模型性能下一篇Kimi Code 自动权限模式Auto Permission Mode指南从进入提醒到源码级运行机制创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 
长河君 · 2026/10/14 20:37:38 · 阅读 1.2k go-datastructures 数据结构库全景指南：从区间树到斐波那契堆的 Go 实现
开发工具【免费下载链接】go-datastructuresA collection of useful, performant, and threadsafe Go datastructures.项目地址https://gitcode.com/gh_mirrors/go/go-datastructures点击查看免费下载go-datastructures 是一个收集了多种常用、高性能且面向并发threadsafeGo 数据结构的开源库覆盖区间树、位数组、队列、范围树、斐波那契堆、集合、切片扩展等十余个模块。本文以 documentation.md 为纲结合仓库源码逐一剖析各数据结构的核心设计、适用场景与底层实现帮助读者在选型时快速判断该用哪个包、为什么、怎么用。项目定位与设计目标正如 documentation.md 开头所述这个库的目标有两层移植把其他语言中一些常见数据结构的成熟实现移植到 Go改进在已有数据结构之上做出针对 Go 语言特性的优化。这些结构被设计为社区可复用的公共组件希望借助开源汇集更多人的工程经验来持续打磨 Go 侧的实现。仓库根目录的 datastructures.go 用一个空导入包统一导入了全部子包方便 depman 等依赖管理工具只导入这一个包即可获得所有子包go.mod声明模块为github.com/Workiva/go-datastructuresgo.mod。获取、测试与上手从 README.md 的 Installation/Testing 小节可以确认标准的获取与验证方式要求 Go 1.3仓库go.mod当前声明go 1.15# 获取全部子包 go get github.com/Workiva/go-datastructures/... # 首次拉取测试依赖并运行全部单元测试 go get -t -u ./... go test ./... # 之后每次只需 go test ./...下文每一节给出的源码路径都对应仓库中真实存在的文件读者可直接对照阅读。Augmented Treen 维区间相交查询区间增广树Augmented Tree专门用于判定区间之间的相交关系。文档给出的典型场景是电子表格把单元格 A1 表示为半开区间 A1:B2然后遍历图去查找精确或近似的相交关系。仓库包注释则用二维平面举例由(0,0)与(10,10)围成的平面是否与(-5,-5)与(5,5)围成的平面重叠答案是重叠——把点查询也建模成长度为零或极小的小区间即可统一处理。接口与实现要点Interval 接口任何要放入树中的元素都必须实现 Interval 接口提供LowAtDimension(uint64) int64、HighAtDimension(uint64) int64、OverlapsAtDimension(Interval, uint64) bool和唯一ID() uint64。注释明确要求区间不可变——返回值一旦变化会导致未定义行为。Tree 接口Tree 提供Add(...Interval)、Delete(...Interval)、Query(Interval) Intervals与Traverse(func(Interval))。用接口而非具体类型返回是因为构造出的树可能是单维或多维的。构造器augmentedtree.New(dimensions uint64) Treeatree.go。从 atree.go 的实现看底层是一棵自顶向下的红黑二叉搜索树node结构体带red标志位旋转/双旋转逻辑见 rotate / doubleRotate。每个节点额外维护子树内所有区间的min/max边界setMin / setMax查询时据此剪枝插入路径上的节点会同步更新max/minadd保证 O(log n) 级别的单维操作删除后通过adjustRanges自底向上重算边界Delete查询沿树下行时先用overlaps(n.children[i].max, high, n.children[i].min, low)判断子树是否有相交可能再逐节点调用intervalOverlapsquery。多维相交判定正是依赖Interval.OverlapsAtDimension在维度 2..maxDimension 上逐一比对intervalOverlaps。维度代价与未来方向文档明确指出当前实现支持 n 维但最快的查询是能在第一维上完成过滤的查询如果查询只能靠第一维以外的维度过滤速度会明显变慢。因此使用时尽量把主过滤维度放在第一维。Query返回的Intervals结果列表复用了sync.Pool缓冲并支持Dispose()归还intervals.go高频查询场景记得调用Dispose以减少分配。文档中的 TODO 是补充自底向上版本以更好地处理重复区间。Bit Array用位运算加速集合比较位数组bitarray/bitmap适用于数据可表示为整数 ID的集合比较场景。文档举的例子是集合{1, 3, 5}与{3, 5, 7}各自编码进位数组后一次按位与即可完成交集计算不计算编码/解码开销而不必逐个元素比较。包内还提供把位数组还原为整数列表的能力。两种密度实现仓库的 BitArray 接口 定义了SetBit/GetBit/ClearBit/Reset/Capacity/Count/Intersects/Or/And/Nand/ToNums等方法接口背后有两种实现稠密实现densebitArray以[]block为底层存储bitarray.go 同包文件 bitarray.go位操作直接在整型块上完成速度最快稀疏实现sparse借鉴线性代数中压缩行稀疏矩阵CSR的思想把大范围稀疏的位图压缩存储。代价是插入与存在性检查退化为 O(log n)但求交集时仍保有速度优势文档原话retains some speed advantages when checking for intersections。两种实现都要求元素拥有uint64唯一标识因此它很适合知道 ID 但不想用哈希表判存在的场景——这一点在 README.md 的 Bitarray 小节有更直白的描述。常量长度 Bitmap此外包内还有 Bitmap32 / Bitmap64分别把 32/64 个布尔值直接塞进一个uint32/uint64所有操作都是 O(1) 的纯位运算SetBit/ClearBit/GetBit/PopCount无需数组、无需哈希。文档还顺带点明位数组加上 B 树是构建原生 Go 数据库的两块基石之一这个Going Forward的线索在文档结尾再次出现。Futures一次完成、全员广播的结果Futures 解决的是一个 goroutine 开始某项操作后希望多个等待方都能收到同一个结果的问题。用缓冲 channel 也能做但对同一结果要反复发送给每个等待者显得有些冗余。仓库包注释futures.go说得更直白channel 在多个监听者同时监听时只会随机挑选一个消费者而 Future 会把结果广播给所有监听者并缓存结果后来的监听者立刻拿到。核心 API 与实现// Completer 是一个只读 channelFuture 只从上面收结果 type Completer -chan interface{} // 构造监听 completer超时后所有等待者收到 error func New(completer Completer, timeout time.Duration) *Future // 阻塞直到结果就绪然后返回 (item, err) func (f *Future) GetResult() (interface{}, error) // 非阻塞地判断结果是否已产生 func (f *Future) HasResult() bool实现上Future结构体futures.go用sync.Mutex保护triggered/item/err用sync.WaitGroup挂起所有等待者listenForResult在select中同时监听 completer channel 与time.Timer超时则把所有监听者以timeout after %f seconds错误唤醒listenForResult。由于只完成一次、wg.Done()只调一次天然满足广播语义且结果被缓存后GetResult直接返回、不再阻塞。行为上它类似于 GAE 中 ndb 的 futures可被理解为一种广播 channel。使用注意点每个 Future 只能完成一次不要在同一个 completer 上重复调用New。Queue队列、优先队列与无锁环形缓冲queue 包内含三种队列文档与包注释queue.go说明其共同特性是发送永不阻塞、按需无限增长且对已Dispose的队列继续 Put 会返回 error 而不是像向已关闭 channel 发送那样 panic——这更贴合 Go 官方用 error 表达失败的设计理念。普通队列与 waitgroup 协调普通队列用waiters []*sema挂起等待者waiters空队列上等待的 goroutine 会在收到消息时被唤醒调用Dispose会立刻让所有等待线程带着 error 返回可用于优雅地通知消费者退出。文档特别指出只要给出合理的构造 hint容量提示普通队列在向 goroutine 发送数据时比 channel 更快。包注释中附有当时环境的基准测试BenchmarkQueue-8 671 ns/op对比BenchmarkChannel-8 2083 ns/op可作为参考而非绝对结论。优先队列priority_queue.go 要求元素实现Item接口的Compare(other Item) int返回 1/0/-1 表达大于/等于/小于Item。内部是一个用切片实现的二叉堆pop把末叶换到根后逐层下沉恢复堆序priorityItems.pop。文档提示当前优先队列速度一般理想替代是斐波那契堆仓库中已有 fibheap 可对照。MPMC 无锁环形缓冲queue 包最近还加入了多生产者多消费者MPMC环形缓冲RingBuffer容量向上取整到 2 的幂roundUpring.go并用 padding 隔离queue/dequeue计数器避免伪共享。满时 Put、空时 Get 会阻塞但Dispose会让所有被阻塞的线程带着 error 返回——这正是文档强调的同步并安全退出 goroutine便于对象被 GC 回收的用法。线程安全完全依靠CAS 原子操作因此速度很快包注释基准BenchmarkRBPut-8 58.1 ns/op、BenchmarkRBGet-8 26.8 ns/op。其设计参考了 1024cores 的 bounded MPMC queue。文档列出的 Future 计划是进一步实现无锁环形缓冲。Range Treen 维点数据的区间查询范围树用于以对数级复杂度存储并查询n 维整数点通常建模为笛卡尔坐标。注意两点查询区间含端点inclusive虽然名字里有 Tree但从包注释rangetree/interface.go和实现看仓库实际采用的是稀疏 n 维有序数组而非传统 BBST——文档说明这是因为 n 维场景下稀疏数组实现更简单、更高维时更省空间。两种实现可变版本orderedTreeorderedtree.go以顶层有序节点列表逐维下钻插入复杂度为 O(log n^d)d 为维度README 给出。速度快但若消费者需要线程安全写入侧会有锁竞争不可变版本immutableRangeTreeimmutable.go是写时复制copy-on-write结构——写操作只复制路径上的那部分节点其余子树被共享。如 Add 所示每次添加返回一棵新树旧树保持不变因此多线程读写互不阻塞。代价是单次操作更慢且批量写入时性价比最高。两者都通过Entry.ValueAtDimension(uint64) int64定位点在每一维的值并通过Interval描述查询范围Entry / Interval / RangeTree。RangeTree 接口还提供了Apply按序迭代命中项、可提前取消、Get按地址批量取回与InsertAtDimension批量平移某维度上的元素并返回被移动/被删除的条目等实用操作。文档的 TODO 是统一两套实现到同一接口并进一步优化性能。Fibonacci Heap摊销 O(1) 的 decrease-key斐波那契堆fibheap是标准实现键为浮点优先级。它的价值在于decrease-key 操作摊销 O(1)因此非常适合作为 Dijkstra 最短路径与 Prim 最小生成树算法的底层优先队列达到理论最优复杂度。包注释fibheap.go给出了经典结论insert/peek/merge 为常数级decrease-key 摊销 O(1)dequeueMin/delete 摊销 O(log n)以 Dijkstra 为例用斐波那契堆可做到 O(m n log n)优于二叉堆/二项堆的 O(m log n)。实现上堆以满足最小堆性质的环形双向链表组织多棵树的森林每个节点记录父指针、任意一个子指针、度数孩子数与标记位堆本身持有最小值指针dequeueMin在弹出最小根后把其子节点并入根表再按度数合并树保证根表中每种度数至多一棵树decreaseKey通过剪切-上浮-级联标记恢复堆性质delete则退化为把键降到 -∞ 再 dequeueMin。实践提醒README 亦有说明斐波那契堆常数因子较大实际性能未必优于配对堆且未针对线程安全设计——单线程/单 goroutine 使用为宜。文档的 Future 计划包括为每个节点挂一个interface{}值指针以携带用户数据、用本堆写出快速 Dijkstra/Prim 实现、以及分析并设计线程安全变体。Set基于 map 的线程安全无序集合文档对集合模块着墨不多这是一个由 Go map 支撑的无序集合且是线程安全的——加锁对性能略有影响但读操作可以并行。查看 set/dict.go内部是items map[interface{}]struct{}加sync.RWMutexSetAdd/Remove走写锁Exists/Len/All走读锁因此并发读不互斥Flatten会把元素摊平成切片并缓存下次 Flatten 直接返回缓存构造器New(items ...interface{})从sync.Pool取对象复用内存initDispose会清空并归还池子。用法上元素类型是interface{}方法集较小Add/Remove/Exists/Flatten/Len/Clear/All/Dispose。文档的 Future 方向是基于标准库hash/fnv非常快的非加密哈希从零实现哈希表并尝试无锁哈希表。SliceInt64 版的有序切片Go 标准库sort包自带IntSlice[]int的排序/搜索辅助但由于早期 Go 没有泛型int64 版本必须单开包。slice 包就是标准库IntSlice的int64 对位实现slice/int64.go并且额外增加了一个Insert方法。Int64Slice实现sort.InterfaceLen/Less/Swap并提供Sort()原地排序Search(x int64) int二分查找返回不低于 x 的最小下标调用方需自行判断该位置是否恰为 xSearchExists(x)基于 Search 的判存在未排序时行为未定义Insert(x)把 x 插入已排序切片中的正确位置并返回新切片若已存在则原样返回Insert。Int64Slice还被 rangetree 内部用作维度坐标缓存见 immutable.go 的newCache是库内复用度较高的基础件。Threadsafe锁包装的线程安全组件threadsafe 包的思路很直接给一些常见接口加锁使其可被多 goroutine 并发访问。文档为此辩护道虽然 Go 官方建议忘掉锁、用 channel但 channel 本质上是锁的高级抽象且在某些多 goroutine 共同写一块内存的场景里channel 既丑又慢又没必要。目前包内唯一的实现是 threadsafe/err 的Error结构用sync.RWMutex保护一个error字段提供Set(err error)与Get() error方便多 goroutine 并发地向同一个错误变量写入比如并行任务的第一个错误。注意该包注释已标记Deprecated建议改用golang.org/x/sync/errgroup或atomic.Pointer[error]——新代码可优先考虑这些替代方案。结语与未来方向Going Forward文档结尾勾勒了作者的长期规划仓库已存在 B 树相关 PR本仓库 btree 目录下已有 palm、plus、immutable 等变体B 树 位数组这两块拼图齐备后就有条件写一个原生的 Go 数据库。这也是为什么文档中位数组是构建原生 Go 数据库所需的两件东西之一的伏笔在这里回收。对使用者的建议同样写在文档里这些数据结构是大量程序与算法即使它们常被上层库抽象隐藏的地基欢迎任何人提交优化与 bug 修复。阅读完本文后你可以按需深入各子包源码——例如区间查询场景看 augmentedtree、集合运算看 bitarray、并发广播看 futures、goroutine 间协调看 queue、n 维点查询看 rangetree、图算法底层层看 fibheap——每处都有对应的_test.go测试文件可以对照验证行为。赞分享开发工具【免费下载链接】go-datastructuresA collection of useful, performant, and threadsafe Go datastructures.项目地址https://gitcode.com/gh_mirrors/go/go-datastructures点击查看免费下载相关推荐二叉堆与斐波那契堆性能对比数据结构选择的终极指南二叉堆与斐波那契堆性能对比数据结构选择的终极指南 在算法和数据结构的世界中堆与优先队列是实现高效操作的关键工具。今天我们将深入探讨两种重要的堆实现二叉堆和示例工程Floccus跨浏览器书签同步完整操作手册打造你的私有书签云Floccus跨浏览器书签同步完整操作手册打造你的私有书签云 在当今多设备、多浏览器的数字生活中书签同步已成为现代互联网用户的核心需求。Floccus作为一前端移动开发数据同步《程序员数学斐波那契》——为什么不能用斐波那契散列做数据库路由算法《程序员数学斐波那契》——为什么不能用斐波那契散列做数据库路由算法 导读斐波那契数列不只是面试题里的递归经典案例它在 JDK 源码中催生了 Thread文档教程后端上一篇FcaNet频率通道注意力网络如何用离散余弦变换提升深度学习模型性能下一篇Kimi Code 自动权限模式Auto Permission Mode指南从进入提醒到源码级运行机制创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考