【1-4 Golang】Go语言快速入门—哈希表MAP

tomato01 · · 776 次点击 · · 开始浏览    

&emsp;&emsp;map又称为hash表、字典,存储键值对,其增删改查时间复杂度可以达到O(1)。map和切片是Go语言开发最常用的数据类型。 ## 基本操作 &emsp;&emsp;map存储键值对,支持key-value键值对的插入,查找/修改/删除key对应的value,并且这些操作都可以在O(1)时间复杂度完成。 ``` package main import "fmt" func main() { //map声明初始化 score := make(map[string]int, 0) //key-value键值对存储 score["zhangsan"] = 100 score["lisi"] = 90 //len返回map存储的键值对数目 fmt.Println(len(score), score) //2 map[lisi:90 zhangsan:100] //查找key对应值,两种方式:1)返回值value,以及bool值表示key-value键值对是否存在;2)只返回值value zhangsan, ok := score["zhangsan"] zhangsan1 := score["zhangsan"] fmt.Println(zhangsan, ok, zhangsan1) //100 true 100 //修改key对应值 score["zhangsan"] = 95 fmt.Println(score["zhangsan"]) //95 //删除map中键值对 delete(score,"zhangsan") //这时候查找key对应值,返回value类型空值,int类型空值就是0 zhangsan, ok = score["zhangsan"] fmt.Println(zhangsan, ok) //0 false } ``` &emsp;&emsp;len函数可以获取map键值对数目,注意map在查找key对应的value时,有两种方式:1)返回一个变量,只返回值value;2)返回两个变量,第一个表示值value,第二个为bool类型表示key-value键值对是否存在。另外,key-value键值对不存在时,查找时返回的是值value类型对应空值,如整数0,空字符串,空切片,指针nil等。特别当值类型为指针时要注意,使用之前最好判断下查找的键值对是否存在,以防出现空指针异常panic。 &emsp;&emsp;map也支持for range遍历(迭代),熟悉PHP语言的都知道,PHP数组元素的遍历和插入顺序是一样的;要特别注意Go语言map遍历时,键值对的访问顺序和插入是不一致的,并且每次遍历的访问顺序都不同,如下面例子所示: ``` package main import "fmt" func main() { //map声明初始化 score := make(map[string]int, 0) //key-value键值对存储 for i := 0; i < 10; i ++ { score[fmt.Sprintf("test-%v", i)] = i } for k, v := range score { fmt.Printf("%v:%v ", k, v) } //test-4:4 test-8:8 test-2:2 test-3:3 test-5:5 test-6:6 test-7:7 test-9:9 test-0:0 test-1:1 fmt.Printf("\n") for k, v := range score { fmt.Printf("%v:%v ", k, v) } //test-9:9 test-0:0 test-1:1 test-5:5 test-6:6 test-7:7 test-2:2 test-3:3 test-4:4 test-8:8 fmt.Printf("\n") //直接修改v是没有用的 for _, v := range score { v += 100 } //map[test-0:0 test-1:1 test-2:2 test-3:3 test-4:4 test-5:5 test-6:6 test-7:7 test-8:8 test-9:9] fmt.Println(score) //遍历过程中这样修改map键值对 for k, v := range score { score[k] = v + 100 } //map[test-0:100 test-1:101 test-2:102 test-3:103 test-4:104 test-5:105 test-6:106 test-7:107 test-8:108 test-9:109] fmt.Println(score) } ``` &emsp;&emsp;看到了吧,两次遍历输出结果都是不一样的,当然你在运行这段代码的时候,结果大概率与上面输出也是不同的。而且,遍历过程中,想修改键key对应的值value也要注意方式,变量k,v只是当前访问的键值对的拷贝,直接修改变量v没有任何意义。 &emsp;&emsp;看到上述代码,突然想到一个问题:如果遍历过程中,往map新增键值对,会怎么样?新增的键值对会再次被遍历访问到吗?遍历过程会无限持续吗? ``` package main import "fmt" func main() { //map声明初始化 score := make(map[string]int, 0) //key-value键值对存储 for i := 0; i < 3; i ++ { score[fmt.Sprintf("test-%v", i)] = i } //map[test-0:0 test-1:1 test-2:2] fmt.Println(score) for k, v := range score { score[fmt.Sprintf("%v-%v", k, v)] = v + 1 } //8 map[test-0:0 test-0-0:1 test-0-0-1:2 test-1:1 test-1-1:2 test-1-1-2:3 test-2:2 test-2-2:3] fmt.Println(len(score),score) } ``` &emsp;&emsp;貌似遍历过程并没有无限持续。初始map键值对数目为3,遍历过程中新增键值对,如果新增的键值对不会再次被遍历访问到,理论上结束后map键值对数目应该为6,但是结果却显示8,键值对数目接近为原来的2倍多,而且观察输出结果,很明显,新增的键值对再次被遍历访问到了。为什么最终键值对数目为8呢?其实这也是一个随机现象,多次运行,你会发现map包含的键值对数据以及数目都是随机的。为什么呢?这里先保留一个疑问,后面会详细说明。 &emsp;&emsp;最后还有一个小小的问题,map作为函数输入参数时,函数中修改了map(修改/删除/新增键值对),在函数调用方,map会同步发生改变吗?len会改变吗?会和切片现象一样吗? ``` package main import "fmt" func main() { score := make(map[string]int, 0) score["zhangsan"] = 100 fmt.Println(len(score), score) //1 map[zhangsan:100] testMap(score) fmt.Println(len(score), score) //2 map[lisi:90 zhangsan:100] } func testMap(m map[string]int) { m["lisi"] = 90 fmt.Println(len(m), m) //2 map[lisi:90 zhangsan:100] } ``` &emsp;&emsp;map数据,len竟然都发生改变了!说好的Go语言函数按值传参呢,map存储的键值对会发生改变还能理解,参考切片,底层数组或者是什么结构可以共用,可是len为什么也会改变呢?这里先保留一个疑问,后面会详细说明。不过在讲解之前,可以先思考下,len应该改变吗? ## 实现原理 &emsp;&emsp;map也可以称为hash表,字典,其是如何实现O(1)的增删改查时间复杂度呢?学习过数据结构的读者应该都知道,一般有两种方式:开放寻址法和拉链法。最常用的当属拉链法了,基于数组+链表实现,先使用散列函数将键key映射到数组索引(如:计算hash值,并按数组长度取模),因为不同的键key可能映射到同一个数组索引,所以多个键值对形成链表。 &emsp;&emsp;Go语言map采取的就是拉链法,只是还做了一些小小的优化。原始方案链表节点存储键值对,每个节点还包含next指针,这样算下来内存利用率其实是较低的;Go语言将多个元素压缩到同一个链表节点(8个),相当于8个key-value键值对才需要一个next指针,内存利用率自然比原始方案高。另外,因为CPU高速缓存(L1、L2、L3)存在,连续内存访问的性能一般要高于分散内存访问,即8个key-value键值对连续存储的访问性能略好。 &emsp;&emsp;Go语言map结构如下图所示,buckets就是我们所说的数组,可以看到链表节点存储多个key-value键值对,并且多个key连续存储,再跟着多个value连续存储: ![1.4-1.png](https://static.golangjob.cn/220916/0caf473c997002f1074633d4cc9b2830.png) &emsp;&emsp;前面介绍的map初始化以及增删改查基本操作,底层都对应有函数实现,定义在文件runtime/map.go: ``` //make第二个参数,小于等于8对应makemap_small函数 func makemap_small() *hmap func makemap(t *maptype, hint int, h *hmap) *hmap //根据key查找对应value,只返回值;对应v = map[key]写法 func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer //根据key查找对应value,返回两个变量:1)值;2)key是否存在。对应v, ok = map[key]写法 func mapaccess2(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, bool) //新增或者修改键值对 func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer //删除键值对 func mapdelete(t *maptype, h *hmap, key unsafe.Pointer) ``` &emsp;&emsp;在介绍这些基本操作之前,先了解下map相关结构的定义: ``` type hmap struct { count int // 键值对数目,len返回的就是该值 B uint8 // 数组buckets长度为 2^B buckets unsafe.Pointer // buckets数组 } // bucketCnt = 8 type bmap struct { // tophash generally contains the top byte of the hash value for each key in this bucket 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. } dataOffset = unsafe.Offsetof(struct { b bmap v int64 }{}.v) ``` &emsp;&emsp;buckets指向数组首地址,bmap就是链表节点的结构定义,但是其定义只有一个tophash字段,看不出什么多个key多个value连续存储。需要说明的是,实际怎么访问bmap内容就看你的代码怎么写了,其实与结构定义没有太大关系,毕竟变量访问无非只需要地址+长度就行了。读者可以阅读这里的注释了,详细说明了tophash字段后面还跟着多个key,多个value,以及overflow指针(就是next指针)。而变量dataOffset就是第一个键key首地址相对于结构体bmap首地址的偏移量。 &emsp;&emsp;注意tophash字段,uint8数组,注释解释到,其存储的是键key的hash值的高字节;hash值类型为int64,占8字节,而最高字节内容就存储在tophash数组。tophash用于快速比较键key的hash值是否相等,计算方式如下: ``` func tophash(hash uintptr) uint8 { top := uint8(hash >> (goarch.PtrSize*8 - 8)) //PtrSize为8字节 if top < minTopHash { //minTopHash = 5,强制tophash值大于minTopHash top += minTopHash } return top } ``` &emsp;&emsp;为什么tophash值必须大于minTopHash呢?因为小于minTopHash的值有特殊标识,用于提升键key查找效率。比如: ``` //当前位置没有存储键值对,且当前桶后续位置也都没有存储键值对 emptyRest = 0 // this cell is empty, and there are no more non-empty cells at higher indexes or overflows. //当前位置没有存储键值对 emptyOne = 1 // this cell is empty ``` &emsp;&emsp;另外,思考下为什么要连续存储多个key,再跟着连续存储多个value呢?为什么不能按key-value键值对对存储呢?这就涉及都内存对齐了,不同类型的变量有内存对齐要求,比如int64首地址必须按8字节对齐(首地址是8的倍数),int32首地址必须按照4字节对齐,int8无要求。所以针对map[int64]int8,两种存储方式很明显会有如下区别: ![1.4-2.png](https://static.golangjob.cn/220916/9e15d8125b4991d9653ae52372f535d1.png) &emsp;&emsp;好了,我们了解到map底层结构为hmap,其包含底层buckets数组,键值对数目等,再观察上面介绍的基本操作函数声明,map初始化函数makemap返回hmap指针,map新增/修改键值对函数mapassign输入参数为hmap指针,删除键值对函数mapdelete输入参数为hmap指针。那么当map作为参数传递呢?其传递的也是hmap指针,那么函数内部修改了map数据,调用方是否同步改变呢?len是否改变呢?答案很明显了。 &emsp;&emsp;最后,基于这两个结构,map是如何实现增删改查等基本操作呢?我们已新增/修改键值对为例,其实现函数为mapassign。该函数查找map,如果找到对应key,则替换值value;如果没有找到对应key,需要找到一个空的bmap位置,存储该键值对。注意学习下面代码时,结合buckets与bmap示意图更容易理解。 ``` //省略了部分代码 func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer { //计算数组索引 bucket := t.hasher(key, uintptr(h.hash0)) & bucketMask(h.B) //buckets桶数组存储的其实就是bmap结构,该结构大小为bucketsize b := (*bmap)(add(h.buckets, bucket*uintptr(t.bucketsize))) //计算tophash值 top := tophash(hash) //记录查找到的可存储键值对位置 var inserti *uint8 //该位置可存储tophash值 var insertk unsafe.Pointer //该位置可存储键key var elem unsafe.Pointer //该位置可存储值value bucketloop: for { //遍历该bmap 8个位置;比较tophash值,比较key for i := uintptr(0); i < bucketCnt; i++ { //如果tophash值不相等,说明键key肯定不想等 if b.tophash[i] != top { //如果当前位置没有存储键值对,且inserti为空,首次记录该位置可存储键值对 if isEmpty(b.tophash[i]) && inserti == nil { inserti = &b.tophash[i] //bmap首地址偏移dataOffset就是第一个键key存储位置,第i个键key,再偏移i个键key即可。 insertk = add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize)) //计算第i个值value地址,bmap首地址偏移dataOffset,再偏移8个键key,再偏移i个值value即可。 elem = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize)) } //emptyRest说明当前桶后续位置也都没有存储键值对,即map中不存在该键key;则新插入键值对到inserti位置。 if b.tophash[i] == emptyRest { break bucketloop } continue } //获取键key k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize)) //判断查找到的键和输入key是否相等 if !t.key.equal(key, k) { continue } //key相等,则更新对应的值value if t.needkeyupdate() { typedmemmove(t.key, k, key) } goto done } //该bmap没有找到对应key,但是如果overflow不为空,则查找链表下一个bmap ovf := b.overflow(t) if ovf == nil { break } b = ovf } //没有查找到对应key,需要新增键值对 //没有找到一个新位置,则需要申请新的bmap if inserti == nil { newb := h.newoverflow(t, b) inserti = &newb.tophash[0] insertk = add(unsafe.Pointer(newb), dataOffset) elem = add(insertk, bucketCnt*uintptr(t.keysize)) } //剩下就是保存新增键值数据到inserti,insertk,elem } ``` &emsp;&emsp;函数mapassign的注意逻辑都写清楚了注释。当然还有一些细节暂时省略了,比如新增键值对的时候还需要判断是否需要扩容,否则链表越来越长,map的时间复杂度将退化为O(N)。map的其他操作,如访问mapaccess1,删除mapdelete与新增/修改mapassign比较类似,核心都是找到bmap,遍历匹配键key,这里就不再介绍了。 ## 迭代/遍历 &emsp;&emsp;还记得我们遗留的两个问题吗,1)for range遍历map时,多次遍历的访问顺序为什么不同呢?2)for range遍历过程中,新增键值对,最终的键值对数目为什么也是随机的呢?针对问题1,其实这是Go语言专门设计的,本身map的遍历顺序就与插入顺序不一致,Go语言设计者,为了让开发人员不要依赖map的遍历顺序,更是将map的遍历顺序设计为随机的。 &emsp;&emsp;如何遍历map每一个键值对呢?我们知道hmap结构维护有一个buckets数组,数组元素类型为bmap,bmap又通过overflow指针形成链表。那么,我们只需要遍历buckets数组,遍历bmap链表,也就能完成map所有键值对的遍历访问。map迭代/遍历依赖两个函数,其中hiter维护当前访问到的位置,以及键值对信息: ``` func mapiterinit(t *maptype, h *hmap, it *hiter) func mapiternext(it *hiter) type hiter struct { //键值对 key unsafe.Pointer // Must be in first position. Write nil to indicate iteration end (see cmd/compile/internal/walk/range.go). elem unsafe.Pointer // Must be in second position (see cmd/compile/internal/walk/range.go). //当前遍历的bmap bptr *bmap // current bucket //当前map已遍历了几个键值对 i uint8 //开始遍历的bucket位置 startBucket uintptr // bucket iteration started at //偏移量,每一个bmap从该偏移量开始遍历 offset uint8 // intra-bucket offset to start from during iteration (should be big enough to hold bucketCnt-1) //当前遍历的bucket位置 bucket uintptr } ``` &emsp;&emsp;函数mapiterinit初始化迭代器hiter,包括开始遍历的bucket位置(随机),每一个bmap开始遍历的偏移量(随机)。正因为这两个值的随机性,才导致map的遍历顺序随机。 ``` func mapiterinit(t *maptype, h *hmap, it *hiter) { //随机 r := uintptr(fastrand()) it.startBucket = r & bucketMask(h.B) it.offset = uint8(r >> h.B & (bucketCnt - 1)) it.bucket = it.startBucket //获取第一个键值对 mapiternext(it) } ``` &emsp;&emsp;函数mapiternext用于访问下一个键值对,只需要从当前bmap(hiter.bptr),当前偏移位置(hiter.i + hiter.offset)开始查找下一个键值对即可。如果当前bmap遍历完毕,通过overflow获取下一个bmap;如果当前bucket所有bmap都已遍历完毕,bucket++;而最终再次遍历到hiter.startBucket时,说明当前map已遍历完毕。这里就不再详述,有兴趣的读者可以自己研究下函数mapiternext实现。 &emsp;&emsp;所以for range遍历map的伪代码应该如下: ``` iter := &hiter{} mapiterinit(map, iter) for { if iter.key == nil { //遍历结束 break } k, v := iter.key, iter.elem //用户代码 //访问下一个键值对 mapiternext(iter) } ``` &emsp;&emsp;map的遍历过程我们都很清楚了,现在是否能回答上面遗留的问题呢:遍历过程中,新增键值对,遍历过程并没有无限持续,map最终的键值对数目竟然是随机的!其实不难理解,新增的键值对会存储在哪一个bucket呢?不知道,由键key的hash值决定;每次遍历从哪一个bucket开始呢?不知道,完全随机。那这就对了,如果新增的键值对,刚好存储在未遍历过的位置;那么就会再次访问到,如果刚好存储在已遍历过的位置,那么就不会再次访问到。所以,新增的键值对能否再次被访问到也是随机的,所以,map最终的键值对数目也是随机的。 ## 扩容 &emsp;&emsp;扩容是什么?map为什么需要扩容呢?想想假如初始化时,map的buckets数组长度为8,一直往map新增键值对,会出现什么情况?buckets数组上挂的bmap链表越来越长,这时候map的时间复杂度还是O(1)吗?已经退化为O(N)了!所以,map需要扩容,需要更大的buckets数组。 &emsp;&emsp;那么map什么时候需要扩容呢?这里有一个概念叫负载因子,其表示最大可存储的键值对数目除以buckets数组长度。当map存储的键值对数目超过buckets数组长度乘以负载因子时,触发扩容操作。那么负载因子应该是多少呢?要知道,当buckets数组长度固定时,负载因子越小,可存储的键值对越少,而一个bmap就能存储8个键值对,键值对过少会浪费bmap内存空间;负载因子越大,可存储的键值对越多,键值对过多bmap链表越长时间复杂度又越高。Go语言作者通过简单的程序,测试不同负载因子下,map的一些指标: ``` // loadFactor %overflow bytes/entry hitprobe missprobe // 4.00 2.13 20.77 3.00 4.00 // 4.50 4.05 17.30 3.25 4.50 // 5.00 6.85 14.77 3.50 5.00 // 5.50 10.55 12.94 3.75 5.50 // 6.00 15.27 11.67 4.00 6.00 // 6.50 20.90 10.79 4.25 6.50 // 7.00 27.14 10.15 4.50 7.00 // 7.50 34.03 9.73 4.75 7.50 // 8.00 41.10 9.40 5.00 8.00 // // %overflow = percentage of buckets which have an overflow bucket // bytes/entry = overhead bytes used per key/elem pair // hitprobe = # of entries to check when looking up a present key // missprobe = # of entries to check when looking up an absent key ``` &emsp;&emsp;最终,选取的负载因子是6.5。扩容的时候,一般buckets数组长度扩大2倍,申请新的buckets数组,同时需要将老的buckets数组所有键值对迁移到新的buckets数组,这就需要重新计算hash值,计算buckets数组索引,重新查找bmap空闲位置。要注意,扩容也不是一次性完成的,即键值对的搬迁是逐步分批次完成的,所以在这期间,同时存在两个buckets数组,这时候,map的增删改查该访问哪个buckets数组呢? &emsp;&emsp;其实也是有迹可循的:1)新增/删除/修改键值对,如果当前map正在扩容,计算键key在oldbuckets数组索引,迁移该bucket所有键值对到新buckets数组,继续执行原有新增/删除/修改键值对逻辑;2)键值对查找,如果当前map正在扩容,计算键key在oldbuckets数组b索引,该bucket即为需要查找的bmap。问题来了,如何计算键key在oldbuckets数组索引呢?上面说了,扩容时,buckets数组长度是扩大两倍的,有键key的hash值,有数组长度,计算数组索引还不容易吗?键值对迁移逻辑可以参照下面两个函数: ``` //oldbucket是需要迁移的oldbuckets数组索引,逻辑省略 func evacuate(t *maptype, h *hmap, oldbucket uintptr) //判断该bucket键值对是否已经迁移 func evacuated(b *bmap) bool { h := b.tophash[0] return h > emptyOne && h < minTopHash } //判断是否生在扩容 func (h *hmap) growing() bool { return h.oldbuckets != nil } ``` &emsp;&emsp;所以,假如需要频繁操作map时,并且已经知道需要存储的键值对数目,比如转化切片到map,这时候使用make初始化map,可以指定初始buckets数组长度,避免不必要的扩容。 ## 并发问题 &emsp;&emsp;我们都知道Go语言具有天然的并发优势,go func可以很方便的创建一个并发协程。那么,假如有一个全局的map,在多个协程中并发操作map呢?可以这么操作吗?我们写个小程序测试一下: ``` package main import ( "fmt" "time" ) func main() { var m = make(map[string]int, 0) //创建10个协程 for i := 0; i <= 10; i ++ { go func() { //协程内,循环操作map for j := 0; j <= 100; j ++ { m[fmt.Sprintf("test_%v", j)] = j } }() } //主协程休眠3秒,否则主协程结束了,子协程没有机会执行 time.Sleep(time.Second * 3) fmt.Println(m) } ``` &emsp;&emsp;运行之前可以猜一下执行结果。程序panic了,异常信息为:"fatal error: concurrent map writes"。很明确,并发写map导致的panic,也就是说,我们不能在多个协程并发执行map写操作,这一点要特别注意,初次写Go语言很容易犯这个错。 &emsp;&emsp;其实在函数mapassign很容易找到这些逻辑: ``` func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer { //如果并发写map,报错 if h.flags&hashWriting != 0 { throw("concurrent map writes") } //记录当前map正在执行写操作 h.flags ^= hashWriting //执行结束后,再次判断 done: if h.flags&hashWriting == 0 { throw("concurrent map writes") } h.flags &^= hashWriting } ``` &emsp;&emsp;那假如确实想在多个协程并发操作map怎么办?这就需要采取其他方案了,比如加锁,比如使用并发安全map(sync.Map),这些将在后面章节并发编程详细介绍。 ## 总结 &emsp;&emsp;map就介绍到这里了,要好好理解Go语言map基本结构,包括buckets数组,bmap结构。map在函数传参时的一些现象也不同于slice,map遍历的随机性也需要注意,而map并发访问panic记得千万要避免。

有疑问加站长微信联系(非本文作者))

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

776 次点击  ∙  1 赞  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传