Struct Map

map.go:283–312

Map is an unordered map from keys to values with Put, Get, Delete, and All operations. Map is inspired by Google's Swiss Tables design as implemented in Abseil's flat_hash_map, combined with extendible hashing. By default, a Map[K,V] uses the same hash function as Go's builtin map[K]V, though a diff

//
// A Map is NOT goroutine-safe.
type Map[K comparable, V any] struct {
	// The hash function to each keys of type K. The hash function is
	// extracted from the Go runtime's implementation of map[K]struct{}.
	hash hashFn
	seed uintptr
	// The allocator to use for the ctrls and slots slices.
	allocator Allocator[K, V]
	// bucket0 is always present and inlined in the Map to avoid a pointer
	// indirection during the common case that the map contains a single
	// bucket. bucket0 is also used during split operations as a temporary
	// bucket to split into before the bucket is installed in the directory.
	bucket0 bucket[K, V]
	// The directory of buckets. See the comment on bucket.index for details
	// on how the physical bucket values map to logical buckets.
	dir unsafeSlice[bucket[K, V]]
	// The number of filled slots across all buckets (i.e. the number of
	// elements in the map).
	used int
	// globalShift is the number of bits to right shift a hash value to
	// generate an index for the global directory. As a special case, if
	// globalShift==0 then bucket0 is used and the directory is not accessed.
	// Note that globalShift==(64-globalDepth). globalShift is used rather
	// than globalDepth because the shifting is the more common operation than
	// needing to compare globalDepth to a bucket's localDepth.
	globalShift uint32
	// The maximum capacity a bucket is allowed to grow to before it will be
	// split.
	maxBucketCapacity uint32
	_                 noCopy
}

// normalizeCapacity rounds capacity to the next power of 2.
func normalizeCapacity(capacity uint32) uint32 {