Skip to content

proposal: container/hash: Map, a generic hash table with custom hash function and equivalence relation #69559

@adonovan

Description

@adonovan

(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:

Metadata

Metadata

Assignees

No one assigned

    Labels

    Type

    No type

    Projects

    Status

    Active

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions