底层总结笔记《Go语言精进之路》
map底层数据结构,也就是运行时的map的样子。
从语法,到运行时
src/runtime/map.go
源码里面key value对应起的名字是key elem
语法方法到runtime方法
操作 | 转换前 | 转换后 |
---|---|---|
初始化 | m := make(map[keyType]valType, capacityhint) | m := runtime.makemap(maptype, capacityhint, m ) |
取值 | v := m[“key”] | v := runtime.mapaccess1(maptype, m, “key”) |
取值 | v, ok := m[“key”] | v, ok := runtime.mapaccess2(maptype, m, “key”) |
赋值 | m[“key”] = “value” | v := runtime.mapassign(maptype, m, “key”) |
删元素 | delete(m, “key”) | runtime.mapdelete(maptype, m, “key”) |
map根据key获取value的效率,比不上索引寻址——切片和数组获取元素的效率。
注意,上面每个转换后的运行时对应的函数调用的参数里,第一个参数都是maptype。
(这个类型里面存了关于map的key,elem大小、类型信息。是一个抽象复用设计)
maptype的存在让Go中所有map类型共享一套运行时map操作函数。
/src/runtime/type.go
type maptype struct {
typ _type
key *_type
elem *_type
bucket *_type // internal type representing a hash bucket
// function for hashing keys (ptr to key, seed) -> hash
hasher func(unsafe.Pointer, uintptr) uintptr
keysize uint8 // size of key slot
elemsize uint8 // size of elem slot
bucketsize uint16 // size of bucket
flags uint32
}
map,到runtime.hmap
语法层面的map类型,会翻译为runtime.hmap。
一个map变量,是一个runtime.hmap类型的实例。
hmap,是map类型的header(所以取名hmap嘛,h就是header的首字母),意思就是它是map类型的描述符。
对应的Go源码定义:
// A header for a Go map.
type hmap struct {
// Note: the format of the hmap is also encoded in cmd/compile/internal/reflectdata/reflect.go.
// Make sure this stays in sync with the compiler's definition.
count int // # live cells == size of map. Must be first (used by len() builtin)
flags uint8
B uint8 // log_2 of # of buckets (can hold up to loadFactor * 2^B items)
noverflow uint16 // approximate number of overflow buckets; see incrnoverflow for details
hash0 uint32 // hash seed
buckets unsafe.Pointer // array of 2^B Buckets. may be nil if count==0.
oldbuckets unsafe.Pointer // previous bucket array of half the size, non-nil only when growing
nevacuate uintptr // progress counter for evacuation (buckets less than this have been evacuated)
extra *mapextra // optional fields
}
英文:
overflow 溢出
bucket 桶
关注的几个字段,每个字段的用途:
字段 | 含义 |
---|---|
count | 就是len()获取map的实际大小的值 |
flags | 表示map的几种状态 (了解)(维护的时候发现修改啥的源码没做并发保护,也知道了为啥说map非线程安全了) |
B | 2的B次方就是buckets数组的长度 |
noverflow | overflow bucket的大致num 数目(“溢出桶” 这个角色出场的原因,就是某个桶bucket[i]装满了,但是hash计算完的key,说,还得存这个桶下面,那怎么办?就弄个溢出桶,链表链着) |
buckets | 指向bucket数组的指针 (buckets数组:map存key value的地方) |
oldbuckets | 当发生扩容的时候,该字段指向原bucket数组,等全迁移完数据,就不用指了,原bucket数组就可以释放了,等着GC了 |
nevacuate | nevacuate的bucket已经完成了数据的排空和迁移 |
一句话,hmap结构体一个成员是buckets 数组,数组长度是2的B次方。
数组每个元素bucket里面有:长度为8的tophash数组,长度为8的key数组,长度为8的value数组,还有万一8个槽装不下还得装避免尴尬的overflow bucket 链表。
map的数据结构这么设计,怎么存数据?
下面挨个说这些设计完了,map到底怎么存数据? 以及设计好在哪?有必要吗?
怎么存key value
来了一个key, value,要存。
map就拿到这个key,进行一个哈希函数计算 hashcode = Hash(key),得到哈希码hashcode。
这个hashcode有16位。
低8位 确定存哪个桶bucket[i](所以每个桶都是存的低8位相同hashcode的key元素们),
高8位 确定存bucket[i]的哪个位置。
tophash的设计意义
tophash的存在意义,就是,找key位置更快。
因为map可以允许key的类型好多种(只要可以等于不等于比较),直接用key比对来找的话,那么万一,比如,key是很长的字符串,那么比较就效率肯定就低了。
所以看上图就能看到,一个bucket桶的设计不是说,就key存储和value存储两部分就完了,为了效率加了tophash部分,是空间换时间的思想设计。
overflow的设计意义
hashcode=Hash(key) 计算的结果低8位确定唯一的bucket[i]。
overflow bucket设计,就是为了缓解当存在很多key,计算后的hashcode的低8位相同的个数大于了一个bucket所能存放的数目8个时,且这个map还没达到扩容条件时,做的一种存储设计。
同一个bucket的多个overflow bucket 以链表的形式连接。
key和value分开存的意义
英文
padding 填充
是为了节省内存空间。
所以不惜增加了算法复杂度!啊不是,是仅仅增加了一些复杂度。[doge]
因为需要内存对齐,所以如果kv一组存储,按例子map[int8]int64,就会发现,每个key都得padding 7 bytes。相比图中左边Go采取的方案,右边的多出了8*7bytes=56bytes的内存浪费。百分比一算就发现浪费太高。
一个bucket 桶,在Go源码中的代码是:
是bmap这个结构体(b:bucket)
// A bucket for a Go map.
type bmap struct {
// tophash generally contains the top byte of the hash value
// for each key in this bucket. If tophash[0] < minTopHash,
// tophash[0] is a bucket evacuation state instead.
tophash [bucketCnt]uint8
// Followed by bucketCnt keys and then bucketCnt elems.
// NOTE: packing all the keys together and then all the elems together makes the
// code a bit more complicated than alternating key/elem/key/elem/... but it allows
// us to eliminate padding which would be needed for, e.g., map[int64]int8.
// Followed by an overflow pointer.
}
自动扩容
map会自动扩容,扩容的内存分配由运行时负责。只要内存够,就可以一直往map里添新数据。
扩容也就是扩充buckets的数量。并重新在bucket间均衡分配数据。
触发扩容有两种:
一个是count太多了!
一个是overflow bucket 数量太多了!
1、count太多,多到 count > LoadFactor * 2^B 这种程度!
count > LoadFactor * 2^B 时,会扩容。
const(
...
// Maximum average load of a bucket that triggers growth is 6.5.
// Represent as loadFactorNum/loadFactorDen, to allow integer math.
loadFactorNum = 13
loadFactorDen = 2
...
)
LoadFactor负载因子目前设置为6.5,就是上面定义的常量值loadFactorNum除以loadFactorDen计算出来的。
然后2^B是buckets数组的长度。
扩容方式是,创建一个原来buckets规模的2倍大的buckets,然后oldbuckets指向原buckets数组,只有当assgin和delete操作(即插入和删除)时,进行排空和迁移,直到完全迁移完,删除oldbuckets指向,原buckets数组释放。
2、overflow bucket 数量太多
noverflow >= uint16(1)<<(B&15)
扩容方式是,创建一个和原来buckets一样规模的buckets,也是只当assgin和delete操作(即插入和删除)时,进行排空和迁移。
map自动扩容源代码
func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
...
// If we hit the max load factor or we have too many overflow buckets,
// and we're not already in the middle of growing, start growing. 我们还没开始生长,就生长吧。[doge]。
if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
hashGrow(t, h)
goto again // Growing the table invalidates everything, so try again
}
...
}
map容量
map 容量
和数组不同,map 可以根据新增的 key-value 动态的伸缩,因此它不存在固定长度或者最大限制,但是也可以选择标明 map 的初始容量 capacity,格式如下:
make(map[keytype]valuetype, cap)
例如:
m := make(map[string]float, 20)
当 map 增长到容量上限的时候,如果再增加新的 key-value,map 的大小会自动加 1,所以出于性能的考虑,对于大的 map 或者会快速扩张的 map,即使只是大概知道容量,也最好先标明。