// 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 hashed import ( ) // 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.) type Map[, any] struct { seed maphash.Seed table map[uint64][]entry[, ] // maps hash to entries of that hash len int // number of map entries hasher maphash.Hasher[] _ noCopy } // NewMap returns a new map that uses the specified hash // function and key-equivalence relation. func [, any]( maphash.Hasher[]) *Map[, ] { var Map[, ] .init() return & } type entry[, any] struct { used bool key value } 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 } var hashPool = sync.Pool{ New: func() any { return new(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[, ] { _ = .len return func( 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[, ] { var Map[, ] .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[] { _ = .len return func( 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[] { _ = .len return func( 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 { := false for , := 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 } } else if == 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 { := .len for , := 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 { var strings.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 { return fmtsort.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. type noCopy struct{} // Lock is a no-op used by -copylocks checker from `go vet`. func (*noCopy) () {} func (*noCopy) () {}