map原理

 map源码结构体：

 type hmap struct {count     int    // 元素的个数B         uint8  // buckets 数组的长度就是 2^B 个overflow uint16 // 溢出桶的数量​buckets    unsafe.Pointer // 2^B个桶对应的数组指针oldbuckets unsafe.Pointer  // 发生扩容时，记录扩容前的buckets数组指针​extra *mapextra //用于保存溢出桶的地址}​type mapextra struct {overflow    *[]*bmapoldoverflow *[]*bmap​nextOverflow *bmap}​type bmap struct {tophash [bucketCnt]uint8}​//在编译期间会产生新的结构体type bmap struct {tophash [8]uint8 //存储哈希值的高8位data    byte[1]  //key value数据:key/key/key/.../value/value/value...overflow *bmap   //溢出bucket的地址}

 

map： bucket中每个元素都是bmap结构，每个bmap保存8个kv键值对，如果8个满了，又来了一个key落在了这个桶里，会使用overflow连接下一个桶。

扩容：

一种是等量扩容 ，一种是增量扩容。

一.等量扩容。

条件：

B：2^B表示bucket的数量， B表示取hash后多少位来做bucket的分组。

1. B> 15时，以15计算，如果overflow的bucket数量超过2^15

2.B<15时，以B计算，如果overflow的bucket数量超过2^B

扩容结果：新建等量大小的map，将旧数据挪过去，元素会发生重排，使数据更加紧凑。

二：增量扩容。

条件： 

装载因子 > 6.5 

装载因子是指当前map中，每个桶中的平均元素个数。

即： 装载因子 =map元素个数/map当前桶个数

扩容结果：2倍的容量扩容（元素会重排，发生渐进式迁移数据）

---

map是线程安全的吗？
答：map不是线程安全的，在对map进行插入、删除、循环遍历的时候只要触发写的操作，就会出现painc异常。但sync.Map是线程安全的。

map是无序的还是有序的，为什么？如何有序输出map？
答：map是无序的。因为map在遍历的时候会先随机生成一个数值。根据这个数值来决定从哪个bucket开始遍历，从bucket的哪个cell开始遍历。因此map不会有序。将map中的key取出来进行排序，然后按照key的顺序进行取值即可有序的输出map。

slice 和 map 分别作为函数参数时有什么区别？
答：makeslice时返回的是一个原类型的slice，而makemap时返回的是一个指针类型的map。因此slice作为参数时，拷贝的是slice的一个副本。map作为参数时，拷贝的时map的地址。当函数内部对map进行修改时也会影响到函数外map的内部值，即使触发了扩容机制也一样。