go语言map系列（二）

「这是我参与2022首次更文挑战的第28天，活动详情查看：2022首次更文挑战」。

前言

上篇文章简单介绍了map的一些操作，今天从底层原理再重新了解下map。

回顾下底层数据结构

type hmap struct {
   count     int 
   flags     uint8
   B         uint8 
   noverflow uint16 
   hash0     uint32 
   buckets    unsafe.Pointer 
   oldbuckets unsafe.Pointer 
   nevacuate  uintptr       
   extra *mapextra 
}

上篇文章介绍了桶的数据结构里面有tophash，其存储的是hash的高八位，简单补充下如果首位是0代表后续kv对不存在，只要首位小于5都属于异常值，不过其他值会在讲搬迁的时候介绍到。

创建map

当初始化map大小小于8时，会直接在堆上分配内存。（也算是go语言常规操作了。）

makemap函数分为以下几部分

• 通过数据大小判断是否会溢出（如果溢出后续会在mapassign处理哈希冲突）
• makeBucketArray根据桶的数量创建一个数组 makeBucketArray的任务是
• 如果B大于4，则需要预分配一些溢出桶，溢出桶和桶的内存空间是连续的
• 为桶分配内存时，如果桶本身存在已分配内存，则会将其清零后服用

哈希操作

在对key经过hash操作后得到A，我们之前有提到过，桶的内部通过高八位来区别key，那么A的低位就是用来区别是在哪个桶，至于低几位很明显需要考虑B，又是奇妙的二进制.

最开始一个桶里没有key，则会存入第一空位，那如果第二个key也存入一个桶中，就会产生哈希冲突，go语言实践中会讲其存在下一个空位（如果没有，则存入溢出桶中）。

通过上面我们也可以推测出在查找时，实际上时根据tophash来寻找对应的kv对，如果找不到，那么就再查一次溢出桶。