总结golang之map

时间：2024-11-08 22:05:41

总结golang之map

2017年04月13日 23:35:53 趁年轻造起来阅读数：18637 标签： golang map go 更多

个人分类： golang

版权声明：本文为博主原创文章，未经博主允许不得转载。 https://blog.****.net/Soooooooo8/article/details/70163475

0x01 map基本操作

0x02 map键类型

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

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

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

slice,
map,
func,

补充

不像Java可以为class自定义hashcode方法，以及C++可以重载==操作符，golang map**不支持**==重载或者使用自定义的hash方法。因此，如果想要把struct用作map的key，就必须保证struct不包含slice, map, func
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，

maptype用来保存map的类型信息，包括key、elem(value)的类型描述器，keysize，valuesize，bucketsize等；
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；
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。

5.4. map扩张

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

0x06 map建议

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

相关文章

