-
Notifications
You must be signed in to change notification settings - Fork 18.3k
Open
Description
(API in this note updated Jun 18 2025 --adonovan.)
Background: In #69420 I proposed to promote the golang.org/x/tools/go/types/typeutil.Map data type to the go/types package, modernizing it with generics. @jimmyfrasche pointed out that really the only part of that proposal that needs to be in go/types is the types.Hash
function, which should have semantics consistent with types.Identical
: that is, identical types must have equal hashes. So, I reduced that proposal to just the hash function, and this proposal governs the table.
Proposal: the standard library should provide a generic hash table that allows the user to specify the hash function and equivalence relation. Here is a starting point for the API:
package hash // "container/hash"
import "iter"
// Map[K, V, H] is a mapping from keys of type K to values of type V,
// using key-equivalence relation H.
type Map[K, V any, H maphash.Hasher[K]] struct { ... }
// NewMap returns a new mapping.
type NewMap[K, V any, H maphash.Hasher[K]]() *Map[K, V, K]
// All returns an iterator over the key/value entries of the map in undefined order.
func (m *Map[K, V]) All() iter.Seq2[K, V]
// At returns the map entry for the given key. It returns zero if the entry is not present.
func (m *Map[K, V]) At(key K) V
// Delete removes th//e entry with the given key, if any. It returns true if the entry was found.
func (m *Map[K, V]) Delete(key K) bool
// Keys returns an iterator over the map keys in unspecified order.
func (m *Map[K, V]) Keys() iter.Seq[K]
// Values returns an iterator over the map values in unspecified order.
func (m *Map[K, V]) Values() iter.Seq[V]
// Len returns the number of map entries.
func (m *Map[K, V]) Len() int
// Set updates the map entry for key to value, and returns the previous entry, if any.
func (m *Map[K, V]) Set(key K, value V) (prev V)
// String returns a string representation of the map's entries in unspecified order.
// Values are printed as if by fmt.Sprint.
func (m *Map[K, V]) String() string
Open questions:
- Should At and Set distinguish the "present but zero" and "missing" cases?
- Should we defend against hash flooding, complicating the hash function? (Decision: yes)
- Should we guarantee randomized iteration order?
Related:
- go/types: add Hasher{,IgnoreTags} types #69420
- proposal: container: add tree-based ordered.Map/Set #60630, its ordered cousin. The APIs should harmonize.
- proposal: container/set: new package to provide a generic set type #69230, a generic set type. Again the APIs should harmonize.
mateusz834, jimmyfrasche, tdakkota, DeedleFake, crossworth and 9 more
Metadata
Metadata
Assignees
Labels
Type
Projects
Status
Active