首先还是提出问题：扩容和缩容有什么用？为什么需要扩容和缩容？

转自:https://studygolang.com/articles/30937#reply0

参考：go语言中文文档：www.topgoer.com

在想解答这个问题之前，首先还是需要了解一下go语言中的map

go语言中的map与Java中的map实现还是有些不同，go的map底层实现方式是hash表(哈希桶+数组)，Java中，JDK1.6，JDK1.7里HashMap采用位桶+链表实现，JDK1.8中，HashMap采用位桶+链表+红黑树实现，当链表长度超过阈值(8)时，将链表转换为红黑树。

先看map的数据结构吧：

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，溢出桶的具体情况下面来具体说明一下：(先给图：网上随便找的不知道是谁的了)

• hmap的B为1，那么进行初始化的时候会生成2^B个桶(bucket1，bucket2)
• 先存入8个key-value，根据一些列的hash算法，然后很不巧的这8个都被存入到了bucket1里面去了
• 现在又有一个key-value来了，根据hash算法，它应该又被分配到了b1里面去，但是最多存8个，现在已经有8个了，这时候怎么办，重新一个hash算法将所有的数据再次分配，不好意思，我也不知道为什么不行，大概没必要，且有根好的做法
• 在原本的bucket1后面再建一个bucket1*，再将这个key-value存进去。上面至于为什么不进行扩容，没办法，没满足要求：

func overLoadFactor(count int, B uint8) bool {    return count > bucketCnt && uintptr(count) > loadFactorNum*(bucketShift(B)/loadFactorDen)}

• map的数据量count大于(2^B)*6.5。注意这里不包括溢出的桶。这里补充插入时的一些操作：

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里面也有缩容判断，不过这个缩容是伪缩容，

func tooManyOverflowBuckets(noverflow uint16, B uint8) bool {    if B > 15 {        B = 15    }    return noverflow >= uint16(1)<=32768(1<<15)}

只有溢出桶太多才会缩容，不过内存大小并不会发生变化，至于为什么不会变化，因为B没有变，想要真正实现内存的优化也是可行的，不过并不会太优雅。这时候就需要我们需要手动缩容了，说这么多，其实代码很简单：

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，可以了解一下