首先,map为什么需要扩容?

主要是由于哈希碰撞问题
在这里插入图片描述

什么情况下会map扩容呢:

  • 溢出桶太多时会导致严重的性能下降
  • runtime.mapassign()可能会触发扩容的情况
    • 装载因子超过6.5个(平均每个槽6.5个key)
    • 使用太多溢出桶(溢出桶超过了普通桶)

hash槽和桶的定义可以自己去了解下



map的两种扩容类型:

  1. 等量扩容(整理):数据不多但是溢出桶太多了,使数据更紧凑
  2. 翻倍扩容:数据太多了增加普通桶的数量


map的扩容过程:

1. 步骤一

  1. 创建一组新桶
  2. oldbuckets指向原有的桶数组
  3. buckets指向新的桶数组
  4. 把map标记为扩容状态

在这里插入图片描述


2. 步骤二

  1. 将所有的数据从旧桶驱逐到新桶
  2. 采用渐进式驱逐**(好多技术都有这种思想,比如redis的rehash)**
  3. 每次操作一个旧桶的时,将旧数据驱逐到新桶
  4. 读取时不进行驱逐,只判断读取新桶还是旧桶

在这里插入图片描述


3. 步骤三

  1. 所有的旧桶驱逐完成后
  2. oldbuckets回收

在这里插入图片描述



总结:

  • 装载系数或者溢出桶的增加,会触发map扩容
  • “扩容”可能并不是增加桶的数量,而是整理数据,使数据更加紧凑
  • map扩容采用渐进式,桶被操作时才会重新分配