Go's maps are famously implemented as hash tables, which is the only reasonable choice. The implementation has gotten somewhat more complicated since I looked at how maps store their values and keys due to the move to swiss tables , and these days you find the comments about how they work in internal/runtime/maps/map.go , but the core is still the same. Recently, a documentation commit landed in the Go development tree that opened my eyes to a bit of subtle complexity I hadn't considered before in Go's map implementation.

One of the things about hash tables is that they hash the value of keys down to some fixed size value in order to do operations more efficiently; in Go's current swiss tables , this is a 64-bit hash. Critically, the hash value of a key must be constant (which can be an issue in languages like Python that let you define a hash function at user level). You also want the actual value of keys to (only) compare equal when they are equal, which can also be a challenge in a language with user defined comparison functions, or just if you're dealing with NaNs .

Go has a quite broad definition of what's allowed as map keys; you can use any type that has == and != comparison operators defined. This includes pointers (which are directly comparable), arrays of pointers, and structs containing pointers (under the rule that a struct is comparable if all its fields are). However, Go pointers aren't guaranteed to be constant values, and today growing and shrinking a goroutine's stack will change some pointer values . This is a potential problem if you're hashing the current integer value of a pointer as part of a Go map key hash; you need that hash value to stay constant.

The documentation commit explains how Go deals with this today, primarily in its comment in map.go . When a Go value is stored as a map key, the Go compiler marks that value as 'escaping' , which means that the value will be allocated in the heap instead of on the stack (along with anything it points to). Currently things in the heap never move, so once a key value is heap allocated, any pointers involved have a constant value and the key's hash value will never change.

As the comment notes, this is only done for keys that are getting stored in the map. Keys used for lookup or for delete will never be stored and so don't need to be specifically heap allocated. As the comment also notes:

If we are looking up a pointer which points to the stack, the hash value is ~irrelevant, as the key is guaranteed to not be in the map [...].

(This includes pointers in structs and so on.)

This map key hash stability requirement is a bit of a subtle constraint on any future Go garbage collector that works through copying values around ( eg , also ). Probably the simplest way to deal with it would be to mark heap pointers involved in map keys and then never copy or otherwise move them. Possibly you could do this on the fly during the garbage collection scanning process, since you need to trace through maps in general to mark their keys and values as used.

(Until I stumbled over this commit message and read into it more, I'd never thought about how the hash table stability requirement might clash with any sort of moving garbage collection mechanism.)