How Go Hashes Map Keys: AES-NI, wyhash and the Seed

TL;DR: Go hashes map keys with an AES-NI instruction sequence when the CPU has AES, SSSE3 and SSE4.1, and with a wyhash-inspired scalar function everywhere else. Both paths mix in two secrets: a process-wide key generated at startup and a fresh random seed per map, which is regenerated whenever the map empties out so an attacker cannot keep colliding keys.

Hashing is the part of a hash map that everybody assumes is magic and nobody looks at. It is also the part where a language has to make two opposing promises: a hash must be fast, because you do it on every operation, and a hash must be unpredictable, because an adversary who can predict it can turn your map into a linked list.

Go has solved this twice, and in the current tree (Go 1.28 development) both solutions live in src/internal/runtime/maps. This is a walk through them.

Which hash function, for which key

First, the key type decides the hash function, and that decision is made by the compiler, at compile time, not at runtime:

go
// src/cmd/compile/internal/reflectdata/alg.go:23
func genhash(t *types.Type) *obj.LSym {
	return genhashSig(eqSignature(t))
}

func genhashSig(sig string) *obj.LSym {
	if len(sig) > 0 && sig[0] == sigAlign {
		_, sig = parseNum(sig[1:])
	}
	switch sig {
	case "":
		return sysClosure("memhash0")
	case string(sigMemory) + "1":
		return sysClosure("memhash8")
	case string(sigMemory) + "2":
		return sysClosure("memhash16")
	case string(sigMemory) + "4":
		return sysClosure("memhash32")
	case string(sigMemory) + "8":
		return sysClosure("memhash64")
	case string(sigMemory) + "16":
		return sysClosure("memhash128")
	case string(sigString):
		return sysClosure("strhash")
	case string(sigIface):
		return sysClosure("interhash")
	case string(sigEface):
		return sysClosure("nilinterhash")
	case string(sigFloat32):
		return sysClosure("f32hash")
	case string(sigFloat64):
		return sysClosure("f64hash")
	case string(sigFloat32) + string(sigFloat32):
		return sysClosure("c64hash")
	case string(sigFloat64) + string(sigFloat64):
		return sysClosure("c128hash")

So a map[string]int uses runtime.strhash, a map[int64]int uses runtime.memhash64, a map[struct{...}]int gets a compiler-generated function that mixes the fields, and so on. These are not the old aeshashbody / aeshashstr assembly routines you may remember from the Go 1.20 source tree; the whole hashing stack moved into the maps package, and the runtime keeps thin shims for compatibility:

go
// src/runtime/alg.go:79
//go:nosplit
//go:linkname memhash
func memhash(p unsafe.Pointer, h, s uintptr) uintptr {
	return maps.MemHash(p, h, s)
}

//go:nosplit
func memhash64(p unsafe.Pointer, seed uintptr) uintptr {
	return maps.MemHash64(readUnaligned64(p), seed)
}

//go:nosplit
func memhash32(p unsafe.Pointer, seed uintptr) uintptr {
	return maps.MemHash32(readUnaligned32(p), seed)
}

Two secrets, not one

The most important thing to understand about Go’s hashing is that there are two independent sources of randomness, and every hash mixes both.

The first is process-wide, generated once at startup from the runtime’s bootstrap randomness source:

go
// src/internal/runtime/maps/runtime_alg.go:36
const hashRandomBytes = goarch.PtrSize / 4 * 64

// used to seed the hash function
var aeskeysched [hashRandomBytes]byte

// used in hash{32,64}.go to seed the hash function
var hashkey [4]uintptr

// Pre-computed comparisons against MinAeshashSize, which reduces a
// load-and-compare-and-branch to a load-and-branch.
var (
	useAeshash32 bool // = MinAeshashSize <= 4
	useAeshash64 bool // = MinAeshashSize <= 8
)

hashkey is the secret for the scalar path; aeskeysched is the AES key schedule for the hardware path.

The second secret is per map, and it is what makes hash flooding impractical. Every map gets a fresh random seed when it is created:

go
// src/internal/runtime/maps/map.go:350
func NewEmptyMap() *Map {
	m := new(Map)
	m.seed = uintptr(rand())
	// See comment in NewMap. No need to eager allocate a group.
	return m
}

rand() is the runtime’s per-M ChaCha8 generator, not math/rand:

go
// src/runtime/rand.go:163
func rand() uint64 {
	// Note: We avoid acquirem here so that in the fast path
	// there is just a getg, an inlined c.Next, and a return.
	// The performance difference on a 16-core AMD is
	// 3.7ns/call this way versus 4.3ns/call with acquirem (+16%).
	mp := getg().m
	c := &mp.chacha8
	for {
		// Note: c.Next is marked nosplit,
		// so we don't need to use mp.locks
		// on the fast path, which is that the
		// first attempt succeeds.
		x, ok := c.Next()
		if ok {
			return x
		}
		mp.locks++ // hold m even though c.Refill may do stack split checks
		c.Refill()
		mp.locks--
	}
}

The seed is not permanent, either. When a map empties out, or is cleared, the seed is replaced:

go
// src/internal/runtime/maps/map.go:695
	if m.used == 0 {
		// Reset the hash seed to make it more difficult for attackers
		// to repeatedly trigger hash collisions. See
		// https://go.dev/issue/25237.
		m.seed = uintptr(rand())
	}

That is the whole defence against hash-flooding denial of service. An attacker who submits a million colliding keys costs you a million-element lookup; but the collisions only work for the current seed, and the seed changes when the map empties, so the attacker has to keep the map non-empty to keep the collisions alive — and a non-empty map costs you memory anyway. The upstream issue is go.dev/issue/25237.

Choosing an implementation at startup

Which hash gets used is decided once, at process start, by looking at the CPU features:

go
// src/internal/runtime/maps/runtime_alg.go:51
func AlgInit() {
	// Always intialize hashkey.
	//
	// See #78073
	for i := range hashkey {
		hashkey[i] = uintptr(bootstrapRand())
	}

	// Install AES hash algorithms if the instructions needed are present.
	if (goarch.GOARCH == "386" || goarch.GOARCH == "amd64") &&
		cpu.X86.HasAES && // AESENC
		cpu.X86.HasSSSE3 && // PSHUFB
		cpu.X86.HasSSE41 { // PINSR{D,Q}

		// In memHashAES we have global variables that should be properly aligned.
		//
		// See #12415
		if !checkMasksAndShiftsAlignment() {
			fatal("maps: global variables for AES hashing are not properly aligned!")
		}
		initAlgAES()

		if memHashUsesVAES && !cpu.X86.HasAVX {
			// We are using intrinsics hash implementation.
			// Override the UseAeshash in this case, since it uses VAES (AVX) instructions.
			// While assembly implementation used AES-NI instructions,
			// simd intrinsics only provide access to AVX ones.
			MinAeshashSize = ^uintptr(0)
		}
	} else if goarch.GOARCH == "arm64" && cpu.ARM64.HasAES {
		initAlgAES()
	}

	useAeshash32 = 4 >= MinAeshashSize
	useAeshash64 = 8 >= MinAeshashSize
}

Three CPU features are required: AESENC for the encryption rounds, PSHUFB for the byte shuffling at the end of a short block, and PINSRD/PINSRQ to build the seed register. That is why the very first AMD Athlons and any pre-2011 x86 chip falls back to the scalar path.

AlgInit is called from runtime/proc.go during scheduler bring-up, after cpuinit and before anything can use a map.

The size threshold

The AES path is only worth taking for big enough inputs. The vector instructions have a fixed latency, and for a four-byte key that latency costs more than it saves. So there is a threshold, and it is measured, not guessed:

go
// src/internal/runtime/maps/runtime_alg.go:14
// MinAeshashSize is the smallest key size hashed with the AES-based
// implementation. Selecting hash is a size comparison against this value.
// Setting this to MaxUintptr disables AES altogether.
//
// When support is detected, the threshold is lowered to select between the
// scalar-based fallback hash and the vector-based AES hash. This value is
// selected on a per-platform basis based on what value produces the best
// benchmark results.
//
// Scalar hashes are faster on small values because it avoids taking a trip
// into the vector unit, which hurts latency (and for very small values,
// throughput).
var MinAeshashSize uintptr = ^uintptr(0)

go
// src/internal/runtime/maps/runtime_alg.go:88
func initAlgAES() {
	// TODO(mcy): investigate cutoffs on a per-uarch basis.
	// See memhash_bench_test.go.
	switch goarch.ArchFamily {
	case goarch.AMD64:
		// Measured on AMD Ryzen Threadripper PRO 7995WX (Zen4).
		MinAeshashSize = 9
	case goarch.ARM64:
		// Measured on Apple M1.
		// Latency crossover is at 192.
		MinAeshashSize = 16
	default:
		MinAeshashSize = 0
	}

	// Initialize with random data so hash collisions will be hard to engineer.
	key := (*[hashRandomBytes / 8]uint64)(unsafe.Pointer(&aeskeysched))
	for i := range key {
		key[i] = bootstrapRand()
	}
}

Here is the surprise: on amd64 the threshold is 9 bytes. That means the AES path is used for strings of 9 bytes or more — and not for 4-byte or 8-byte integer keys, because useAeshash32 and useAeshash64 are computed as 4 >= MinAeshashSize and 8 >= MinAeshashSize, both false when the threshold is 9.

In other words: on a modern x86 laptop, map[int64]int does not use AES-NI. It uses the scalar wyhash-style function. Integer keys are hashed with a multiply-fold, not with the AES pipeline.

The dispatch

The generic entry point is short:

go
// src/internal/runtime/maps/memhash_aes.go:13
const memHashAESImplemented = true

func MemHash(p unsafe.Pointer, h, s uintptr) uintptr {
	if s >= MinAeshashSize {
		return memHashAES(p, h, s)
	}
	return memHashFallback(p, h, s)
}

func MemHash32(k uint32, h uintptr) uintptr {
	if useAeshash32 {
		return memHash32AES(k, h)
	}
	return memHash32Fallback(k, h)
}

func MemHash64(k uint64, h uintptr) uintptr {
	if useAeshash64 {
		return memHash64AES(k, h)
	}
	return memHash64Fallback(k, h)
}

func StrHash(s string, h uintptr) uintptr {
	return MemHash(unsafe.Pointer(unsafe.StringData(s)), h, uintptr(len(s)))
}

Note the h parameter: that is the per-map seed, threaded through from typ.Hasher(key, m.seed).

On architectures without AES at all, the same file shape exists but every AES entry point panics and everything falls back:

go
// src/internal/runtime/maps/memhash_noaes.go:13
// AES hashing not implemented for these architectures
const memHashAESImplemented = false
const memHashUsesVAES = false

func memHash32AES(k uint32, h uintptr) uintptr {
	panic("memHash32AES not implemented")
}

func memHash64AES(k uint64, h uintptr) uintptr {
	panic("memHash64AES not implemented")
}

func memHashAES(p unsafe.Pointer, h, s uintptr) uintptr {
	panic("memHashAES not implemented")
}

func MemHash(p unsafe.Pointer, h, s uintptr) uintptr {
	return memHashFallback(p, h, s)
}

func MemHash32(k uint32, h uintptr) uintptr {
	return memHash32Fallback(k, h)
}

func MemHash64(k uint64, h uintptr) uintptr {
	return memHash64Fallback(k, h)
}

The AES hash itself

The amd64 implementation is assembly, and the first thing it does is mix the per-map seed with the per-process key schedule:

asm
// src/internal/runtime/maps/memhash_amd64.s:7
// func memHashAES(p unsafe.Pointer, h, s uintptr) uintptr
// hash function using AES hardware instructions
TEXT ·memHashAES<ABIInternal>(SB),NOSPLIT,$0-32
	// AX: data
	// BX: hash seed
	// CX: length
	// At return: AX = return value

	// Fill an SSE register with our seeds.
	MOVQ	BX, X0				// 64 bits of per-table hash seed
	PINSRW	$4, CX, X0			// 16 bits of length
	PSHUFHW $0, X0, X0			// repeat length 4 times total
	MOVO	X0, X1				// save unscrambled seed
	PXOR	·aeskeysched(SB), X0	// xor in per-process seed
	AESENC	X0, X0				// scramble seed

	CMPQ	CX, $16
	JB	aes0to15
	JE	aes16
	CMPQ	CX, $32
	JBE	aes17to32
	CMPQ	CX, $64
	JBE	aes33to64
	CMPQ	CX, $128
	JBE	aes65to128
	JMP	aes129plus

The shape of the whole function is “one AES round to scramble the seed, then one AES round per 16 bytes of data, then fold the results together”. The seed is placed in the low 64 bits of an XMM register, the length is broadcast into the high bits, and the per-process key schedule is XORed in before the first round. Because the data is XORed with the scrambled seed before being encrypted, the hash depends on both the key bytes and the length.

The final fold for the long case looks like this:

asm
// src/internal/runtime/maps/memhash_amd64.s:335
	PXOR	X12, X8
	PXOR	X13, X9
	PXOR	X14, X10
	PXOR	X15, X11
	PXOR	X10, X8
	PXOR	X11, X9
	PXOR	X9, X8
	// X15 must be zero on return
	PXOR	X15, X15
	MOVQ	X8, AX	// return X8
	RET

Under the goexperiment.simd build, the same algorithm is expressed with intrinsics instead of assembly, using VAES:

go
// src/internal/runtime/maps/memhash_aes_simd.go:16
func memHash32AES(k uint32, seed uintptr) uintptr {
	var state archsimd.Uint64x2
	state = state.SetElem(0, uint64(seed)).SetElem(1, uint64(k))

	hash := state.
		AsUint8x16().
		AESEncryptOneRound(archsimd.LoadUint32x4Array((*[4]uint32)(unsafe.Pointer(&aeskeysched[0])))).
		AESEncryptOneRound(archsimd.LoadUint32x4Array((*[4]uint32)(unsafe.Pointer(&aeskeysched[16])))).
		AESEncryptOneRound(archsimd.LoadUint32x4Array((*[4]uint32)(unsafe.Pointer(&aeskeysched[32])))).
		AsUint64x2().
		GetElem(0)
	return uintptr(hash)
}

Because VAES is an AVX instruction, the runtime disables the AES path entirely on machines that have AES-NI but not AVX — you can see that override in AlgInit above.

The wyhash fallback

Everything that is not “long enough for AES” goes through a scalar function that is explicitly inspired by wyhash:

go
// src/internal/runtime/maps/runtime_hash64.go:17
const (
	m5 = 0x1d8e4e27c47d124f
)

func memHashFallback(p unsafe.Pointer, seed, s uintptr) uintptr {
	var a, b uintptr
	seed ^= hashkey[0]
	switch {
	case s == 0:
		return seed
	case s < 4:
		a = uintptr(*(*byte)(p))
		a |= uintptr(*(*byte)(add(p, s>>1))) << 8
		a |= uintptr(*(*byte)(add(p, s-1))) << 16
	case s == 4:
		a = r4(p)
		b = a
	case s < 8:
		a = r4(p)
		b = r4(add(p, s-4))
	case s == 8:
		a = r8(p)
		b = a
	case s <= 16:
		a = r8(p)
		b = r8(add(p, s-8))
	default:
		l := s
		if l > 48 {
			seed1 := seed
			seed2 := seed
			for ; l > 48; l -= 48 {
				seed = mix(r8(p)^hashkey[1], r8(add(p, 8))^seed)
				seed1 = mix(r8(add(p, 16))^hashkey[2], r8(add(p, 24))^seed1)
				seed2 = mix(r8(add(p, 32))^hashkey[3], r8(add(p, 40))^seed2)
				p = add(p, 48)
			}
			seed ^= seed1 ^ seed2
		}
		for ; l > 16; l -= 16 {
			seed = mix(r8(p)^hashkey[1], r8(add(p, 8))^seed)
			p = add(p, 16)
		}
		a = r8(add(p, l-16))
		b = r8(add(p, l-8))
	}

	return mix(m5^s, mix(a^hashkey[1], b^seed))
}

The structure is the classic wyhash shape: read the input as two 64-bit halves (overlapping for short inputs), mix them with a single 64x64 multiply, and fold in the length. The mix helper is literally one multiply:

go
// src/internal/runtime/maps/runtime_hash64.go:77
func mix(a, b uintptr) uintptr {
	hi, lo := bits.Mul64(uint64(a), uint64(b))
	return uintptr(hi ^ lo)
}

func r4(p unsafe.Pointer) uintptr {
	return uintptr(readUnaligned32(p))
}

func r8(p unsafe.Pointer) uintptr {
	return uintptr(readUnaligned64(p))
}

hi ^ lo of a 64x64->128 multiply is a very good avalanche for the price of one MULQ. The constant m5 is wyhash’s secret constant, and m5^s mixes the length into the final value so that "ab" and "ab\x00" do not hash the same.

Note seed ^= hashkey[0] on the very first line: the per-map seed is combined with the per-process secret before anything else happens.

On 32-bit platforms the same job is done with 32-bit halves:

go
// src/internal/runtime/maps/runtime_hash32.go:57
func mix32(a, b uint32) (uint32, uint32) {
	c := uint64(a^uint32(hashkey[1])) * uint64(b^uint32(hashkey[2]))
	return uint32(c), uint32(c >> 32)
}

A shortcut worth knowing about

The string fast path has one more trick. For long strings, Go compares a few bytes before hashing at all, and skips the hash entirely if there is an exact match:

go
// src/internal/runtime/maps/runtime_faststr.go:30
	// The 64 threshold was chosen based on performance of BenchmarkMapStringKeysEight,
	// where there are 8 keys to check, all of which don't quick-match the lookup key.
	// In that case, we can save hashing the lookup key. That savings is worth this extra code
	// for strings that are long enough that hashing is expensive.
	if len(key) > 64 {
		// String hashing and equality might be expensive. Do a quick check first.
		j := abi.MapGroupSlots
		for i := range abi.MapGroupSlots {
			if ctrls&(1<<7) == 0 && longStringQuickEqualityTest(key, *(*string)(slotKey)) {

Eight quick prefix comparisons, and if one of them hits, no hashing is needed at all. For a map with eight long string keys, that is the difference between hashing a 10 KB string and comparing a few dozen bytes.

Trade-offs

What the two-layer seeding buys:

Hash flooding is impractical. The per-map seed means the collisions an attacker found yesterday do not work today, and the seed rotates whenever the map empties.
The per-process secret means even a zero-seed map is not attackable. Two programs running the same binary do not produce the same hash for the same key.
The AES path is genuinely hard to invert. Three AES rounds per block with a random key schedule is not something you brute-force in a web request.

What it costs:

The hash of a key changes when the map’s seed changes. Any code that caches “hash of this key” outside the map is broken.
Two secrets means two places to get it wrong. The scalar path mixes hashkey[0..3]; the AES path mixes aeskeysched. They are separate mechanisms, and the compiler and runtime both rely on them agreeing.
The threshold is a benchmark result, not a law. MinAeshashSize = 9 on amd64 was measured on a Threadripper; a different microarchitecture might want a different number.
AES-NI is not universal. The feature bits have to be checked at startup, the key schedule has to be aligned in memory (there is an explicit runtime check for that), and the code has to be duplicated in assembly and in intrinsics.

Caveats

Do not use Go’s map hash as a content hash. It is seeded per map and per process; two runs of the same program will produce different values for the same key. If you need a stable hash, use hash/maphash (which is explicitly a stable hash) or crypto/sha256.

maphash.Hash and map keys use different mechanisms. maphash gives you a Seed you can keep and reuse, deliberately stable across a program’s lifetime. The map’s internal seed is not exposed and rotates.

The AES path is not used for small keys. If you were expecting AES-NI to be doing the work for map[int]int or map[int64]int, it is not — the threshold on amd64 is 9 bytes, and integer keys fall to the scalar path.

NaN keys are special. Float keys get a random hash component, because NaN is never equal to itself and would otherwise create unbounded chains:

go
// src/runtime/alg.go:118
func f32hash(p unsafe.Pointer, h uintptr) uintptr {
	f := *(*float32)(p)
	switch {
	case f == 0:
		return trimHash(c1 * (c0 ^ h)) // +0, -0
	case f != f:
		return trimHash(c1 * (c0 ^ h ^ uintptr(rand()))) // any kind of NaN
	default:
		return memhash(p, h, 4)
	}
}

The hash seed is not a defence against a determined attacker who can keep the map full. The protection is a cost trade: to keep the collisions working, the attacker has to keep a large non-empty map alive, which costs you memory. It raises the cost of the attack; it does not make it impossible.

Wasm uses 32-bit hashes. The hash size is fixed at compile time per platform, and on Wasm it is 4 bytes rather than 8.

Wrapping up

The one thing to remember: every map key hash mixes in two secrets — a process-wide key generated at startup and a per-map random seed — and the seed is replaced whenever the map empties or is cleared. That is why the same key hashes differently in two different maps, and differently again in the same map after a Clear.

The part people get wrong: assuming AES-NI hashes everything. On amd64 the AES path only kicks in at 9 bytes, so integer keys use the scalar wyhash-style multiply-fold function, and the AES key schedule is only one of the two secrets in play.

What to go do about it: if you are writing code that depends on hash values, use hash/maphash explicitly rather than relying on the map’s internal hash. If you are benchmarking, remember that the map’s hash cost depends on the key size: a map[string] with long keys can skip hashing entirely on a prefix match, while a map[int64] never uses AES at all.