总结下这段程序，主要有几个部分：

a. map hash 不匹配的情况，会看是否是空kv 。如果调用了delete，会出现空kv的情况，那先把地址留下，如果后面也没找到对应的k（也就是说之前map 里面没有对应的Key），那就直接用空kv的位置即可。

b. 如果 map hash 是匹配的，需要判定key 的字面值是否匹配。如果不匹配，还需要查找。如果匹配了，那直接把key 更新（因为可能有引用），v的地址返回即可。

c. 如果上面都没有，那就看下一个bucket

⑤ 插入数据前，会先检查数据太多了，需要扩容，如果需要扩容，那就从第③开始拿到新的bucket，并查找对应的位置。

if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
  hashGrow(t, h)
  goto again // Growing the table invalidates everything, so try again
}

⑥ 如果刚才看没有有空的位置，那就需要在链表后追加一个bucket，拿到kv。

if inserti == nil {
  // all current buckets are full, allocate a new one.
  newb := h.newoverflow(t, b)
  inserti = &newb.tophash[0]
  insertk = add(unsafe.Pointer(newb), dataOffset)
  val = add(insertk, bucketCnt*uintptr(t.keysize))
}

⑦ 最后更新tophash 和 key 的字面值, 并解除hashWriting 约束

// 如果非指针数据（也就是直接赋值的数据），还需要申请内存和拷贝
if t.indirectkey() {
  kmem := newobject(t.key)
  *(*unsafe.Pointer)(insertk) = kmem
  insertk = kmem
}
if t.indirectvalue() {
  vmem := newobject(t.elem)
  *(*unsafe.Pointer)(val) = vmem
}
// 更新tophash, k
typedmemmove(t.key, insertk, key)
*inserti = top

done:
if h.flags&hashWriting == 0 {
    throw("concurrent map writes")
  }
  h.flags &^= hashWriting
  if t.indirectvalue() {
    val = *((*unsafe.Pointer)(val))
  }
  return val

到这里，map的赋值基本就介绍完了。下面学习下步骤⑤中的map的扩容。

Map 的扩容

有两种情况下，需要做扩容。一种是存的kv数据太多了，已经超过了当前map的负载。还有一种是overflow的bucket过多了。这个阈值是一个定值，经验得出的结论，所以我们这里不考究。

当满足条件后，将开始扩容。如果满足条件二，扩容后的buckets 的数量和原来是一样的，说明可能是空kv占据的坑太多了，通过map扩容做内存整理。如果是因为kv 量多导致map负载过高，那就扩一倍的量。

func hashGrow(t *maptype, h *hmap) {
  bigger := uint8(1)
  // 如果是第二种情况，扩容大小为0
  if !overLoadFactor(h.count+1, h.B) {
    bigger = 0
    h.flags |= sameSizeGrow
  }
  oldbuckets := h.buckets

  // 申请一个大数组，作为新的buckets
  newbuckets, nextOverflow := makeBucketArray(t, h.B+bigger, nil)

  flags := h.flags &^ (iterator | oldIterator)
  if h.flags&iterator != 0 {
    flags |= oldIterator
  }
  
  // 然后重新赋值map的结构体，oldbuckets 被填充。之后将做搬迁操作
  h.B += bigger
  h.flags = flags
  h.oldbuckets = oldbuckets
  h.buckets = newbuckets
  h.nevacuate = 0
  h.noverflow = 0

  // extra 结构体做赋值
  if h.extra != nil && h.extra.overflow != nil {
    // Promote current overflow buckets to the old generation.
    if h.extra.oldoverflow != nil {
      throw("oldoverflow is not nil")
    }
    h.extra.oldoverflow = h.extra.overflow
    h.extra.overflow = nil
  }
  if nextOverflow != nil {
    if h.extra == nil {
      h.extra = new(mapextra)
    }
    h.extra.nextOverflow = nextOverflow
  }
}

总结下map的扩容操作。首先拿到扩容的大小，然后申请大数组，然后做些初始化的操作，把老的buckets，以及overflow做切换即可。

map 数据的迁移

扩容完成后，需要做数据的迁移。数据的迁移不是一次完成的，是使用时才会做对应bucket的迁移。也就是逐步做到的数据迁移。下面我们来学习。

在数据赋值的第③步，会看需要操作的bucket是不是在旧的buckets里面，如果在就搬迁。下面是搬迁的具体操作：

