Map - 图1

Map的哈希函数（与运算）

桶的数量一定是2的整数次幂，否则采用与运算哈希函数一定会出现空桶（不会被选中）。
桶的
image.png
图中：若桶的数量为5，则m-1=4，则hash值进行与运算只可能等于0或4，所以1,3,5必为空桶

哈希表的迁移

渐进式扩容

发生哈希表迁移时，哈希表不会一次性把所有的数据从旧表迁移到新表，而是每次哈希操作的时候迁移一部分。
image.png

Map的结构

image.png
bmap是桶的结构
image.png
image.png
例子：
image.png

扩容

image.png
image.png
m=4时，m-1 = 011
m=8时， m-1 = 111
因此，旧桶中的数据会根据hash值 在上图红圈所在的位 的值 为0或1，0被分到0-3位，1被分到4-7位。

image.png
负载因子较小，但是使用溢出桶较多，说明桶中大量键值对被删除，所以使用等量扩容进行键值对整理