How does Go calculate a hash for keys in a map? Is it truly unique and is it available for use in other structures?
I imagine it's easy for primitive keys like int
or immutable string
but it seems nontrivial for composite structures.
The language spec doesn't say, which means that it's free to change at any time, or differ between implementations.
The hash algorithm varies somewhat between types and platforms. As of now: On x86 (32 or 64 bit) if the CPU supports AES instructions, the runtime uses aeshash
, a hash built on AES primitives, otherwise it uses a function "inspired by" xxHash and cityhash, but different from either. There are different variants for 32-bit and 64-bit systems. Most types use a simple hash of their memory contents, but floating-point types have code to ensure that 0 and -0 hash equally (since they compare equally) and NaNs hash randomly (since two NaNs are never equal). Since complex types are built from floats, their hashes are composed from the hashes of their two floating-point parts. And an interface's hash is the hash of the value stored in the interface, and not the interface header itself.
==
they must have equal hashes (or maps wouldn't work... this is also the reasoning behind all of the special cases I outlined above). That means that strings hash their bodies, not their headers. And structs compose the hashes of all of their fields. I can't find the code actually implementing that, but the tests and the comparison rules make it clear.
The Go map implementation uses a hash called aeshash
. It's not AES, but it uses the aesenc assembly instruction to compute hashes. This hash isn't exported for use in the standard library.
The hash itself is written in assembly, and can be found in the runtime package source.
Since Go 1.14, the go standard library provides the hash/maphash package. The hash functions in this package aren't guaranteed to be the same ones used by Go maps (but it appears that they are, which makes sense); they are guaranteed to be good functions for implementing hashmaps and the like.
hash/maphash only operates on strings or byte slices, so it's still up to you to figure out how to serialize a composite data structure into bytes for hashing purposes.