Go的map使用实践

初始化

使用 map 的时候需要注意，你需要显式地初始化才能对 map 进行操作.

1
2


var m map[string]string
m["a"]="sssss"

上面的代码会报 panic: assignment to entry in nil map ，必须用内建的 make() 函数才行.

1
2


m:=make(map[string]string)
m["a"]="sssss"

key

key类型

Go 语言中只要是可比较的类型都可以作为 key。除开 slice，map，functions 这几种类型，其他类型都是 OK 的。具体包括：布尔值、数字、字符串、指针、通道、接口类型、结构体、只包含上述类型的数组。这些类型的共同特征是支持 == 和 != 操作符，k1 == k2 时，可认为 k1 和 k2 是同一个 key。如果是结构体，则需要它们的字段值都相等，才被认为是相同的 key。

map中的key可以是任何的类型，只要它的值能比较是否相等，Go的语言规范已精确定义，Key的类型可以是：

布尔值
数字
字符串
指针
通道
接口类型
结构体(struct必须是可比较的，才能作为key，否则编译时报错)

只包含上述类型的数组。

但不能是：

slice
map
function

Key类型只要能支持 == 和 != 操作符，即可以做为Key，当两个值==时，则认为是同一个Key。

比较相等

我们先看一下样例代码：

 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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68


package main

import "fmt"

type _key struct {
}

type point struct {
	x int
	y int
}

type pair struct {
	x int
	y int
}

type Sumer interface {
	Sum() int
}

type Suber interface {
	Sub() int
}

func (p *pair) Sum() int {
	return p.x + p.y
}

func (p *point) Sum() int {
	return p.x + p.y
}

func (p pair) Sub() int {
	return p.x - p.y
}

func (p point) Sub() int {
	return p.x - p.y
}

func main() {
	fmt.Println("_key{} == _key{}: ", _key{} == _key{}) // output: true

	fmt.Println("point{} == point{}: ", point{x: 1, y: 2} == point{x: 1, y: 2})     // output: true
	fmt.Println("&point{} == &point{}: ", &point{x: 1, y: 2} == &point{x: 1, y: 2}) // output: false

	fmt.Println("[2]point{} == [2]point{}: ",
	  [2]point{point{x: 1, y: 2}, point{x: 2, y: 3}} == [2]point{point{x: 1, y: 2}, point{x: 2, y: 3}}) //output: true

	var a Sumer = &pair{x: 1, y: 2}
	var a1 Sumer = &pair{x: 1, y: 2}
	var b Sumer = &point{x: 1, y: 2}
	fmt.Println("Sumer.byptr == Sumer.byptr: ", a == b)        // output: false
	fmt.Println("Sumer.sametype == Sumer.sametype: ", a == a1) // output: false

	var c Suber = pair{x: 1, y: 2}
	var d Suber = point{x: 1, y: 2}
	var d1 point = point{x: 1, y: 2}
	fmt.Println("Suber.byvalue == Suber.byvalue: ", c == d)  // output: false
	fmt.Println("Suber.byvalue == point.byvalue: ", d == d1) // output: true

	ci1 := make(chan int, 1)
	ci2 := ci1
	ci3 := make(chan int, 1)
	fmt.Println("chan int == chan int: ", ci1 == ci2) // output: true
	fmt.Println("chan int == chan int: ", ci1 == ci3) // output: false
}

上面的例子让我们较直观地了解结构体，数组，指针，chan在什么场景下是相等。我们再来看Go语言规范中是怎么说的：

Pointer values are comparable. Two pointer values are equal if they point to the same variable or if both have value nil. Pointers to distinct zero-size variables may or may not be equal.当指针指向同一变量，或同为nil时指针相等，但指针指向不同的零值时可能不相等。
Channel values are comparable. Two channel values are equal if they were created by the same call to make or if both have value nil.Channel当指向同一个make创建的或同为nil时才相等
Interface values are comparable. Two interface values are equal if they have identical dynamic types and equal dynamic values or if both have value nil.从上面的例子我们可以看出，当接口有相同的动态类型并且有相同的动态值，或者值为都为nil时相等。
A value x of non-interface type X and a value t of interface type T are comparable when values of type X are comparable and X implements T. They are equal if t’s dynamic type is identical to X and t’s dynamic value is equal to x.如果一个是非接口类型X的变量x，也实现了接口T，与另一个接口T的变量t，只t的动态类型也是类型X，并且他们的动态值相同，则他们相等。
Struct values are comparable if all their fields are comparable. Two struct values are equal if their corresponding non-blank fields are equal.结构体当所有字段的值相同，并且没有相应的非空白字段时，则他们相等，
Array values are comparable if values of the array element type are comparable. Two array values are equal if their corresponding elements are equal.两个数组只要他们包括的元素，每个元素的值相同，则他们相等。

注意：Go语言里是无法重载操作符的，struct是递归操作每个成员变量，struct也可以称为map的key，但如果struct的成员变量里有不能进行==操作的，例如slice，那么就不能作为map的key。

类型判断

判断两个变量是否相等，首先是要判断变量的动态类型是否相同，在runtime中，_type结构是描述最为基础的类型（runtime/type.go），而map, slice, array等内置的复杂类型也都有对应的类型描述（如maptype，slicetype，arraytype）。

 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


type _type struct {
	size       uintptr
	ptrdata    uintptr
	hash       uint32
	tflag      tflag
	align      uint8
	fieldalign uint8
	kind       uint8
	alg        *typeAlg
	gcdata    *byte
	str       nameOff
	ptrToThis typeOff
}
...
type chantype struct {
	typ  _type
	elem *_type
	dir  uintptr
}
...
type slicetype struct {
	typ  _type
	elem *_type
}
...

其中对于类型的值是否相等，需要使用到成员alg *typeAlg(runtime/alg.go)，它则持有此类型值的hash与equal的算法，它也是一个结构体:

1
2
3
4
5
6
7
8


type typeAlg struct {
	// function for hashing objects of this type
	// (ptr to object, seed) -> hash
	hash func(unsafe.Pointer, uintptr) uintptr
	// function for comparing objects of this type
	// (ptr to object A, ptr to object B) -> ==?
	equal func(unsafe.Pointer, unsafe.Pointer) bool
}

runtime/alg.go中提供了各种基础的hash func与 equal func，例如：

1
2
3
4
5
6
7
8


func strhash(a unsafe.Pointer, h uintptr) uintptr {
	x := (*stringStruct)(a)
	return memhash(x.str, h, uintptr(x.len))
}

func strequal(p, q unsafe.Pointer) bool {
	return *(*string)(p) == *(*string)(q)
}

有了这些基础的hash func与 equal func，再复杂的结构体也可以按字段递归计算hash与相等比较了。那我们再来看一下，当访问map[key]时，其实现对应在runtime/hashmap.go中的mapaccess1函数:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
	...
	alg := t.key.alg
	hash := alg.hash(key, uintptr(h.hash0)) // 1
	m := uintptr(1)<<h.B - 1
	b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize))) // 2
	...
	top := uint8(hash >> (sys.PtrSize*8 - 8))
	if top < minTopHash {
		top += minTopHash
	}
	for {
		for i := uintptr(0); i < bucketCnt; i++ {
			...
			k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
			if alg.equal(key, k) { // 3
				v := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))
				...
				return v
			}
		}
	...
	}
}

mapaccess1的代码还是比较多的，简化逻辑如下（参考注释上序列）：

调用key类型的hash方法，计算出key的hash值
根据hash值找到对应的桶bucket
在桶中找到key值相等的map的value。判断相等需调用key类型的equal方法

到现在我们也就有了初步了解，map中的key访问时同时需要使用该类型的hash func与 equal func，只要key值相等，当结构体即使不是同一对象，也可从map中获取相同的值，例如：

1
2
3
4
5


m := make(map[interface{}]interface{})
m[_key{}] = "value"
if v, ok := m[_key{}];ok {
	fmt.Println("%v", v) // output: value
}

key可以是float型吗

从语法上看，是可以的。

来看个例子：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


func main() {
	m := make(map[float64]int)
	m[1.4] = 1
	m[2.4] = 2
	m[math.NaN()] = 3
	m[math.NaN()] = 3

	for k, v := range m {
		fmt.Printf("[%v, %d] ", k, v)
	}

	fmt.Printf("\nk: %v, v: %d\n", math.NaN(), m[math.NaN()])
	fmt.Printf("k: %v, v: %d\n", 2.400000000001, m[2.400000000001])
	fmt.Printf("k: %v, v: %d\n", 2.4000000000000000000000001, m[2.4000000000000000000000001])

	fmt.Println(math.NaN() == math.NaN())
}

程序的输出：

1
2
3
4
5


[2.4, 2] [NaN, 3] [NaN, 3] [1.4, 1]
k: NaN, v: 0
k: 2.400000000001, v: 0
k: 2.4, v: 2
false

例子中定义了一个 key 类型是 float 型的 map，并向其中插入了 4 个 key：1.4， 2.4， NAN，NAN。

打印的时候也打印出了 4 个 key，如果你知道 NAN != NAN，也就不奇怪了。因为他们比较的结果不相等，自然，在 map 看来就是两个不同的 key 了。

接着，我们查询了几个 key，发现 NAN 不存在，2.400000000001 也不存在，而 2.4000000000000000000000001 却存在。

有点诡异，不是吗？

接着，我通过汇编发现了如下的事实：

当用 float64 作为 key 的时候，先要将其转成 unit64 类型，再插入 key 中。

具体是通过 Float64frombits 函数完成：

1
2
3


// Float64frombits returns the floating point number corresponding
// the IEEE 754 binary representation b.
func Float64frombits(b uint64) float64 { return *(*float64)(unsafe.Pointer(&b)) }

也就是将浮点数表示成 IEEE 754 规定的格式。如赋值语句：

1
2
3
4


