Map底层原理

map是一种数据结构，用于存储一系列无序的键值对，里面是基于键来存储的，这样我们可以通过键很快的找到对应的值。

内部实现介绍

Go底层是一个散列表，散列表里头包含一组捅，当在存储、删除及查找键值对的时候，所有的操作都是需要选择一个捅，把操作映射时指定的键传给映射的散列函数进行计算，就能找到对应的捅。通过合理数量的桶来平衡键值对的分布，这样大大提高查找效率。

栗子：

上面声明一个map，键值都是string类型，首先，看一看键是字符串，在map底层是如何存储的。

将字符串作为map的键，底层会通过哈希函数计算出散列值，然而该散列值在映射的序号范围内表示可以用于存储的捅序号。得到的散列值用于选择那个捅，也用于存储在及查找指定的键值对是非常方便。

深入剖析map底层

Go的map有自己的底层实现原理，其中最核心是由hmap 和 bmap这两个结构体实现。

（1）Map初始化，底层会做哪些骚动作？

假设，你初始化一个容量为5个元素的map

go/src/runtime/map.go

源码：

（2）添加数据时，又发生什么呢？

第一步：首先会通过你传的key，结合哈希因子生成哈希值

第二步：拿到哈希值后B位（哈希值是二进制）来确定该数据应该存储在那个捅(Bmap)

第三步：确定捅之后，就可以添加数据了，存储的是将高8位存储到Bmap里面tophash，添加捅满的时候，会通过overflow找到溢出捅。

源码：

（3）读取数据会发生什么？

第一步：结合哈希因子和键生成哈希值

第二步：通过哈希值的后B位的值来确定该键存储对应的捅(Bmap)

第三步：然后根据tophash(高8位)去捅里面查询对应数据

（4）Map扩容

何时出发扩容机制？

扩容条件：

  • map数据总个数 / 捅个数 > 6.5 ，会触发翻倍扩容
  • 使用太多的溢出捅（溢出捅使用太多会导致map处理速度降低）
    • B <= 15 已使用的溢出捅个数 >= 2的B次方时，触发等量扩容
    • B > 15 已使用的溢出捅个数 >= 2的15次方时，触发等量扩容

源码：

（5）扩容后数据迁移发生了什么？

翻倍扩容：如果发生翻倍扩容时，那么迁移是将旧捅数据导入到新捅，根据哈希值来迁移的，具体实现。

将旧捅遍历

（6）其他扩展

map作为函数参数，有什么特点？

注：该栗子，证明map作为函数参数，是地址传递，而不值传递。

（7）map特点

  • 键不能重复
  • 键必须可以哈希（也就是说必须能作为计算的哈希）
  • 无序

Map的知识点还有很多细节，值得我们学习，这里有些还没有讲到，比如Map并发安全吗？这块我放到并发的时候来讲。

创作不易，你的点赞支持，便是我创作最大动力！