https://mp.weixin.qq.com/s/2CDpE5wfoiNXm1agMAq4wA
1.map内存模型：hashmap，结构为如下图，bucket存储key和value，而buckets的长度为2*B,而每个bucket最多存储8个key,当有第九个k-v对落入该bucket 时，那就需要再构建一个 bucket ，通过 overflow 指针连接起来
https://mp.weixin.qq.com/s/2CDpE5wfoiNXm1agMAq4wA
2.哈希类型：在程序启动时，会检测 cpu 是否支持 aes，如果支持，则使用 aes hash，否则使用 memhash
bucket里面的存储（https://mp.weixin.qq.com/s/2CDpE5wfoiNXm1agMAq4wA）
3.key如何定位：key经过哈希计算得到哈希值，共64个bit位，计算在哪个bucket时只需看最后B个bit位，再用最高8个bit位计算在bucket的位置，当添加时，会找到第一个空位进行插入，如果bucket没有找到则判断overflow是不是nil,如果不是继续查找，知道查到为止
如何解决不同key放入到同一个bucket中，使用链表法：从前往后找到第一个空位放入
源于曹大大的博客
4.扩容：如果所有的key都落到了一个bucket，直接退化成了链表，时间复杂度又变成了O(N),因此，需要有一个指标来衡量前面描述的情况，这就是 装载因子 "loadFactor := count / (2^B)", count 就是 map 的元素个数，2^B 表示 bucket 数量，扩容是渐进式的，每次最多搬迁两个 bucket，触发扩容的条件：
(1)装载因子超过阈值，源码里定义的阈值是 6.5。造成的原因：bucket过少，key值过多 解决办法：B+1
(2)overflow 的 bucket 数量过多：当 B 小于 15，也就是 bucket 总数 2^B 小于 2^15 时，如果 overflow 的 bucket 数量超过 2^B；当 B >= 15，也就是 bucket 总数 2^B 大于等于 2^15，如果 overflow 的 bucket 数量超过 2^15。 造成的原因：不停地插入，后删除，导致overflow bucket会很多，但是由于删除，key值相对分散，也造成插入查询缓慢。 解决办法：创建新的bucket，将老得bucket移动到新的bucket
5.map为什么是无序的
其实当扩容的时候肯定顺序肯定和之前的不一样，因为有的去了别的bucket，有的还在原地，但是当我新建个map的时候，添加完数据后，不做任何添加和删除的操作，那按理说他一直是有序的，但是go为了杜绝这种桉顺序返回的情况，它并不是固定地从 0 号 bucket 开始遍历，每次都是从一个随机值序号的 bucket 开始遍历，并且是从这个 bucket 的一个随机序号的 cell 开始遍历
6.map遍历：map 遍历的核心在于理解 2 倍扩容时，老 bucket 会分裂到 2 个新 bucket 中去。而遍历操作，会按照新 bucket 的序号顺序进行，碰到老 bucket 未搬迁的情况时，要在老 bucket 中找到将来要搬迁到新 bucket 来的 key -----具体讲解看原文
7.map的赋值/更新和删除：都是双层循环，外层循环bucket和overflow bucket，内层循环bucket中的cell，赋值时根据计算key值得到哈希值，根据后B位bit,和高8位(同上)，计算出第几个bucket以及bucket对应的cell, 需准备两个指针，一个指针用于指定第几个数组(bucket)，另一个用于指向第几个cell,此时value值对应的地址也就出来了，“跨过” 8 个 key 的长度则是value的地址，这些操作前都会先检查map中flag的标志，如果是1则直接Panic，因为map是线程不安全的，赋值/删除都会修改map中count值，代表map的个数
总结：通过哈希查找表实现 map，用链表法解决哈希冲突
网友评论