0x00bd 00189 (test18.go:9)      LEAQ    "".statictmp_0(SB), DX
0x00c4 00196 (test18.go:9)      MOVQ    DX, 16(SP)
0x00c9 00201 (test18.go:9)      PCDATA  $0, $2
0x00c9 00201 (test18.go:9)      CALL    runtime.mapassign(SB)

"".statictmp_0(SB) 变量是这样的：

1
2
3
4
5
6


"".statictmp_0 SRODATA size=8
        0x0000 33 33 33 33 33 33 03 40
"".statictmp_1 SRODATA size=8
        0x0000 ff 3b 33 33 33 33 03 40
"".statictmp_2 SRODATA size=8
        0x0000 33 33 33 33 33 33 03 40

我们再来输出点东西：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


package main

import (
	"fmt"
	"math"
)

func main() {
	m := make(map[float64]int)
	m[2.4] = 2

    fmt.Println(math.Float64bits(2.4))
	fmt.Println(math.Float64bits(2.400000000001))
	fmt.Println(math.Float64bits(2.4000000000000000000000001))
}

1
2
3


4612586738352864255
4612586738352862003
4612586738352862003

转成十六进制为：

1
2
3


0x4003333333333333
0x4003333333333BFF
0x4003333333333333

和前面的 “".statictmp_0 比较一下，很清晰了吧。2.4 和 2.4000000000000000000000001 经过 math.Float64bits() 函数转换后的结果是一样的。自然，二者在 map 看来，就是同一个 key 了。

再来看一下 NAN（not a number）：

1
2


// NaN returns an IEEE 754 ``not-a-number'' value.
func NaN() float64 { return Float64frombits(uvnan) }

uvan 的定义为：

1

uvnan    = 0x7FF8000000000001

NAN() 直接调用 Float64frombits，传入写死的 const 型变量 0x7FF8000000000001，得到 NAN 型值。既然，NAN 是从一个常量解析得来的，为什么插入 map 时，会被认为是不同的 key？

这是由类型的哈希函数决定的，例如，对于 64 位的浮点数，它的哈希函数如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


func f64hash(p unsafe.Pointer, h uintptr) uintptr {
	f := *(*float64)(p)
	switch {
	case f == 0:
		return c1 * (c0 ^ h) // +0, -0
	case f != f:
		return c1 * (c0 ^ h ^ uintptr(fastrand())) // any kind of NaN
	default:
		return memhash(p, h, 8)
	}
}

第二个 case，f != f 就是针对 NAN，这里会再加一个随机数。

这样，所有的谜题都解开了。

由于 NAN 的特性：

1
2


NAN != NAN
hash(NAN) != hash(NAN)

因此向 map 中查找的 key 为 NAN 时，什么也查不到；如果向其中增加了 4 次 NAN，遍历会得到 4 个 NAN。

最后说结论：float 型可以作为 key，但是由于精度的问题，会导致一些诡异的问题，慎用之。

value

任何类型都可以作为 value，包括 map 类型。

value不可达

看一个例子:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


package main

import "fmt"

type user struct {
    name string
    age  int
    school map[string]school
}

type school struct {
    Teacher string
    Name string
}

func main() {
    s := map[string]school{"primarySchool":{Teacher:"李老师", Name:"XX小学"}, "highSchool":{Teacher:"曹老师", Name:"XX中学"}}
    u := user{name:"张三",age:12,school:s}
    u.school["highSchool"].Name = "XX第二中学"//错误
    fmt.Println(u)
}

1

cannot assign to struct field u.school["highSchool"].Name in map

原因出在user 中的 map[string]school 这里， u.school[“highSchool”] 访问到这里都没有问题，问题在于后面的 “ .Name ” ，因为map[string]school 中储存的school是值拷贝，当要修改school里面的Name时，就发生了不可寻址的错误。

正确的做法有：

重新覆盖，既然无法单独修改里面的某一项，那就全部都替换掉，u.school[“highSchool”] = school{Teacher:“曹老师”, Name:“XX第二中学”}
改为储存指针，把map[string]school 改为 map[string]*school，把school的指针存进去，这样go就可以寻址，从而可以修改里面的值

多维map

用到了一个二维 map，结果第一遍写的时候就碰到了那个 nil map 的问题。

一开始的代码是这样的：

1
2


m:=make(map[string]map[string]string)
m["a"]["b"]="ccc"

后来才想明白如果插新加入的元素也是个 map 的话需要再次 make()或初始化,修正后的代码如下

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


package main

import "fmt"

func main() {
	m := make(map[int]map[int]int)
	m[0] = map[int]int{1: 3} //重新make或直接初始化
	m[0][3] = 2 //正确
	fmt.Println(m[0])
}

参考

http://lanlingzi.cn/post/technical/2016/0904_go_map/

https://barbery.me/post/2014-08-06-go%E5%A4%9A%E7%BB%B4map%E8%AF%BB%E5%86%99%E6%93%8D%E4%BD%9C%E7%9A%84%E9%97%AE%E9%A2%98/

文章目录

初始化

key