大话图解golang map
前言网上分析golang中map的源码的博客已经非常多了,随便一搜就有,而且也非常详细,所以如果我再来写就有点画蛇添足了(而且我也写不好,手动滑稽)。但是我还是要写,略略略,这篇博客的意义在于能从几张图片,然后用我最通俗的文字,让没看过源码的人最快程度上了解golang中map是怎么样的。 当然,因为简单,所以不完美。有很多地方省略了细节问题,如果你觉得没看够,或者本来就想了解详细情况的话在文末给出了一些非常不错的博客,当然有能力还是自己去阅读源码比较靠谱。 那么下面我将从这几个方面来说明,你先记住有下面几个方向,这样可以有一个大致的思路:
基础结构图解这个就是golang中map的结构,其实真的不复杂,我省略了其中一些和结构关系不大的字段,就只剩下这些了。 大话大话来描述一些要点:
这就是map的结构,然后我们稍微对比总结一下。
源码一瞥
那么看完结构你肯定会有疑问?为什么要多一层8个格子的bucket呢?我们怎么确定放在8个格子其中的哪个呢?带着问题往下看。 初始化源码一瞥初始化就不需要图去说明了,因为初始化之后就是产生基础的一个结构,根据map中存放的类型不同。这里主要说明一下,初始化的代码放在什么位置。我也删除了其中一些代码,大致看看就好。 // makehmap_small implements Go map creation for make(map[k]v) and // make(map[k]v,hint) when hint is known to be at most bucketCnt // at compile time and the map needs to be allocated on the heap. func makemap_small() *hmap { h := new(hmap) h.hash0 = fastrand() return h } // makemap implements Go map creation for make(map[k]v,hint). // If the compiler has determined that the map or the first bucket // can be created on the stack,h and/or bucket may be non-nil. // If h != nil,the map can be created directly in h. // If h.buckets != nil,bucket pointed to can be used as the first bucket. func makemap(t *maptype,hint int,h *hmap) *hmap { ..... // initialize Hmap if h == nil { h = (*hmap)(newobject(t.hmap)) } h.hash0 = fastrand() // find size parameter which will hold the requested # of elements B := uint8(0) for overLoadFactor(hint,B) { B++ } h.B = B ...... return h } ?
其中需要注意一个点:“B”,还记得刚才说名字叫bmap的桶数量是不确定的吗?这个B一定程度上表示的就是桶的数量,当然不是说B是3桶的数量就是3,而是2的3次方,也就是8;当B为5,桶的数量就是32;记住这个B,后面会用到它。 其实你想嘛,初始化还能干什么,最重要的肯定就是确定一开始要有多少个桶,初始的大小还是很重要的,还有一些别的初始化哈希种子等等,问题不大。我们的重点还是要放在存/取上面。 GET图解其实从结构上面来看,我们已经可以摸到一些门道了。先自己想一下,要从一个hashmap中获取一个元素,那么一定是通过key的哈希值去定位到这个元素,那么想着这个大致方向,看下面一张流程图来详细理解golang中是如何实现的。 大话下面说明要点:
总结一下:通过后B位确定桶,通过前8位确定格子,循环遍历连着的所有桶全部找完为止。 源码一瞥其中红色的字标出的地方说明了上面的关键点,最后有关key和value具体的存放方式和取出的定位不做深究,有兴趣可以看最后的参考博客。 PUT其实当你知道了如何GET,那么PUT就没有什么难度了,因为本质是一样的。PUT的时候一样的方式去定位key的位置:
图解这里主要图解说明一下,如果新来的key发现前面有一个格子空着(这个情况是删除造成的),就会记录这个位置,当全部扫描完成之后发现自己确实是新来的,那么就会放前面那个空着的,而不会放最后(我把这个称为紧凑原则,尽可能保证数据存放紧凑,这样下次扫描会快) 代码位置go/src/runtime/hashmap.go的mapassign函数就是map的put方法,因为代码很长这里就不多赘述了。 扩容这个就是最复杂的地方了,但是呢?Don‘t worry我这里还是会省略其中某些部分,将最重要的地方拎出来。 扩容的方式
扩容的条件装载因子如果你看过Java的HashMap实现,就知道有个装载因子,同样的在golang中也有,但是不一样哦。装载因子的定义是这个样子: 扩容条件1装载因子 > 6.5(这个值是源码中写的) 扩容条件2overflow 的 bucket 数量过多:当 B 小于 15,如果 overflow 的 bucket 数量超过 2B ;当 B >= 15,如果 overflow 的 bucket 数量超过 215 。 扩容条件3当前不能正在扩容 图解这张图表示的就是相同容量的扩容,实际上就是一种整理,将分散的数据集合到一起,提高扫描效率。(上面表示扩容之前,下面表示扩容之后) 这张图表示的是就是2倍的扩容(上面表示扩容之前,下面表示扩容之后),如果有两个key后三位分别是001和101,当B=2时,只有4个桶,只看最后两位,这两个key后两位都是01所以在一个桶里面;扩容之后B=3,就会有8个桶,看后面三位,于是它们就分到了不同的桶里面。 大话下面说一些扩容时的细节:
源码一瞥扩容的三个条件,看到了吗?这个地方在mapassign方法中。 这里可以看到,注释也写的很清楚,如果是加载因子超出了,那么就2倍扩容,如果不是那么就是因为太多溢出桶了,sameSizeGrow表示就是相同容量扩容 evacuate是搬运方法,这边可以看到,每次搬运是1到2个 evacuate实在是太长了,也非常复杂,但是情况就是图上描述的那样,有兴趣的可以详细去看,这里不截图说明了。 总结和小问题至此你应该对于golang中的map有一个基本的认识了,你还可以去看看删除,你还可以去看看遍历等等,相信有了上面的基本认识那么应该不会难到你。下面有几个小问题:
写的仓促,难免疏漏,有问题的地方还请批评指正。 参考资料如果你希望看到源码的各种细节讲解,下面这几篇是我学习的时候看的,供你参考,希望对你有帮助 ? ? 作者:LinkinStar 未经允许,不得转载 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |