0x01 map基本操作

• 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

0x02 map键类型

支持 == 操作符的类型有：

• boolean, 
• numeric, 
• string, 
• pointer, 
• channel, 
• interface(as long as dynamic type supports equality), 
• 以及只包含上述类型的array和struct

不支持 == 操作符的类型有：

• slice, 
• map, 
• func,

补充

1. 不像Java可以为class自定义hashcode方法，以及C++可以重载==操作符，golang map**不支持**==重载或者使用自定义的hash方法。因此，如果想要把struct用作map的key，就必须保证struct不包含slice, map, func
2. golang为uint32、uint64、string提供了fast access，使用这些类型作为key可以提高map访问速度，详见hashmap_fast.go

0x03 map并发

map不是并发安全的，通常使用sync.RWMutex保护并发map

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

0x04 map小技巧

4.1. 利用value类型的零值

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12

4.2. map[k1]map[k2]v 对比 map[struct{k1, k2}]v

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

0x05 map实现细节浅析

5.1. 如何计算hash值

golang为每个类型定义了类型描述器_type，并实现了hashable类型的_type.alg.hash和_type.alg.equal。

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8

5.2. map实现结构

map的实现主要有三个struct，

1. maptype用来保存map的类型信息，包括key、elem(value)的类型描述器，keysize，valuesize，bucketsize等；
2. hmap - A header for a Go map. hmap保存了map的实例信息，包括count，buckets，oldbuckets等；buckets是bucket的首地址，用hash值的低h.B位hash & (uintptr(1)<<h.B - 1)计算出key所在bucket的index； 
   
3. bmap - A bucket for a go map. bmap只有一个域tophash [bucketCnt]uint8，它保存了key的hash值的高8位uint8(hash >> (sys.PtrSize*8 - 8))；一个bucket包括一个bmap(tophash数组)，紧跟的bucketCnt个keys和bucketCnt个values，以及一个overfolw指针。 
   

makemap根据maptype中的信息初始化hmap

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

5.3. 如何访问map

golang的maptype保存了key的类型描述器，以供访问map时调用key.alg.hash, key.alg.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
• 26
• 27
• 28
• 29
• 30
• 31
• 32
• 33
• 34
• 35
• 36
• 37
• 38
• 39
• 40
• 41
• 42

5.4. map扩张

这部分留待以后有机会再续。这里暂时附上Keith Randall的slide作为参考。 

0x06 map建议

• 如果知道size，预先分配资源make(map[int]int, 1000)
• uint32, uint64, string作为键，非常快
• 清理map：for k:= range m { delete(m, k) }
• key和value中没有指针可以使GC scanning更快