map的自动扩容与手动缩容

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