map的底层实现是一个链表，因此实现map的实际过程就是实现链表的过程。map主要有两种结构，hmap(a header for a go map)，一个叫bmap(a bucket for a go map, 通常叫做bucket)。
hmap的数据结构：
<br /> bmap的数据结构：<br /> 
哈希表的特点是有一个哈希函数，对你传来的key进行哈希运算，得到唯一的值。一般的情况下都是一个数值，golang的map中也有这么一个哈希函数，也会算出唯一的值，对于这个值的使用，golang也很有意思。
Golang把求得的值按照用途一分为二：高位和低位：
如图所示，蓝色为高位，红色为低位，然后低位用于寻找当前key属于hmap中的哪个bucket，而高位用于寻找bucket中的key。上文中提到，bucket中有个属性字段是“高位哈希值”数组，这里存的就是蓝色的高位值（87897890），便于查找。
map中的key/value是以字节数组形式存放的，数组中的顺序是这样的：
现在我们可以得到go语言map的整个结构图：
map的扩容
当以上的哈希表增长的时候，go语言会将bucket数组的数量扩充一倍，产生一个新的bucket数组，并将就数组的数据迁移至新的数组。
加载因子
判断扩充的条件，就是哈希表中的加载因子（loadFactor）。加载因子是一个阈值，一般为map中的元素数除以位置总数，是一种“产生冲突机会”和“使用空间”的平衡和折中。加载因子越小，说明空间空置率越高，空间使用率越小。但是加载因子越大，说明空间利用率上了，但是产生冲突的机会高了，整个map遍历读就更慢了。
当go的map长度增长大于增长因子所需要的map长度时，go语言就会产生一个新的bucket数组，然后把旧的bucket数组移到oldbucket中。并不是立刻把旧的数组中的元素转移到新的bucket中，而是当访问到具体的某个bucket的时候，会把bucket中的数据转移到新的bucket中。如下图所示，当扩容到时候，Go的map结构体中，会保存旧的数据和生成的新的数组：
上面部分代表旧的数据bucket，下面部分代表新生成的新bucket，蓝色代表有数据的bucket，橘黄色代表空的bucket。
扩容时map并不会立即把新数据做迁移，而是当访问原来旧bucket数据的时候，才把旧数据做迁移：
注意：这里并不是直接删除旧的bucket，而是把原来的引用去掉，利用GC清除内存。
map中数据的删除
如果理解了map的整体结构，那么查找，更新，删除的基本步骤应该都会比较清楚了。这里就不再赘述。值得观察一下：
1. 如果key是一个指针类型，则直接把其值置为nil，等待GC清除2. 如果是值类型的，则清除相关内存3. 同理，对value做相同的操作4. 最后把key对应的高位值对应的数组index清空
参考
https://segmentfault.com/a/1190000039101378
http://zhangtielei.com/posts/blog-redis-dict.html
若有收获，就点个赞吧
0 人点赞
