问题引入
1 | type Key struct { |
运行上面的代码，我们会得到一个panic：
1 | panic: runtime error: hash of unhashable type map[string]interface {} |
原因是因为，当使用map存储时，key要求是可以计算hash值的，而在go中，map、slice、channel和func类型都是不能计算hash值的，因此当使用这些类型作为map的key时会发生panic，而当key是复合类型，并且包含了这四种类型，也会发生panic，如上面的例子中，如果包含了接口类型，那么在运行时会动态检查其类型。
具体实现
接下来，我们来看一下go是如何给map的key计算hash值的。
首先，我们先看一下map中关于hash的计算逻辑：
1 | alg := t.key.alg // 这里的t是maptype |
接下来看一下maptype的结构定义：
1 | // maptype表示一个map的类型 |
go中所有的类型对应的元类型声明都是：1
2
3
4type xxxtype struct {
typ _type
...
}
而_type中的alg字段，声明了用于计算该类型的hash函数和用于比较的比较函数。
而在runtime/alg.go中，列出了一些预先定义的的alg：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16var algarray = [alg_max]typeAlg{
alg_NOEQ: {nil, nil}, // 表示没有hash方法和equal方法
alg_MEM0: {memhash0, memequal0},
alg_MEM8: {memhash8, memequal8},
alg_MEM16: {memhash16, memequal16},
alg_MEM32: {memhash32, memequal32},
alg_MEM64: {memhash64, memequal64},
alg_MEM128: {memhash128, memequal128},
alg_STRING: {strhash, strequal},
alg_INTER: {interhash, interequal}, // iface的hash和equal
alg_NILINTER: {nilinterhash, nilinterequal}, // eface的hash和equal
alg_FLOAT32: {f32hash, f32equal},
alg_FLOAT64: {f64hash, f64equal},
alg_CPLX64: {c64hash, c64equal},
alg_CPLX128: {c128hash, c128equal},
}
我们就其中几个例子来感受一下：
计算eface的hash：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27func nilinterhash(p unsafe.Pointer, h uintptr) uintptr {
a := (*eface)(p) // p实际上就是一个空接口指针
t := a._type
if t == nil {
return h
}
// 使用实际类型的hash方法来计算
fn := t.alg.hash
// 如果没有hash方法，表明该类型不支持计算hash，比如slice、map或者func
if fn == nil {
// 这里的panic不就跟上面例子中的panic一样嘛
panic(errorString("hash of unhashable type " + t.string()))
}
// isDirectIface如果返回true，表示这个接口存的实际是一个指针值
if isDirectIface(t) {
// v:= &struct{...}
// i:=(interface{})(v)
// 这时候是这种情况，使用指针v的值计算hash
return c1 * fn(unsafe.Pointer(&a.data), h^c0)
} else {
// v:= struct{...}
// i:=(interface{})(v)
// 这时候是这种情况，对结构体计算hash
return c1 * fn(a.data, h^c0)
}
}
eface的equal：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26func nilinterequal(p, q unsafe.Pointer) bool {
x := *(*eface)(p)
y := *(*eface)(q)
// 首先比较他们的类型是否一致
return x._type == y._type && efaceeq(x._type, x.data, y.data)
}
func efaceeq(t *_type, x, y unsafe.Pointer) bool {
if t == nil {
return true
}
// 然后调用实际类型的equal方法
eq := t.alg.equal
if eq == nil {
panic(errorString("comparing uncomparable type " + t.string()))
}
if isDirectIface(t) {
// Direct interface types are ptr, chan, map, func, and single-element structs/arrays thereof.
// Maps and funcs are not comparable, so they can't reach here.
// Ptrs, chans, and single-element items can be compared directly using ==.
// 我们代码中得到的chan实际上就是一个ptr，chan的比较实际上就是比较地址
return x == y
}
return eq(x, y)
}
字符串的hash1
2
3
4
5func strhash(a unsafe.Pointer, h uintptr) uintptr {
x := (*stringStruct)(a)
// str指向底层字节数组，使用底层字节数组的内容计算hash
return memhash(x.str, h, uintptr(x.len))
}
接下来，我们看一下文章开头例子反编译后的汇编代码，我们主要是要看一下Key类型的hash方法
首先，看一下Key的类型元信息：
1 | type."".Key SRODATA size=144 |
接着来看一下汇编生成的type..hash."".Key方法，这里只保留主要逻辑
我们首先回顾一下该struct的声明：1
2
3
4type Key struct {
a int
eface interface{}
}
对应hash方法的代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17// 首先该函数有两个参数p和h，p表示要hash的对象指针，h表示hash seek，返回一个hash值
TEXT type..hash."".Key(SB), DUPOK|ABIInternal, $40-24
MOVQ "".p+48(SP), AX // 调用hash时传入的指针p，*Key类型
MOVQ AX, (SP) // memhash第一个参数，实际上是 Key.a 的地址
MOVQ "".h+56(SP), CX
MOVQ CX, 8(SP) // memhash第二个参数，调用hash时传入的seed
MOVQ $8, 16(SP) // memhash第三个参数，因为字段a是int类型，在64位平台上占用8个字节
CALL runtime.memhash(SB) // 调用memhash计算hash值
MOVQ 24(SP), AX // 将返回值保存到ax中
MOVQ "".p+48(SP), CX
ADDQ $8, CX // 这里指针计算，p+8对应的就是Key.eface
MOVQ CX, (SP) // nilinterhash第一个参数
MOVQ AX, 8(SP) // 将前面对 a 计算的hash作为seed传入
CALL runtime.nilinterhash(SB) // 调用nilinterhash
MOVQ 16(SP), AX // 返回值mov到ax
MOVQ AX, "".~r2+64(SP) // 设置返回值
RET
直接看上面的逻辑，当计算Key的hash时，首先对key.a进行hash，然后将结果作为nilinterhash的第二个参数seed，计算eface的hash值，得到最终的hash值。
那么开头我们的例子中，运行的结果是panic，因此说明在nilinterhash中，因此对应的type没有hash方法而导致panic，为了验证我们的结论，我们看下map[string]interface{}{}对应的_type中的alg
1 | func main() { |
查看编译后的汇编代码：
1 | type.map[string]interface {} SRODATA dupok size=80 |