func growWork(t *maptype, h *hmap, bucket uintptr) {
  // 首先把需要操作的bucket 搬迁
  evacuate(t, h, bucket&h.oldbucketmask())
  
  // 再顺带搬迁一个bucket
  if h.growing() {
    evacuate(t, h, h.nevacuate)
  }
}

nevacuate 标识的是当前的进度，如果都搬迁完，应该和2^B的长度是一样的（这里说的B是oldbuckets 里面的B，毕竟新的buckets长度可能是2^(B+1))。

在evacuate 方法实现是把这个位置对应的bucket，以及其冲突链上的数据都转移到新的buckets上。

① 先要判断当前bucket是不是已经转移。 (oldbucket 标识需要搬迁的bucket 对应的位置)

b := (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.bucketsize)))
// 判断
if !evacuated(b) {
  // 做转移操作
}

转移的判断直接通过tophash 就可以，判断tophash中第一个hash值即可 （tophash的作用可以参考第三讲）

func evacuated(b *bmap) bool {
  h := b.tophash[0]
  // 这个区间的flag 均是已被转移
  return h > emptyOne && h 
	
② 如果没有被转移，那就要迁移数据了。数据迁移时，可能是迁移到大小相同的buckets上，也可能迁移到2倍大的buckets上。这里xy 都是标记目标迁移位置的标记：x 标识的是迁移到相同的位置，y 标识的是迁移到2倍大的位置上。我们先看下目标位置的确定：

	
var xy [2]evacDst
x := &xy[0]
x.b = (*bmap)(add(h.buckets, oldbucket*uintptr(t.bucketsize)))
x.k = add(unsafe.Pointer(x.b), dataOffset)
x.v = add(x.k, bucketCnt*uintptr(t.keysize))
if !h.sameSizeGrow() {
  // 如果是2倍的大小，就得算一次 y 的值
  y := &xy[1]
  y.b = (*bmap)(add(h.buckets, (oldbucket+newbit)*uintptr(t.bucketsize)))
  y.k = add(unsafe.Pointer(y.b), dataOffset)
  y.v = add(y.k, bucketCnt*uintptr(t.keysize))
}

	
③ 确定bucket位置后，需要按照kv 一条一条做迁移。（目的就是清除空闲的kv）

	
// 遍历每个bucket
for ; b != nil; b = b.overflow(t) {
  k := add(unsafe.Pointer(b), dataOffset)
  v := add(k, bucketCnt*uintptr(t.keysize))

  // 遍历bucket 里面的每个kv
  for i := 0; i 
	
对于key 非间接使用的数据（即非指针数据），做内存回收

	
if h.flags&oldIterator == 0 && t.bucket.kind&kindNoPointers == 0 {
  b := add(h.oldbuckets, oldbucket*uintptr(t.bucketsize))
  ptr := add(b, dataOffset)
  n := uintptr(t.bucketsize) - dataOffset

  // ptr 是kv的位置， 前面的topmap 保留，做迁移前的校验使用
  memclrHasPointers(ptr, n)
}

	
④ 如果当前搬迁的bucket 和 总体搬迁的bucket的位置是一样的，我们需要更新总体进度的标记 nevacuate

	
// newbit 是oldbuckets 的长度，也是nevacuate 的重点
func advanceEvacuationMark(h *hmap, t *maptype, newbit uintptr) {
  // 首先更新标记
  h.nevacuate++

  // 最多查看2^10 个bucket
  stop := h.nevacuate + 1024
  if stop > newbit {
    stop = newbit
  }

  // 如果没有搬迁就停止了，等下次搬迁
  for h.nevacuate != stop && bucketEvacuated(t, h, h.nevacuate) {
    h.nevacuate++
  }

  // 如果都已经搬迁完了，oldbukets 完全搬迁成功，清空oldbuckets
  if h.nevacuate == newbit {
    h.oldbuckets = nil
    if h.extra != nil {
      h.extra.oldoverflow = nil
    }
    h.flags &^= sameSizeGrow
  }
}

	
总结

	
    
		
  1. Map 的赋值难点在于数据的扩容和数据的搬迁操作。
    2. 
		
  2. bucket 搬迁是逐步进行的，每进行一次赋值，会做至少一次搬迁工作。
    3. 
		
  3. 扩容不是一定会新增空间，也有可能是只是做了内存整理。
    4. 
		
  4. tophash 的标志即可以判断是否为空，还会判断是否搬迁，以及搬迁的位置为X or Y。
    5. 
		
  5. delete map 中的key，有可能出现很多空的kv，会导致搬迁操作。如果可以避免，尽量避免。
    6.