map的自动扩容与手动缩容

TonoT · · 1287 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

### map的自动扩容与手动缩容 首先还是提出问题:*扩容和缩容有什么用?为什么需要扩容和缩容?* 在想解答这个问题之前,首先还是需要了解一下go语言中的map go语言中的map与Java中的map实现还是有些不同,go的map底层实现方式是hash表(哈希桶+数组),Java中,JDK1.6,JDK1.7里HashMap采用位桶+链表实现,JDK1.8中,HashMap采用位桶+链表+红黑树实现,当链表长度超过阈值(8)时,将链表转换为红黑树。 先看map的数据结构吧: ```go const ( bucketCntBits = 3 bucketCnt = 1 << bucketCntBits // 一个桶最多存储8个key-value对 loadFactorNum = 13 // 扩散因子:loadFactorNum / loadFactorDen = 6.5。触发扩容 loadFactorDen = 2 ) type hmap struct { count int flags uint8 // 记录几个特殊的位标记,如当前是否有别的线程正在写map、当前是否为相同大小的增长(扩容/缩容?) B uint8 // hash桶buckets的数量为2^B个 noverflow uint16 hash0 uint32 // hash种子 buckets unsafe.Pointer // 指向2^B个桶组成的数组的指针,数据存在这里 oldbuckets unsafe.Pointer nevacuate uintptr // 计数器,标示扩容后搬迁的进度 extra *mapextra // 保存溢出桶的链表和未使用的溢出桶数组的首地址 } type mapextra struct { overflow *[]*bmap oldoverflow *[]*bmap nextOverflow *bmap //保存为使用的数组桶地址 } type bmap struct { tophash [8]uint8 //存储哈希值的高8位 data byte[1] //key value数据:key/key/key/.../value/value/value... 如此存放是为了节省 字节对齐带来的空间浪费。 overflow *bmap //溢出bucket的地址 } ``` 以上面的代码来说说吧,hmap是map的数据结构,bmap是真正用来存放数据的地方,一个bmap内能够存放8个键值对(很神奇吧,很多语言的阈值为8,这是一个神奇的数字),tophash有8个字节,这是用来干嘛的,总要区分一下桶里的key吧,data是数据,overflow是来干嘛的?也是用来存数据,这里不要和extra弄混,extra预留的桶,可以被用来作为overflow,溢出桶的具体情况下面来具体说明一下:(先给图:网上随便找的不知道是谁的了) ![在这里插入图片描述](https://img-blog.csdnimg.cn/20200929220534347.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTgyOTY1NQ==,size_16,color_FFFFFF,t_70#pic_center) + hmap的B为1,那么进行初始化的时候会生成2^B个桶(bucket1,bucket2) + 先存入8个key-value,根据一些列的hash算法,然后很不巧的这8个都被存入到了bucket1里面去了 + 现在又有一个key-value来了,根据hash算法,它应该又被分配到了b1里面去,但是最多存8个,现在已经有8个了,这时候怎么办,重新一个hash算法将所有的数据再次分配,不好意思,我也不知道为什么不行,大概没必要,且有根好的做法 + 在原本的bucket1后面再建一个bucket1*,再将这个key-value存进去。 上面至于为什么不进行扩容,没办法,没满足要求: ```go func overLoadFactor(count int, B uint8) bool { return count > bucketCnt && uintptr(count) > loadFactorNum*(bucketShift(B)/loadFactorDen) } ``` map的数据量count大于(2^B)*6.5。注意这里不包括溢出的桶。 这里补充插入时的一些操作: ```go if h.flags&hashWriting != 0 { throw("concurrent map writes") } ``` 这就是为什么同时读写map为什么会报错的原因了,加锁就行。 基本了解了数据结构,接着说扩容,还是上面的例子,B=1,扩容因为6.5,当key-value的数量达到13的时候(包括已经删除的),会触发扩容,B=B+1,容量扩大了一倍。为什么会包括已经删除的,其实这里描述的不太准确,mapdelete里面的具体操作是这样的: + 当这个被删除的key不是当前桶(包括溢出桶)里面的最后一个有效key时,则只置emptyOne标志,该位置被删除但未内存没有被释放,后续插入操作不能使用此位置 + 如果只剩最后一个有效节点了也被删除了,则把桶里面所有标志为emptyOne的位置,都置为emptyRest。置为emptyRest的位置可以在后续的插入操作中被使用。 为什么这么做: **这种删除方式,以少量空间来避免桶链表和桶内的数据移动。事实上,go 数据一旦被插入到桶的确切位置,map是不会再移动该数据在桶中的位置了。** 那么这个删除模式会导致一种情况,就是每个桶里面只有一个数据,造成了很大的空间浪费了,想想map只增不减情况,这时候就需要缩容了。go里面也有缩容判断,不过这个缩容是伪缩容, ```go func tooManyOverflowBuckets(noverflow uint16, B uint8) bool { if B > 15 { B = 15 } return noverflow >= uint16(1)<<(B&15) //溢出的桶数量noverflow>=32768(1<<15) } ``` 只有溢出桶太多才会缩容,不过内存大小并不会发生变化,至于为什么不会变化,因为B没有变,想要真正实现内存的优化也是可行的,不过并不会太优雅。这时候就需要我们需要手动缩容了,说这么多,其实代码很简单: ```go oldMap := make(map[int]int, 100000) newMap := make(map[int]int, len(oldMap)) for k, v := range oldMap { newMap[k] = v } oldMap = newMap ``` map还有一个比较有意思的是for range,可以了解一下

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

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

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