Golang提案：container/：通用集合类型

背景：Go Collections 工作组于 2025 年底成立，旨在以熟悉的 Go 实用主义和简单性原则为指导，将通用的集合数据结构引入标准库。按姓氏字母顺序排列，该小组由乔纳森·阿姆斯特丹 (@jba)、艾伦·多诺万 (@adonovan)、罗伯特·格里塞默 (@griesemer)、丹尼尔·马蒂 (@mvdan)、罗杰·佩佩 (@rogpeppe)、基思·兰德尔 (@khr) 和伊恩·兰斯·泰勒 (@ianlancetaylor) 组成。我们现在已经准备好与社区分享我们的成果了。本期主要讨论 Go 1.28 的新集合 API 的几个相关提案。它提供了主题的高级概述，以及各种具体提案和相关实施 CL 的链接。 Go 目前在其库中提供了很少的集合类型，从一开始我们就强调了该语言内置切片和映射类型的灵活性。在提供的这些中，最重要的是堆，用于优先级队列。连套装都没有；它们通常用map[T]bool 或map[T]struct{} 表示。基于二叉树的有序映射和集合完全不存在。自从 Go 1.18 中添加泛型和 Go 1.23 中添加迭代器以来，库定义类型已经可以实现与内置类型相当的人体工程学，并且切片和映射上的许多常见操作可以表示为对库函数的调用。这项工作旨在将几种更重要的数据类型添加到标准库中，并为其 API 和未来添加的 API 建立约定。提案：建议添加的内容包括：#70471、CL 657296（在 go1.27 中发布）：hash/maphash.Hasher：用于表达任意数据类型的自定义哈希函数和等价关系的标准接口。这些可能与 map[K]V 使用的编译器定义的不同，并且当键类型不可比较（例如切片或映射）时，或者当默认比较产生错误结果时（例如对于 types.Type 值，需要深度比较操作 types.Identical ），它们很有用。它的包文档包括在布隆过滤器中使用它的示例。 #69559，CL 612217：container/hash.Map[K,V]：使用上面提到的自定义哈希函数的基于哈希的 Map。 #80584 ， CL 741160 ：container/hash.Set[T] ：基于哈希的 Set 沿着相同的路线。 #69230，CL 745441：container/set.Set[T]：元素可比较的集合的规范数据类型。它透明地表示为map[T]struct{}，并支持所有常用的集合操作，例如并集和交集。它比基于map[T]bool 和map[T]struct{} 的“遗留”集更方便，并且避免了map[T]bool 中潜在错误值的歧义。我们期望它成为大多数新 Go API 中的标准集。 #77052、CL 724420：容器/地图集：辅助函数包（并集、交集等），用于方便地将旧集操作为现有代码中的集（其 API 无法更改）。这些函数与 set.Set 的方法完全并行。 #60630：container/ordered.Map[K,V]：有序映射。当前的实现使用平衡二叉树，但设计中没有任何要求。在大多数情况下，构建 map[K]V 然后对其键进行排序的常见 Go 模式表现良好，但有时，例如需要范围查询时，其他数据结构的表现要好得多。 #77397：container/heap/v2.Heap：一个通用的二进制堆 API，用于替换标准库现有的堆，该堆可能很难使用。我们希望在适当的时候考虑其他建议，例如插入顺序哈希映射（#80194）和堆栈。所有提出的数据结构的初始实现旨在尽可能简单地满足 API 和渐近性能期望。毫无疑问，后期优化有很多机会来减少常数因素，但它们超出了提案流程的范围。尽管新包将存在于现有的容器树中，但我们更喜欢使用术语“集合”，以避免与 Linux 中的容器虚拟化概念混淆。抽象集合约束接口 新Map 和Set 类型的大多数方法并不特定于任何具体表示类型，而是在所有Map 和Set 中通用。然而，由于“二元方法问题”，它们并不是公共接口类型的真正实现：如果每个集合数据类型 S 都有一个 func (S) Union(S) S 形式的 Union 方法，那么不同集合类型的 Union 方法是不兼容的，因此它们没有公共的普通接口。为了表达这个抽象的 Set 类型，我们必须使用 F-bounded 多态性，或者递归约束接口。 CL 761460 向容器包添加了未导出的抽象 Collection、Set 和 Map 约束接口类型，这些类型允许包实现者编写适用于工作的抽象辅助函数（例如 ContainsAny、Subset 或 Arbitrary）。