// Copyright 2026 The Go Authors. All rights reserved.// Use of this source code is governed by a BSD-style// license that can be found in the LICENSE file.
// Package hashed defines hash-based containers such as [Map].
package hashedimport ()// Map[K, V] is a hash-table based mapping from keys K to values V,// using the hash function and key-equivalence relation specified// at construction.//// A Map must be created with [NewMap].// Neither a nil pointer nor the zero value are valid maps.//// Map values must not be copied; use [Map.Clone] instead.//// Do not use Map with a comparable key type K and its usual ==// equivalence relation; instead, use Go's built-in map type.// (If you need set operations such as Union and Intersection,// use the helpers in the collection/set package.)typeMap[, any] struct {seedmaphash.Seedtablemap[uint64][]entry[, ] // maps hash to entries of that hashlenint// number of map entrieshashermaphash.Hasher[] _ noCopy}// NewMap returns a new map that uses the specified hash// function and key-equivalence relation.func [, any]( maphash.Hasher[]) *Map[, ] {varMap[, ] .init()return &}typeentry[, any] struct {usedboolkeyvalue}func ( *Map[, ]) ( maphash.Hasher[]) { .seed = maphash.MakeSeed() .table = make(map[uint64][]entry[, ]) .hasher = }// hash returns the hash of the specified key.func ( *Map[, ]) ( ) uint64 {// Because the m.hasher.Hash(h) call is dynamic, // escape analysis is conservative, causing Hash h to escape. // To amortize allocation, we recycle Hashes using a sync.Pool. // // (Even if we had expressed the hasher type as an additional // type parameter, it would not have been sufficient to cause // escape analysis to stack-allocate h.) := hashPool.Get().(*maphash.Hash) .SetSeed(.seed) .hasher.Hash(, ) := .Sum64()hashPool.Put()return}varhashPool = sync.Pool{New: func() any { returnnew(maphash.Hash) },}// Len returns the number of map entries.func ( *Map[, ]) () int {return .len}// All returns an iterator over the key/value entries of the map in// unspecified order.//// It is safe to modify the map during iteration. As with the built-in// map, if a key is removed during iteration, its entry will not be// yielded by the iterator. If a key is added during iteration, it may// or may not be yielded by the iterator. The iterator yields the// value most recently associated with a given key.func ( *Map[, ]) () iter.Seq2[, ] { _ = .lenreturnfunc( func(, ) bool) {// Iterate by hash key to dynamically evaluate bucket slice length. // This avoids holding a stale slice header if a concurrent or // nested Set reallocates the bucket, matching built-in map semantics.for := range .table {for := 0; < len(.table[]); ++ { := &.table[][]if .used && !(.key, .value) {return } } } }}// Clone returns a new non-nil map with the same entries as m.func ( *Map[, ]) () *Map[, ] {varMap[, ] .cloneFrom()return &}func ( *Map[, ]) ( *Map[, ]) { * = Map[, ]{hasher: .hasher,seed: .seed,table: make(map[uint64][]entry[, ]), } .setAll(.All())}// Keys returns an iterator over the keys of the map in random order.//// It is safe to modify the map during iteration, with the same// semantics as the [Map.All] iterator.func ( *Map[, ]) () iter.Seq[] { _ = .lenreturnfunc( func() bool) {// Iterate by hash key to dynamically evaluate bucket slice length. // This safely handles additions/reallocations during iteration.for := range .table {for := 0; < len(.table[]); ++ { := &.table[][]if .used && !(.key) {return } } } }}// Values returns an iterator over the values of the map in random order.//// It is safe to modify the map during iteration, with the same// semantics as the [Map.All] iterator.func ( *Map[, ]) () iter.Seq[] { _ = .lenreturnfunc( func() bool) {// Iterate by hash key to dynamically evaluate bucket slice length. // This safely handles additions/reallocations during iteration.for := range .table {for := 0; < len(.table[]); ++ { := &.table[][]if .used && !(.value) {return } } } }}// Delete removes the entry with the given key, if present.// It returns the previous value for key if present, or the zero value if not.// The boolean (deleted) indicates whether the operation deleted a map entry.func ( *Map[, ]) ( ) ( , bool) { := .table[.hash()]for , := range {if .used && .hasher.Equal(, .key) {// We can't compact the bucket as it // would disturb iterators. := .value [] = entry[, ]{} .len--return , true } }return *new(), false}// DeleteFunc removes each map entry for which del returns true.// It reports whether the map changed.func ( *Map[, ]) ( func(, ) bool) bool { := falsefor , := range .All() {if (, ) {if , := .Delete(); { = true } } }return}// Lookup reports whether the map contains the specified key, and returns// the corresponding value if found, or the zero value if not.func ( *Map[, ]) ( ) (, bool) {for , := range .table[.hash()] {if .used && .hasher.Equal(, .key) {return .value, true } }return *new(), false}// Get returns the value corresponding the given key,// or the zero value if the entry is not present.func ( *Map[, ]) ( ) { , := .Lookup()return}// Contains reports whether the map contains an entry with the given key.func ( *Map[, ]) ( ) bool { , := .Lookup()return}// Set updates the map entry for key to value.// It returns the previous value for key if present, or the zero value if not.// The boolean (present) indicates whether the operation updated an existing entry// for that key.func ( *Map[, ]) ( , ) ( , bool) { := .hash() := .table[]var *entry[, ]for := range { := &[]if .used {if .hasher.Equal(, .key) { = .value .key = .value = return , true } } elseif == nil { = } }if != nil { * = entry[, ]{true, , } // overwrite deleted entry } else { .table[] = append(, entry[, ]{true, , }) } .len++return , false}// setAll calls Set(k, v) for each key/value pair in the sequence.// It reports whether the number of map entries increased.func ( *Map[, ]) ( iter.Seq2[, ]) bool { := .lenfor , := range { .Set(, ) }return .len > }// Clear removes all entries from the map.func ( *Map[, ]) () {clear(.table) .len = 0}// String returns a string representation of the map's entries// in an unspecified but deterministic order.//// Keys and values are printed as if by [fmt.Sprint].func ( *Map[, ]) () string {varstrings.Builder .WriteByte('{')// Sort the entries by their shallow representation, // using the same logic as fmt.Sprint(map). := make([]*entry[, ], 0, .Len())for , := range .table {for , := range {if .used { = append(, &[]) } } }slices.SortStableFunc(, func(, *entry[, ]) int {returnfmtsort.Compare(reflect.ValueOf(.key), reflect.ValueOf(.key)) })for , := range {if > 0 { .WriteString(", ") }fmt.Fprintf(&, "%v: %v", .key, .value) } .WriteByte('}')return .String()}// noCopy may be added to structs which must not be copied// after the first use.//// See https://golang.org/issues/8005#issuecomment-190753527// for details.//// Note that it must not be embedded, due to the Lock and Unlock methods.typenoCopystruct{}// Lock is a no-op used by -copylocks checker from `go vet`.func (*noCopy) () {}func (*noCopy) () {}
The pages are generated with Goldsv0.8.7. (GOOS=linux GOARCH=amd64)