Map使用

声明 & 默认值

map的声明的时候默认值是nil （也就是没有分配地址空间，如果需要空间就得使用make），此时进行取值，返回的是对应类型的零值（不存在也是返回零值）。
image.png

初始化

我们需要在初始化哈希时声明键值对的类型
image.pngimage.png

新增 & 删除 & 更新 & 查询

image.png

底层原理

map的数据结构

使用哈希表作为底层实现，一个哈希表中有多个哈希表节点bucket，每个bucket保存了map中的一个或一组键值对。
image.png
举例拥有4个bucket的map
image.png

bucket数据结构

image.png
image.png

参数理解

1、每个bucket可以存储8个键值对。
2、tophash这样理解：理解tophash之前要知道的流程，拿过来一个key进哈希函数。生成一个64位的数，用这个key生成的数先看低B位，因为hmap中定义个2^B长度的bucket数组。比如B=5，低5位00011就是定位到bucket数组的第3个bucket（哈希表节点）。每个key生成的高8位放进tophash，记住是每一个key生成的哈希函数值都取他的高8位。tophash最多存8个这样的高8位。然后存进tophash用于索引bucket节点中的key，进而取得value。如果tophash中没找到且overflow不是空的，则会沿着overflow继续查找，直至遍历所有bucket。一个确定第几个bucket，一个是确定是bucket内的哪个kv。
3、data区存放的是key-value数据，存放顺序是key/key/key/…value/value/value，如此存放是为了节省字节对齐带来的空间浪费。
4、overflow 指针指向的是下一个bucket，据此将所有冲突的键连接起来。

哈希冲突

当有两个或以上数量的键（key不一样）被哈希到了同一个bucket时，我们称这些键发生了冲突。Go使用链地址法来解决键冲突。由于每个bucket可以存放8个键值对，所以同一个bucket存放超过8个键值对时就会再创建一个键值对，用类似链表的方式将bucket连接起来。bucket数据结构指示下一个bucket的指针称为overflow bucket，意为当前bucket盛不下而溢出的部分。
image.png

负载因子

负载因子用于衡量一个哈希表冲突情况，公式为：负载因子 = 键数量/bucket数量。
例如，对于一个bucket数量为4，包含4个键值对的哈希表来说，这个哈希表的负载因子为1
哈希因子过小，说明空间利用率低
哈希因子过大，说明冲突严重，存取效率低
每个哈希表的实现对负载因子容忍程度不同，比如Redis实现中负载因子大于1时就会触发rehash，而Go则在在负载因子达到6.5时才会触发rehash，
因为Redis的每个bucket只能存1个键值对，而Go的bucket可能存8个键值对，所以Go可以容忍更高的负载因子。

渐进式扩容

扩容的前提条件

为了保证访问效率，当新元素将要添加进map时，都会检查是否需要扩容，扩容实际上是以空间换时间的手段。触发扩容的条件有二个。负载因子 > 6.5时，也即平均每个bucket存储的键值对达到6.5个。overflow数量 > 2^15时，也即overflow数量超过32768时。

增量扩容

当负载因子过大时，就新建一个bucket，新的bucket长度是原来的2倍（但是每个bucket还是只能存8个kV），然后旧bucket数据搬迁到新的bucket。
image.png

举例

当前map存储了7个键值对，只有1个bucket。此地负载因子为7。再次插入数据时将会触发扩容操作，扩容之后再将新插入键写入新的bucket。当第8个键值对插入时，将会触发扩容
image.png
hmap数据结构中oldbuckets成员指身原bucket，而buckets指向了新申请的bucket。新的键值对被插入新的bucket中。后续对map的访问操作会触发迁移，将oldbuckets中的键值对逐步的搬迁过来。当oldbuckets中的键值对全部搬迁完毕后，删除oldbuckets。（从bucket0——>bucket00，bucket11）

等量扩容

所谓等量扩容，实际上并不是扩大容量，buckets数量不变，重新做一遍类似增量扩容的搬迁动作，把松散的键值对重新排列一次，以使bucket的使用率更高，进而保证更快的存取。
image.png
overflow的buckt中大部分是空的，访问效率会很差。此时进行一次等量扩容，即buckets数量不变，经过重新组织后overflow的bucket数量会减少，即节省了空间又会提高访问效率。

查找过程

image.png

插入过程

image.png

为什么遍历map每次结果不同？

回答：
Go的Map本质上是“无序的”
1. 正常写入(非哈希冲突写入)：是hash到某一个bucket上，而不是按buckets顺序写入。
2. 哈希冲突写入：如果存在hash冲突，会写到同一个bucket上。
可能写到这个位置：
image.png
极限情况，也可能写到这个位置：
image.png
更有可能写到溢出桶去：
image.png
所以，写数据时，并没有单独维护键值对的顺序。
第二个原因就是扩容迫使元素顺序变化