17

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.

3 Answers 3

19
  1. The language spec doesn't say, which means that it's free to change at any time, or differ between implementations.

  2. 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.

  3. All of this stuff is in private functions, so no, you can't access Go's internal hash for a value in your own code.
3
  • How are hashes of structs made? Does it hash the struct contents as one linear chunk of memory? How about strings? Does it hash the string data itself or the internal struct representation which is a pointer and length? Would a hash of two strings which store the same byte sequence but in a different location result in equal or inequal hashes? Aug 18, 2017 at 2:45
  • @thomasrutter if two things compare equal with == 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.
    – hobbs
    Aug 18, 2017 at 4:21
  • Thanks for the link Aug 18, 2017 at 6:03
8

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.

5

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.

Your Answer

Reminder: Answers generated by Artificial Intelligence tools are not allowed on Stack Overflow. Learn more

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.