go中的数据结构字典-map
1. map的使用
golang中的map是一种数据类型，将键与值绑定到一起，底层是用哈希表实现的，可以快速的通过键找到对应的值。
类型表示：map[keyType][valueType] key一定要是可比较的类型（可以理解为支持==的操作），value可以是任意类型。
初始化：map只能使用make来初始化，声明的时候默认为一个为nil的map，此时进行取值，返回的是对应类型的零值（不存在也是返回零值）。添加元素无任何意义，还会导致运行时错误。向未初始化的map赋值引起 panic: assign to entry in nil map。
复制代码
1 package main
2
3 import (
4 "fmt"
5 )
6
7 // bool 的零值是false
8 var m map[int]bool
9 a, ok := m[1]
10 fmt.Println(a, ok) // false false
11
12 // int 的零值是0
13 var m map[int]int
14 a, ok := m[1]
15 fmt.Println(a, ok) // 0 false
16
17
18 func main() {
19 var agemap[string]int
20 if age== nil {
21 fmt.Println("map is nil.")
22 age= make(map[string]int)
23 }
24 }
复制代码
清空map：对于一个有一定数据的集合 exp，清空的办法就是再次初始化: exp = make(map[string]int)，如果后期不再使用该map，则可以直接：exp= nil 即可，但是如果还需要重复使用，则必须进行make初始化，否则无法为nil的map添加任何内容。
属性：与切片一样，map 是引用类型。当一个 map 赋值给一个新的变量，它们都指向同一个内部数据结构。因此改变其中一个也会反映到另一个。作为形参或返回参数的时候，传递的是地址的拷贝，扩容时也不会改变这个地址。
复制代码
1 func main() {
2 exp := map[string]int{
3 "steve": 20,
4 "jamie": 80,
5 }
6 fmt.Println("Ori exp", age)
7 newexp:= exp
8 newexp["steve"] = 18
9 fmt.Println("exp changed", exp)
10 }
11
12 //Ori age map[steve:20 jamie:80]
13 //age changed map[steve:18 jamie:80]
复制代码
遍历map：map本身是无序的，在遍历的时候并不会按照你传入的顺序，进行传出。
复制代码
1 //正常遍历：
2 for k, v := range exp {
3 fmt.Println(k, v)
4 }
5
6 //有序遍历
7 import "sort"
8 var keys []string
9 // 把key单独抽取出来，放在数组中
10 for k, _ := range exp {
11 keys = append(keys, k)
12 }
13 // 进行数组的排序
14 sort.Strings(keys)
15 // 遍历数组就是有序的了
16 for _, k := range keys {
17 fmt.Println(k, m[k])
18 }
复制代码
2. map的结构
Go中的map在可以在 $GOROOT/src/runtime/map.go找到它的实现。哈希表的数据结构中一些关键的域如下所示：
复制代码
1 type hmap struct {
2 count int //元素个数
3 flags uint8
4 B uint8 //扩容常量
5 noverflow uint16 //溢出 bucket 个数
6 hash0 uint32 //hash 种子
7 buckets unsafe.Pointer //bucket 数组指针
8 oldbuckets unsafe.Pointer //扩容时旧的buckets 数组指针
9 nevacuate uintptr //扩容搬迁进度
10 extra *mapextra //记录溢出相关
11 }
12
13 type bmap struct {
14 tophash [bucketCnt]uint8
15 // Followed by bucketCnt keys
16 //and then bucketan Cnt values
17 // Followed by overflow pointer.
18 }
复制代码
说明：每个map的底层都是hmap结构体，它是由若干个描述hmap结构体的元素、数组指针、extra等组成，buckets数组指针指向由若干个bucket组成的数组，其每个bucket里存放的是key-value数据(通常是8个)和overflow字段（指向下一个bmap），每个key插入时会根据hash算法归到同一个bucket中，当一个bucket中的元素超过8个的时候，hmap会使用extra中的overflow来扩展存储key。
图中len 就是当前map的元素个数，也就是len()返回的值。也是结构体中hmap.count的值。bucket array是指数组指针，指向bucket数组。hash seed 哈希种子。overflow指向下一个bucket。
map的底层主要是由三个结构构成:
hmap --- map的最外层的数据结构，包括了map的各种基础信息、如大小、bucket，一个大的结构体。
mapextra --- 记录map的额外信息，hmap结构体里的extra指针指向的结构，例如overflow bucket。
bmap --- 代表bucket，每一个bucket最多放8个kv，最后由一个overflow字段指向下一个bmap，注意key、value、overflow字段都不显示定义，而是通过maptype计算偏移获取的。
mapextra的结构如下
复制代码
1 // mapextra holds fields that are not present on all maps.
2 type mapextra struct {
3 // If both key and value do not contain pointers and are inline, then we mark bucket
4 // type as containing no pointers. This avoids scanning such maps.
5 // However, bmap.overflow is a pointer. In order to keep overflow buckets
6 // alive, we store pointers to all overflow buckets in hmap.extra.overflow and hmap.extra.oldoverflow.
7 // overflow and oldoverflow are only used if key and value do not contain pointers.
8 // overflow contains overflow buckets for hmap.buckets.
9 // oldoverflow contains overflow buckets for hmap.oldbuckets.
10 // The indirection allows to store a pointer to the slice in hiter.
11 overflow *[]*bmap
12 oldoverflow *[]*bmap
13
14 // nextOverflow holds a pointer to a free overflow bucket.
15 nextOverflow *bmap
16 }
复制代码
其中hmap.extra.nextOverflow指向的是预分配的overflow bucket，预分配的用完了那么值就变成nil。
bmap的详细结构如下
在map中出现哈希冲突时，首先以bmap为最小粒度挂载，一个bmap累积8个kv之后，就会申请一个新的bmap（overflow bucket）挂在这个bmap的后面形成链表，优先用预分配的overflow bucket，如果预分配的用完了，那么就malloc一个挂上去。这样减少对象数量，减轻管理内存的负担，利于gc。注意golang的map不会shrink，内存只会越用越多，overflow bucket中的key全删了也不会释放。
bmap中所有key存在一块，所有value存在一块，这样做方便内存对齐。当key大于128字节时，bucket的key字段存储的会是指针，指向key的实际内容；value也是一样。
hash值的高8位存储在bucket中的tophash字段。每个桶最多放8个kv对，所以tophash类型是数组[8]uint8。把高八位存储起来，这样不用完整比较key就能过滤掉不符合的key，加快查询速度。实际上当hash值的高八位小于常量minTopHash时，会加上minTopHash，区间[0, minTophash)的值用于特殊标记。查找key时，计算hash值，用hash值的高八位在tophash中查找，有tophash相等的，再去比较key值是否相同。
复制代码
1 type typeAlg struct {
2 // function for hashing objects of this type
3 // (ptr to object, seed) -> hash
4 hash func(unsafe.Pointer, uintptr) uintptr
5 // function for comparing objects of this type
6 // (ptr to object A, ptr to object B) -> ==?
7 equal func(unsafe.Pointer, unsafe.Pointer) bool
8
9 // tophash calculates the tophash value for hash.
10 func tophash(hash uintptr) uint8 {
11 top := uint8(hash >> (sys.PtrSize*8 - 8))
12 if top < minTopHash {
13 top += minTopHash
14 }
15 return top
16 }
复制代码
golang为每个类型定义了类型描述器_type，并实现了hashable类型的_type.alg.hash和_type.alg.equal，以支持map的范型，定义了这类key用什么hash函数、bucket的大小、怎么比较之类的，通过这个变量来实现范型。
3. map的基本操作
3.1 map的创建
复制代码
1 //makemap为make（map [k] v，hint）实现Go map创建。
2 //如果编译器已确定映射或第一个存储桶,可以在堆栈上创建，hmap或bucket可以为非nil。
3 //如果h！= nil，则可以直接在h中创建map。
4 //如果h.buckets！= nil，则指向的存储桶可以用作第一个存储桶。
5 func makemap(t *maptype, hint int, h *hmap) *hmap {
6 if hint < 0 || hint > int(maxSliceCap(t.bucket.size)) {
7 hint = 0
8 }
9
10 // 初始化Hmap
11 if h == nil {
12 h = new(hmap)
13 }
14 h.hash0 = fastrand()
15
16 // 查找将保存请求的元素数的size参数
17 B := uint8(0)
18 for overLoadFactor(hint, B) {
19 B++
20 }
21 h.B = B
22
23 // 分配初始哈希表
24 // if B == 0, 稍后会延迟分配buckets字段（在mapassign中）
25 //如果提示很大，则将内存清零可能需要一段时间。
26 if h.B != 0 {
27 var nextOverflow *bmap
28 h.buckets, nextOverflow = makeBucketArray(t, h.B, nil)
29 if nextOverflow != nil {
30 h.extra = new(mapextra)
31 h.extra.nextOverflow = nextOverflow
32 }
33 }
34
35 return h
36 }
复制代码
hint是一个启发值，启发初建map时创建多少个bucket，如果hint是0那么就先不分配bucket，lazy分配。大概流程就是初始化hmap结构体、设置一下hash seed、bucket数量、实际申请bucket、申请mapextra结构体之类的。
申请buckets的过程：
复制代码
1 // makeBucketArray初始化地图存储区的后备数组。
2 // 1 << b是要分配的最小存储桶数。
3 // dirtyalloc之前应该为nil或bucket数组
4 //由makeBucketArray使用相同的t和b参数分配。
5 //如果dirtyalloc为零，则将分配一个新的支持数组，dirtyalloc将被清除并作为后备数组重用。
6 func makeBucketArray(t *maptype, b uint8, dirtyalloc unsafe.Pointer) (buckets unsafe.Pointer, nextOverflow *bmap) {
7 base := bucketShift(b)
8 nbuckets := base
9 // 对于小b，溢出桶不太可能出现。
10 // 避免计算的开销。
11 if b >= 4 {
12 //加上估计的溢出桶数
13 //插入元素的中位数
14 //与此值b一起使用。
15 nbuckets += bucketShift(b - 4)
16 sz := t.bucket.size * nbuckets
17 up := roundupsize(sz)
18 if up != sz {
19 nbuckets = up / t.bucket.size
20 }
21 }
22 if dirtyalloc == nil {
23 buckets = newarray(t.bucket, int(nbuckets))
24 } else {
25 // dirtyalloc先前是由上面的newarray（t.bucket，int（nbuckets）），但不能为空。
26 buckets = dirtyalloc
27 size := t.bucket.size * nbuckets
28 if t.bucket.kind&kindNoPointers == 0 {
29 memclrHasPointers(buckets, size)
30 } else {
31 memclrNoHeapPointers(buckets, size)
32 }
33 }
34
35 if base != nbuckets {
36 //我们预先分配了一些溢出桶。
37 //为了将跟踪这些溢出桶的开销降至最低，我们使用的约定是，如果预分配的溢出存储桶发生了溢出指针为零，则通过碰撞指针还有更多可用空间。
38 //对于最后一个溢出存储区，我们需要一个安全的非nil指针；只是用bucket。
39 nextOverflow = (*bmap)(add(buckets, base*uintptr(t.bucketsize)))
40 last := (*bmap)(add(buckets, (nbuckets-1)*uintptr(t.bucketsize)))
41 last.setoverflow(t, (*bmap)(buckets))
42 }
43 return buckets, nextOverflow
44 }
复制代码
默认创建2b个bucket，如果b大于等于4，那么就预先额外创建一些overflow bucket。除了最后一个overflow bucket，其余overflow bucket的overflow指针都是nil，最后一个overflow bucket的overflow指针指向bucket数组第一个元素，作为哨兵，说明到了到结尾了。
3.2 查询操作
复制代码
1 // mapaccess1返回指向h [key]的指针。从不返回nil，而是 如果值类型为零，它将返回对零对象的引用,该键不在map中。
2 //注意：返回的指针可能会使整个map保持活动状态，因此请不要坚持很长时间。
3 func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
4 if raceenabled && h != nil { //raceenabled是否启用数据竞争检测。
5 callerpc := getcallerpc()
6 pc := funcPC(mapaccess1)
7 racereadpc(unsafe.Pointer(h), callerpc, pc)
8 raceReadObjectPC(t.key, key, callerpc, pc)
9 }
10 if msanenabled && h != nil {
11 msanread(key, t.key.size)
12 }
13 if h == nil || h.count == 0 {
14 return unsafe.Pointer(&zeroVal[0])
15 }
16 // 并发访问检查
17 if h.flags&hashWriting != 0 {
18 throw("concurrent map read and map write")
19 }
20
21 // 计算key的hash值
22 alg := t.key.alg
23 hash := alg.hash(key, uintptr(h.hash0)) // alg.hash
24
25 // hash值对m取余数得到对应的bucket
26 m := uintptr(1)<>= 1
33 }
34 oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize)))
35 if !evacuated(oldb) {
36 b = oldb
37 }
38 }
39
40 // 计算tophash，取高8位
41 top := uint8(hash >> (sys.PtrSize*8 - 8))
42
43 for {
44 for i := uintptr(0); i < bucketCnt; i++ {
45 // 检查top值，如高8位不一样就找下一个
46 if b.tophash[i] != top {
47 continue
48 }
49
50 // 取key的地址
51 k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
52
53 if alg.equal(key, k) { // alg.equal
54 // 取value得地址
55 v := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))
56 }
57 }
58
59 // 如果当前bucket没有找到，则找bucket链的下一个bucket
60 b = b.overflow(t)
61 if b == nil {
62 // 返回零值
63 return unsafe.Pointer(&zeroVal[0])
64 }
65 }
66 }
复制代码
先定位出bucket，如果正在扩容，并且这个bucket还没搬到新的hash表中，那么就从老的hash表中查找。
在bucket中进行顺序查找，使用高八位进行快速过滤，高八位相等，再比较key是否相等，找到就返回value。如果当前bucket找不到，就往下找overflow bucket，都没有就返回零值。
访问的时候，并不进行扩容的数据搬迁。并且并发有写操作时抛异常。
注意，t.bucketsize并不是bmap的size，而是bmap加上存储key、value、overflow指针，所以查找bucket的时候时候用的不是bmap的szie。
3.3 更新/插入过程
复制代码
1 // 与mapaccess类似，但是如果map中不存在密钥，则为该密钥分配一个插槽
2 func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
3 ...
4 //设置hashWriting调用alg.hash，因为alg.hash可能出现紧急情况后，在这种情况下，我们实际上并没有进行写操作.
5 h.flags |= hashWriting
6
7 if h.buckets == nil {
8 h.buckets = newobject(t.bucket) // newarray(t.bucket, 1)
9 }
10
11 again:
12 bucket := hash & bucketMask(h.B)
13 if h.growing() {
14 growWork(t, h, bucket)
15 }
16 b := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + bucket*uintptr(t.bucketsize)))
17 top := tophash(hash)
18
19 var inserti *uint8
20 var insertk unsafe.Pointer
21 var val unsafe.Pointer
22 for {
23 for i := uintptr(0); i < bucketCnt; i++ {
24 if b.tophash[i] != top {
25 if b.tophash[i] == empty && inserti == nil {
26 inserti = &b.tophash[i]
27 insertk = add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
28 val = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))
29 }
30 continue
31 }
32 k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
33 if t.indirectkey {
34 k = *((*unsafe.Pointer)(k))
35 }
36 if !alg.equal(key, k) {
37 continue
38 }
39 // 已经有一个 mapping for key. 更新它.
40 if t.needkeyupdate {
41 typedmemmove(t.key, k, key)
42 }
43 val = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))
44 goto done
45 }
46 ovf := b.overflow(t)
47 if ovf == nil {
48 break
49 }
50 b = ovf
51 }
52 //// 如果已经达到了load factor的最大值，就继续扩容。
53 //找不到键的映射。分配新单元格并添加条目。
54 //如果达到最大负载系数或溢出桶过多，并且我们还没有处于成长的中间，就开始扩容。
55 if !h.growing() && (overLoadFactor(h.count+1, h.B) ||
56 tooManyOverflowBuckets(h.noverflow, h.B)) {
57 hashGrow(t, h)
58 goto again // //扩大表格会使所有内容无效， so try again
59 }
60 if inserti == nil {
61 // 当前所有存储桶已满，请分配一个新的存储桶
62 newb := h.newoverflow(t, b)
63 inserti = &newb.tophash[0]
64 insertk = add(unsafe.Pointer(newb), dataOffset)
65 val = add(insertk, bucketCnt*uintptr(t.keysize))
66 }
67
68 // 在插入的位置，存储键值
69 if t.indirectkey {
70 kmem := newobject(t.key)
71 *(*unsafe.Pointer)(insertk) = kmem
72 insertk = kmem
73 }
74 if t.indirectvalue {
75 vmem := newobject(t.elem)
76 *(*unsafe.Pointer)(val) = vmem
77 }
78 typedmemmove(t.key, insertk, key)
79 *inserti = top
80 h.count++
81
82 done:
83 if h.flags&hashWriting == 0 {
84 throw("concurrent map writes")
85 }
86 h.flags &^= hashWriting
87