map底层是由哈希表实现的
Go使用链地址法来解决键冲突。
map本质上是一个指针,指向hmap
这里的buckets就是桶,bmap
每一个bucket最多可以放8个键值对,但是为了让内存排列更加紧凑,8个key放一起,8个value放一起。在8个key前面是8个tophash,每个tophash都是对应哈希值的高8位,最后由一个overflow字段指向下一个bmap,就是溢出桶。溢出桶内存布局和常规桶一样,bmap内存布局如图
如果哈希表要分配的桶的数目大于24,就会预分配2(B-4)个溢出桶备用。
这些溢出桶和常规桶在内存中是连续的,前2^B个用作常规桶,后面的用作溢出桶
新元素插入过程如下:
为了保证访问效率,当新元素将要添加进map时,都会检查是否需要扩容,扩容实际上是以空间换时间的手段。
触发扩容的条件有二个:
负载因子 > 6.5时,也即平均每个bucket存储的键值对达到6.5个。
负载因子 = 键数量/bucket数量
溢出桶(overflow)数量 > 2^15时,也即overflow数量超过32768时。
如果负载因子>6.5时,进行增量扩容。这时会新建一个桶(bucket),新的bucket长度是原来的2倍,然后旧桶数据搬迁到新桶。每个旧桶的键值对都会分流到两个新桶中
考虑到如果map存储了数以亿计的key-value,一次性搬迁将会造成比较大的延时,Go选择“渐进式扩容”,先分配2倍内存空间的新桶,然后标记当前哈希表正在扩容,每次访问map时都会触发一次搬迁,这样可以把扩容消耗的时间分散到多次操作中。
负载因子没超标,溢出桶较多
如果常规桶数目不大于2^15,那么使用的溢出桶数目超过常规桶就算是多了;
如果常规桶数目大于215,那么使用溢出桶数目一旦超过215就算多了。
所谓等量扩容,就是创建和旧桶数目一样多的新桶,然后把原来的键值对迁移到新桶中,重新做一遍类似增量扩容的搬迁动作。这样做的目的是把松散的键值对重新排列一次,能够存储的更加紧凑,进而减少溢出桶的使用,以使bucket的使用率更高,进而保证更快的存取。