首先,map为什么需要扩容?
主要是由于哈希碰撞问题
什么情况下会map扩容呢:
- 溢出桶太多时会导致严重的性能下降
- runtime.mapassign()可能会触发扩容的情况
- 装载因子超过6.5个(平均每个槽6.5个key)
- 使用太多溢出桶(溢出桶超过了普通桶)
hash槽和桶的定义可以自己去了解下
map的两种扩容类型:
- 等量扩容(整理):数据不多但是溢出桶太多了,使数据更紧凑
- 翻倍扩容:数据太多了增加普通桶的数量
map的扩容过程:
1. 步骤一
- 创建一组新桶
- oldbuckets指向原有的桶数组
- buckets指向新的桶数组
- 把map标记为扩容状态
2. 步骤二
- 将所有的数据从旧桶驱逐到新桶
- 采用渐进式驱逐**(好多技术都有这种思想,比如redis的rehash)**
- 每次操作一个旧桶的时,将旧数据驱逐到新桶
- 读取时不进行驱逐,只判断读取新桶还是旧桶
3. 步骤三
- 所有的旧桶驱逐完成后
- oldbuckets回收
总结:
- 装载系数或者溢出桶的增加,会触发map扩容
- “扩容”可能并不是增加桶的数量,而是整理数据,使数据更加紧凑
- map扩容采用渐进式,桶被操作时才会重新分配