Background: The Go Collections working group was formed in late 2025 with the purpose of bringing common collection data structures to the standard library, guided by the familiar Go principles of pragmatism and simplicity. Alphabetically by last name, the group consists of Jonathan Amsterdam (@jba), Alan Donovan (@adonovan), Robert Griesemer (@griesemer), Daniel Martí (@mvdan), Roger Peppe (@rogpeppe), Keith Randall (@khr), and Ian Lance Taylor (@ianlancetaylor). We’ve now reached a point where we’re ready to share our results with the community.
This issue is an umbrella for discussing several related proposals for new collections APIs for Go 1.28. It presents a high level overview of the themes, and links to the various concrete proposals and associated implementation CLs.
Go currently provides few collection types in its library, and from the outset we have emphasized the flexibility of the language’s built-in slice and map types. Of those provided, the most important is the heap, used for priority queues. Even sets are absent; they are conventionally expressed in terms of map[T]bool or map[T]struct{}. Ordered maps and sets based on binary trees are entirely absent.
Since the addition of generics in Go 1.18 and iterators in Go 1.23, it has become possible for library-defined types to achieve comparable ergonomics to built-in types, and for many common operations on slices and maps to be expressed as calls to library functions. This work seeks to add several of the more important data types to the standard library, and to establish conventions for their APIs and those of future additions.
Proposal: The proposed additions include:
#70471, CL 657296 (released in go1.27): hash/maphash.Hasher: a standard interface for expressing custom hash functions and equivalence relations for arbitrary data types. These may differ from the compiler-defined ones used by map[K]V, and are useful when the key type is not comparable (such as a slice or map), or when the default comparison yields the wrong result (such as for types.Type values, which need the deep comparison operation types.Identical). Its package docs include an example of its use in a Bloom filter.
#69559, CL 612217: container/hash.Map[K,V]: a hash-based Map that uses the custom hash functions mentioned above.
#80584, CL 741160: container/hash.Set[T]: a hash-based Set along the same lines.
#69230, CL 745441: container/set.Set[T]: a canonical data type for sets whose elements are comparable. It is transparently represented as map[T]struct{} and supports all the usual set operations such as Union and Intersection. It is more convenient than “legacy” sets based on map[T]bool and map[T]struct{}, and avoids ambiguity about potential false values in a map[T]bool. We expect it to become the standard set in most new Go APIs.
#77052, CL 724420: container/mapset: a package of helper functions (Union, Intersection, and so on) for conveniently manipulating legacy sets as sets in existing code whose API cannot be changed. These functions are exactly parallel to the methods of set.Set.
#60630: container/ordered.Map[K,V]: an ordered mapping. The current implementation uses a balanced binary tree, but nothing in the design requires that. The common Go pattern of building a map[K]V then sorting its keys performs well in most cases, but on occasion, such as when a range query is needed, other data structures perform much better.
#77397: container/heap/v2.Heap: a generic binary heap API to replace the standard library's existing heap, which can be difficult to use.
We expect to consider additional proposals in due course, such as insertion-ordered hash maps (#80194) and stacks.
The initial implementations of all the proposed data structures aim to satisfy the API and asymptotic performance expectations as simply as possible. There are doubtless many opportunities for later optimizations to reduce constant factors, but they are out of scope of the proposal process.
Though the new packages will live in the existing container tree, we prefer the term “collection” to avoid confusion with the container virtualization concept from Linux.
Abstract collection constraint interfaces
Most of the methods of the new Map and Set types are not particular to any concrete representation type, but are common across all Maps and Sets. However, they are not really implementions of a common interface type because of the “binary method problem”: if each set data type S has a Union method of the form func (S) Union(S) S, then the Union methods of different set types are incompatible, so they have no common ordinary interface. To express this abstract Set type, we must use F-bounded polymorphism, or recursive constraint interfaces.
CL 761460 adds to the container package unexported abstract Collection, Set, and Map constraint interface types that permit package implementors to write abstract helper functions (such as ContainsAny, Subset, or Arbitrary) that work across a range of concrete collection, set or map types. We reproduce these interfaces below, with some brief commentary, to help give a high-level picture but they are not part of any proposal. They merely serve to guarantee conformance in tests. See the individual proposals for more detail.
// _AbstractCollection models a collection C of elements E,
// such as *hash.Map, *hash.Set, *ordered.Map, or set.Set.
type _AbstractCollection[E any, C _AbstractCollection[E, C]] interface {
Clear()
Clone() C
Contains(E) bool
ContainsAll(iter.Seq[E]) bool
Len() int
String() string
}
// _AbstractMap models a mapping M from keys K to values V,
// such as *hash.Map or *ordered.Map.
type _AbstractMap[K, V any, M _AbstractMap[K, V, M]] interface {
_AbstractCollection[K, M]
All() iter.Seq2\[K, V\]
At(K) V
Delete(K) (V, bool)
DeleteAll(iter.Seq\[K\]) bool
DeleteFunc(func(K, V) bool) bool
Get(K) (V, bool)
Keys() iter.Seq\[K\]
Set(K, V) (V, bool)
SetAll(iter.Seq2\[K, V\]) bool
Values() iter.Seq\[V\]
}
// _AbstractSet models a set S of elements E,
// such as *hash.Set, or set.Set.
type _AbstractSet[E any, S _AbstractSet[E, S]] interface {
_AbstractCollection[E, S]
All() iter.Seq\[E\]
Delete(E) bool
DeleteAll(iter.Seq\[E\]) bool
DeleteFunc(func(E) bool) bool
Difference(S) S
DifferenceWith(S)
Equal(S) bool
Insert(E) bool
InsertAll(iter.Seq\[E\]) bool
Intersection(S) S
IntersectionWith(S)
Intersects(S) bool
SymmetricDifference(S) S
SymmetricDifferenceWith(S)
Union(S) S
UnionWith(S)
}
For now these abstract types are non-exported and merely serve as documentation of Go’s conventions to help ensure consistency. We do not propose to publish them yet, but may do so a later release after gaining experience with the concrete collection types. In the meantime, users can define minimal constraint types as needed, as in this example (from CL 761460) of a generic Take function over abstract sets:
// _TakeSet defines an abstraction of a set sufficient for the [Take] function.
type _TakeSet[E any, S _TakeSet[E, S]] interface {
All() iter.Seq[E]
Delete(E) bool
}
// Take removes and returns an arbitrary element from a set.
// It returns zero if the set was empty.
func Take[S _TakeSet[E, S], E any](set S) (e E, found bool) {
for e = range set.All() {
found = true
set.Delete(e)
break
}
return
}
There is a certain arbitrariness to the set of methods included in each interface. For some data structures, a method permits a more efficient specialized implementation. But if every possible operation were added to the interface, the burden on the implementor would be unreasonable.
For instance, should the Set interface include a Subset(Set) bool method, or should Subset be written as a generic operation over abstract sets, like the Take example? Ordered sets can quickly reject a Subset test when the two operands have disjoint ranges, but even so, in the common case a Subset test is still typically O(n), so we decided to omit Subset from the interface. By contrast, we retained DeleteFunc in the Set and Map interfaces because, without it, conditionally deleting each element of a tree is asymptotically worse: O(n log n) instead of O(n).
By delaying the commitment to a particular set of methods, we can learn from practice. It may turn out that we don’t need to publish canonical constraint types at all.
Miscellaneous rationalizations
The remainder of this doc briefly notes a few of the many small design choices that led to the current set of proposals.
Methods return as much information as possible to avoid repeated lookups. For example:
- Most mutation methods report whether they changed the size of the collection.
- Map.Set and Map.Delete return the previous key if any, plus a boolean so that an existing key can be distinguished from the zero value.
- Get is variant of At that provides the boolean. (At is provided for convenience of use in expressions.)
Map.Set should replace any existing entry with the same key, following the built-in map.
Unlike Sets, maps have no Equal method, because map values may be non-comparable.
The fundamental set operations (Intersects, Union, etc) are part of the Set interface to enable efficient concrete implementations across a variety of representations, even though many of these could be expressed abstractly in terms of just All, Len, and Contains, as shown in this table, at some asymptotic cost in performance:
- Union{,With} interface{ All() iter.Seq\[E\] }
- Intersection interface{ All() iter.Seq\[E\]; Contains(E) bool; Len() int }
- IntersectionWith interface{ Contains(E) bool }
- Difference interface{ All() iter.Seq\[E\]; Contains(E) bool }
- DifferenceWith interface{ All() iter.Seq\[E\]; Contains(E) bool }
- SymmetricDifference{,With} interface{ All() iter.Seq\[E\] }
Secondary operations such as Set.{Take,Arbitrary,Subset,Superset} were removed from the interface and expressed as generic operations using the abstract set interface, again at some potential cost in asymptotic performance. DeleteFunc was retained.
Set algebra operations such as Union are purely functional, returning their result as a new set. Each comes with a -With variant that mutates its left operand and returns no result. The two variants are “convenient” and “allocation efficient”, respectively. We rejected the idea of merging them into a single method based on experience with the math/big.Int API, and to avoid risks of accidental mutation or forgetting to use the result.
It is possible to define a KeySetView[M, K, V] wrapper type that satisfies the Set[K] abstraction using the key set of an underlying Map[K,V] of type M. (Inserting an element to the Set is of course meaningless and must panic.)
For symmetry, let’s consider each of the AbstractMap methods and the operations provided by the existing ‘maps’ package:
- no maps.Clear: served by builtin clear(m)
- AbstractMap.Clone = maps.Clone
- no maps.Contains; served by _, ok = m[k]; but see proposal #67377
- no maps.ContainsAll: served efficiently by for k := range seq { _, ok = m[k], … }
- no maps.Len: served by builtin len(m)
- AbstractMaps.All = maps.All
- no maps.At: served by m[k]
- no maps.Delete: served by delete(m, k)
- no maps.DeleteAll: served efficiently by for k = range seq { delete(m, k) }
- AbstractMaps.DeleteFunc = maps.DeleteFunc
- no maps.Get: served by v, ok = m[k]
- AbstractMaps.Keys = maps.Keys
- no maps.Set: served by prev, ok = m[k]; m[k] = newval
- AbstractMap.SetAll = maps.Insert
- AbstractMaps.Values = maps.Values
Five of them (Clone, DeleteFunc, All, Keys, Values) are exactly parallel. One operation (AbstractMap.SetAll) has a different name (maps.Insert). All the rest are served by built-in operators.
We might want to propose adding maps.{Contains,ContainsAll,DeleteAll}. Contains is more useful than _, ok = s[k] in an expression context; ContainsAll and DeleteAll avoid the need for loops and boolean bookkeeping.
Instagram Engineering
Shopify Engineering