半路出家去学计算机网站开发,电商设计公司官网,印刷网站建设,wordpress信息登记一.map介绍和使用 map是一种无序的基于key-value的数据结构#xff0c;Go语言的map是引用类型#xff0c;必须初始化才可以使用。 1. 定义 Go语言中#xff0c;map类型语法如下#xff1a;
map[KeyType]ValueType
KeyType表示键类型ValueType表示值类型 map类型的变量默认…一.map介绍和使用 map是一种无序的基于key-value的数据结构Go语言的map是引用类型必须初始化才可以使用。 1. 定义 Go语言中map类型语法如下
map[KeyType]ValueType
KeyType表示键类型ValueType表示值类型 map类型的变量默认初始值为nil需要使用make函数来分配内存。语法为
make(map[KeyType]ValueType, [cap])map[KeyType]ValueType{} //底层也是使用的makemap[KeyType]Value{ //底层也是使用的makekey:value,key:value,...
} 其中cap表示map的容量该参数虽然不是必须的但是我们应该在初始化map的时候就为其指定一个合适的容量。 可以使用len()内置函数来获取map键值对的个数。 注意map保存的键值对中键不能被修改只能修改值。 2.基本使用
package mainimport fmtfunc main() {scoreMap : make(map[string]int, 8)scoreMap[张三] 100scoreMap[小明] 90fmt.Println(scoreMap)fmt.Printf(key num is %d\n, len(scoreMap))fmt.Println(scoreMap[小明])fmt.Printf(type(scoreMap)%T\n, scoreMap)
} map也支持在声明时填充元素
package mainimport fmtfunc main() {userInfo : map[string]string{username: zhansan,password: 123456,}fmt.Println(userInfo)
} 3. 判断某个键是否存在 Go语言中有个判断map中的键是否存在的特殊写法
value, ok : map[key] 例子
package mainimport fmtfunc main() {userInfo : map[string]string{username: zhansan,passward: 123456,}value, ok : userInfo[passward]if ok {fmt.Println(value)} else {fmt.Println(passward is not exit)}value, ok userInfo[sex]if ok {fmt.Println(value)} else {fmt.Println(sex is not exit)}
} 4. map的遍历 遍历key和value
package mainimport fmtfunc main() {scoreMap : make(map[string]int, 8)scoreMap[小明] 100scoreMap[张三] 80scoreMap[李四] 60for key, value : range scoreMap {fmt.Printf(scoreMap[%s] %d\n, key, value)}
} 只遍历key 注意遍历map时的元素顺序与添加键值对的顺序无关。 5. 删除键值对 使用delete()内置函数从map中删除一组键值对格式如下
delete(map, key)//map:为需要删除键值对的map
//key:表示要删除键值对的键
package mainimport fmtfunc main() {scoreMap : make(map[string]int, 8)scoreMap[小明] 100scoreMap[张三] 80scoreMap[李四] 60value, ok : scoreMap[李四]if ok {fmt.Println(value)} else {fmt.Println(李四 is not exit)}//删除键值对delete(scoreMap, 李四)value, ok scoreMap[李四]if ok {fmt.Println(value)} else {fmt.Println(李四 is not exit)}
} 6. 按照指定顺序遍历map 实际时先获取到所有的键将键设置成指定顺序再通过键来遍历map。
package mainimport (fmtmath/randsorttime
)func main() {rand.Seed(time.Now().UnixNano()) //初始化随机种子scoreMap : make(map[string]int, 200)for i : 0; i 100; i {key : fmt.Sprintf(stu%02d, i)scoreMap[key] rand.Intn(100) //获取0-100的随机数//fmt.Println(key, scoreMap[key])}keys : make([]string, 0, 200)//保存key//按照排序后的key遍历scoreMapfor key : range scoreMap {keys append(keys, key)}//fmt.Println(keys)sort.Strings(keys) //对keys进行排序for _, key : range keys {fmt.Printf(scoreMap[%s] %d\n, key, scoreMap[key])}
} 7. 元素为map类型的切片
package mainimport fmtfunc main() {mapSlice : make([]map[string]string, 3, 10) //并没有为map分配地址空间for index, val : range mapSlice {fmt.Printf(mapSlice[%d] %v\n, index, val)}//分配地址空间for index, _ : range mapSlice {mapSlice[index] make(map[string]string, 10)}fmt.Println(---------插入键值对后---------)//插入键值对mapSlice[0][name] 张三mapSlice[0][passwd] 123123mapSlice[1][name] 李四mapSlice[1][passwd] 321321mm : map[string]string{name: 小明,passwd: 123465,}mapSlice append(mapSlice, mm)for index, val : range mapSlice {fmt.Printf(mapSlice[%d] %v\n, index, val)}
} 8. 值为切片类型的map
package mainimport fmtfunc main() {sliceMap : make(map[string][]string, 10) //没有为slice分配空间sliceMap[中国] make([]string, 0, 10)sliceMap[中国] append(sliceMap[中国], 北京, 上海, 长沙)key : 美国value, ok : sliceMap[key]if !ok {value make([]string, 0)}value append(value, 芝加哥, 华盛顿)sliceMap[key] valuefor key, val : range sliceMap {fmt.Printf(sliceMap[%s] %v\n, key, val)}
} 二.map底层原理 Go语言的map底层数据结构为哈希表(散列表)但是与C的哈希表实现不同。想要了解Go语言map的底层实现需要先了解两个重要的数据结构 hmap和bmap。 2.1 map头部数据结构——hmap hmap中有几个重要的属性
count记录了map中实际元素的个数B控制哈希桶的个数为2^B个buckets是一个指向长度为2^B大小的类型为bmap的数组oldbuckets与buckets一样也是指向一个多桶的数组不同的是oldbuckets指向的是旧桶的地址当oldbuckets不为空时表示map正处于扩容阶段。
type hmap struct {// map中元素的个数使用len返回就是该值count int// 状态标记// 1: 迭代器正在操作buckets// 2: 迭代器正在操作oldbuckets // 4: go协程正在像map中写操作// 8: 当前的map正在增长并且增长的大小和原来一样flags uint8// buckets桶的个数为2^BB uint8 // 溢出桶的个数noverflow uint16 // key计算hash时的hash种子hash0 uint32// 指向的是桶的地址buckets unsafe.Pointer// 旧桶的地址当map处于扩容时旧桶才不为niloldbuckets unsafe.Pointer //扩容之后数据迁移的计数器,记录下次迁移的位置当nevacuate旧桶元素个数数据迁移完nevacuate uintptr // 额外的map字段,存储溢出桶信息// 这个字段是为了优化GC扫描而设计的。当key和value均不包含指针并且都可以inline时使用。extra是指向mapextra类型的指针。extra *mapextra
} 创建一个map实际是创建一个指针指向hmap结构。 mapextra结构 如果一个哈希表要分配桶的数目大于2^4个就认为使用溢出桶的几率比较大就会预分配2^(B-4)个溢出桶备用这些溢出桶与常规桶内存中是连续的只是前2^B个作为常规桶。
type mapextra struct {// 如果 key 和 value 都不包含指针并且可以被 inline(128 字节)// 就使用 hmap的extra字段 来存储 overflow buckets这样可以避免 GC 扫描整个 map// 然而 bmap.overflow 也是个指针。这时候我们只能把这些 overflow 的指针// 都放在 hmap.extra.overflow 和 hmap.extra.oldoverflow 中了// overflow 包含的是 hmap.buckets 的 overflow 的 buckets// oldoverflow 包含扩容时的 hmap.oldbuckets 的 overflow 的 bucketoverflow *[]*bmap //记录已使用的溢出桶的地址oldoverflow *[]*bmap //扩容阶段旧桶使用的溢出桶地址// 指向空闲的 overflow bucket 的指针nextOverflow *bmap //指向下一个空闲溢出桶
} 2.2 bmap bmap是每一个桶的数据结构每一个bmap包含8个key和value。
type bmap struct {tophash [bucketCnt]uint8 // len为8的数组用来快速定位key是否在这个bmap中// 一个桶最多8个槽位如果key所在的tophash值在tophash中则代表该key在这个桶中
} 上面是bmap的静态结构在编译过程中runtime.bmap会扩展成以下结构
topbits :用来快速定位桶中键值对的位置。keys键值对的键values键值对的值overflow当8个key满的时候需要新创建一个桶overflow保存下一个桶的地址。 细节 这里将键和键保存到了一起值和值保存在了一起为什么不讲键和值保存在一起 因为键和值的类型可能不同结构体内存对齐会浪费空间。 type bmap struct{topbits [8]uint8keys [8]keytypevalues [8]valuetypepad uintptr // 内存对齐使用可能不需要overflow uintptr // 当bucket 的8个key 存满了之后// overflow 指向下一个溢出桶 bmap// overflow是uintptr而不是*bmap类型保证bmap完全不含指针是为了减少gc溢出桶存储到extra字段中
}2.3 整体结构示意图
如下图创建一个容量为5的map此时B5分配桶数为2^532个(为[]bmap下标0-31)则备用溢出桶数为2^(5-4)2个(为[]bmap下标3233)。此时0号的bmap桶满了overflow指向下一个溢出桶地址即[]bmap下标为32位置。hmap中的noverflow表示使用溢出桶数量这里为1extra字段记录溢出桶mapextra结构体。mapextra中的overflow保存使用的溢出桶nextoverflow指向下一个空闲溢出桶33号。 创建一个mapGo语言底层实际调用的是makemap函数主要做的工作就是初始化hmap结构体的各个字段。比如计算B的大小设置哈希种子hash0给buckets分配内存等。
func makemap(t *maptype, hint int, h *hmap) *hmap {//计算内存空间和判断是否内存溢出mem, overflow : math.MulUintptr(uintptr(hint), t.bucket.size)if overflow || mem maxAlloc {hint 0}// initialize Hmapif h nil {h new(hmap)}h.hash0 fastrand()//计算出指数B,那么桶的数量表示2^BB : uint8(0)for overLoadFactor(hint, B) {B}h.B Bif h.B ! 0 {var nextOverflow *bmap//根据B去创建对应的桶和溢出桶h.buckets, nextOverflow makeBucketArray(t, h.B, nil)if nextOverflow ! nil {h.extra new(mapextra)h.extra.nextOverflow nextOverflow}}return h
}2.4 key定位原理 key通过哈希计算后得到哈希值哈希值的低B位用于确定桶哈希值的高8位用于在一个独立的桶中找到键的位置。 例子 当在6号buckets中每有找到对应的tophash并且overflow不为空还需要继续到overflow指向的buckets中的tophash中查找直到找到或者所有的key槽位都找遍包括该buckets下的所有溢出桶(overflow)。 2.5 插入元素
插入 key通过哈希函数得到哈希值通过低B位确定桶位置在桶中按顺序找空位置找到后将高8位保存在tophash中key和value保存到keys和values中。如果当前桶中没有空闲位置查看是否有溢出桶有的话在溢出桶中找空位置保存。没有溢出桶添加溢出桶将数据保存到第一个空位置。
哈希冲突 当两个不同的key键通过哈希函数落到了同一个桶中这时就发生了哈希冲突。 Go语言的解决办法是链地址法由于桶(bmap)的数据结构一个桶保存8个键和值。在桶中按顺序寻找第一个空位若有空位则将其置于其中若没有空位判断是否有溢出桶若有溢出桶在溢出桶中寻找空位。若没有溢出桶则添加溢出桶并将其置于溢出桶的第一个空位(非扩容的情况)。 当不同的key通过哈希函数得到的哈希值相同时低位和高位都相同如何查找到对应的键值对 步骤和上面相同低B为找到对应的桶高8位找到对应的tophash位置拿出key与要找的key比较是否相同相同的话取出不同的话再在tophash中查找哈希值高8位的值没找到在溢出桶中找直到找完所有key或者找到对应的key为止。 2.6 扩容 为什么要进行扩容 当元素越来越多或者溢出桶的数量越来越多导致查找的效率会变低。 2.6.1 负载因子 负载因子是决定哈希表是否进行扩容的关键指标。负载因子的值为6.5(经验所得)意思是平均每个桶中键值对的数量。当 总键值对个数 桶总数 * 6.5这个时候说明大部分的桶可能快满了。这个时候就可能需要扩容。 2.6.2 扩容的条件
扩容的条件有两个
判断负载因子是否达到临界点(6.5)如果达到了如果插入新的元素大概率会需要挂在溢出桶上了。判断溢出桶是否过多当正常桶总数 2^15时如果溢出桶总数正常桶总数则认为溢出桶过多。当正常桶总数2^15时直接与2^15比较当溢出桶总数2^15时则认为溢出桶总数过多。 其实第二点是对第一点的补充。因为在负载因子比较小的情况下有可能map的查找和插入的效率也可能很低。即map里的元素少但是桶数量多(真实分配的桶数量多包括大量的溢出桶)。 导致上面这种情况的原因是对map中的元素不断的增删增加会导致桶的数量变多删除导致负载因子不高。 这样导致桶的使用率不高存储的值比较稀疏导致查找的效率变低。 2.6.3 解决方案 针对超过负载因子的情况将B1新建一个buckets数组新的buckets大小是原来的2倍然后将旧buckets数据搬迁到新的buckets。该方法我们称之为增量扩容。 针对桶数量过多的情况并不扩大容量buckets数量维持不变重新做一遍类似增量扩容的操作就是将键值对重新映射到新buckets中使得buckets的使用率变高。该方法我们称为等量扩容。 对于等量扩容其实存在一种极端情况如果插入map的key通过哈希函数后得到的哈希值一样那它们就会落到同一个buckets中查过8个就会产生overflow结果也会照成溢出桶过多移动元素其实解决不了问题此时哈希表退化成了一个链表操作效率编程了O(n)但Go的每一个map都会在初始阶段的makemap是定义一个随机哈希种子所以要构成这种冲突是没有那么容易的。 扩容首先分配新的buckets(不管增量扩容还是等量扩容都要新分配buckets)将老的buckets挂到oldbuckets字段上。buckes挂上新的buckets。然后将oldbuckets上的键值对重新哈希到buckets上直到旧桶中的键值对全部搬迁完毕后删除oldbuckets。 当oldbuckets值为nil表示扩容完毕。 2.6.4 渐进式扩容 由于map扩容需要使用将原有的键值对重新搬迁到新的内存地址如果map储存了数以亿计的键值对一次性搬迁会照成比较大的延时。因此Go语言map扩容采取了一种渐进式的方式。 原有的key不会一次性搬迁完毕每次最多搬迁2个buckets并且只有在插入修改或删除key的时候才会进行搬迁buckets工作。
参考文档深入解析Golang的map设计 - 知乎
