Go语言map解析之key的定位核心流程

1 哈希表

创新互联建站是专业的弥勒网站建设公司，弥勒接单;提供网站设计、网站建设,网页设计,网站设计,建网站,PHP网站建设等专业做网站服务;采用PHP框架,可快速的进行弥勒网站开发网页制作和功能扩展;专业做搜索引擎喜爱的网站,专业的做网站团队,希望更多企业前来合作!

哈希表属于编程中比较常见的数据结构之一，基本上所有的语言都会实现数组和哈希表这两种结构，Hash table 的历史是比较悠远的，我们在编程时也是离不开的，这种数据结构的作用其实很简单，就是我们可以根据一个 key 可以查找到对应的 value，也就是说这种数据结构存储的是键值对的“列表”。

1.1 原理

首先哈希表中第一个点就是哈希函数，也就是我们需要一个函数，根据我们的 key 计算出一个值，然后根据这个值可以直接找到对应的 value。因为我们的哈希表的一个作用就是 O(1) 复杂度找到 key 对应的 value。

完美的哈希函数是可以做到将任何一个 key 值都可以计算出一个唯一且固定大小的值，不幸的是目前世界上还没有这种完美的哈希函数。因此我们需要解决的另外一个问题就是哈希冲突的解决。

1.1.1 哈希冲突

假如我们有两个不同的 key，通过哈希函数计算出的结果相同，那么我们是不能认为这两个 key 在 map 中是相同的，也就是如果出现了这种情况，我们的 map 结构是可以解决这个问题的。目前解决办法有很多，这里只说三个比较常见的解决方案：

开放地址法(Open Addressing)：

  • 写入时：假如 key Alice 与 Bob 通过哈希函数计算出结果冲突。当 map 中已经存在 key Alice，再写入 key 为 Bob时，发现哈希结果对应位置已经存在 Alice，此时在 Alice 位置之后再寻找位置，一直找到为空的位置，将 Bob 写入。
  • 读取时：此时 map 中已存在 key Alice、Bob，且哈希结果相同，此时想查找 Bob 对应 value 时，先计算 Bob 哈希结果，再通过哈希结果在 map 中查找位置，此时由于和 Alice 哈希结果相同，并且 Alice 先于 Bob 存入 map，所以会直接找到 Alice 的位置，发现 key 是 Alice 不是 Bob，接着在 Alice 位置后面查找，直到找到 key Bob 或者找到空。

再哈希法(Re-Hashing)：

  • 设计多个哈希函数，假如 Alice 与 Bob 计算哈希结果相同，那么用另外一个哈希函数来计算 Bob 的哈希值，这种方式来解决哈希冲突。
  • 链地址法(Separate Chaining)：
  • 此方法将同一个哈希结果对应的位置想象成一个桶，如果多个 key 对应哈希结果相同，那么都放到同一个桶中，并且桶中元素使用链表结构存储。
  • 写入时：Alice 于 Bob 哈希结果相同，此时 map 已经有 Alice，再写入 Bob 时，发现对应哈希结果位置已经存在了 Alice，此时在当前桶中的 Alice 后链接一个 Bob，此时哈希结果对应的桶就存在了两个元素 Alice 与 Bob。
  • 读取时：读取 Bob key 时，发现对应哈希结果的桶中第一个元素是 Alice，此时在桶中按链表顺序挨个查找，直到 key 相同或者空。
  • 装载因子：此方案存在一个问题，当一个桶中元素过多时，其复杂度将增加，极端情况下就变成了链表。所以我们会限制在一个桶中元素的个数。这样在一个桶中元素过多时，需要生成新的桶。
  • 装载因子 = 元素总量 / 桶总个数

在 Go 语言中，map 使用的是链地址法。

2 Go 中 map分析

2.1 map 数据结构

map 的源码位于 src/runtime/map.go 文件中，结构如下：

 
 
 
    
  
  
  
  1. type hmap struct { 
    2. 
  
  
  
  2.     count     int // 当前 map 中元素数量 
    3. 
  
  
  
  3.     flags     uint8 
    4. 
  
  
  
  4.     B         uint8  // 当前 buckets 数量，2^B 等于 buckets 个数 
    5. 
  
  
  
  5.     noverflow uint16 // approximate number of overflow buckets; see incrnoverflow for details 
    6. 
  
  
  
  6.     hash0     uint32 // 哈希种子 
    7. 
  
  
  
  7.  
    8. 
  
  
  
  8.     buckets    unsafe.Pointer // buckets 数组指针 
    9. 
  
  
  
  9.     oldbuckets unsafe.Pointer // 扩容时保存之前 buckets 数据。 
    10. 
  
  
  
  10.     nevacuate  uintptr        // progress counter for evacuation (buckets less than this have been evacuated) 
    11. 
  
  
  
  11.  
    12. 
  
  
  
  12.     extra *mapextra // optional fields 
    13. 
  
  
  
  13. } 
    14. 
  
  
  
  14.  
    15. 
  
  
  
  15. // 每一个 bucket 的结构，即 hmap 中 buckets 指向的数据。 
    16. 
  
  
  
  16. type bmap struct { 
    17. 
  
  
  
  17.     tophash [bucketCnt]uint8 
    18. 
  
  
  
  18. } 
    19. 
  
  
  
  19.  
    20. 
  
  
  
  20. // 编译期间重构此结构 
    21. 
  
  
  
  21. type bmap struct { 
    22. 
  
  
  
  22.     topbits  [8]uint8 
    23. 
  
  
  
  23.     keys     [8]keytype 
    24. 
  
  
  
  24.     values   [8]valuetype 
    25. 
  
  
  
  25.     pad      uintptr 
    26. 
  
  
  
  26.     overflow uintptr 
    27. 
  
  
  
  27. } 
    28.

关于 hmap 的结构这里已经将很多重要的字段列出来了，其中最重要的就是 buckets 这一部分，根据上面我们说过的链地址法可知，对同一类 key (哈希结果相同)放入相同的桶中。此时每一个桶还有另外一个字段 overflow，也就是当前桶装不下就会再创建新的桶。这就是 Go 中 map 的主要实现方法，更详细的部分我们接下来一点一点聊。

2.2 源码

map 的源码位于 src/runtime/map.go 文件中。关于 map 的操作的具体实现在这里都可以找到：

  • 创建 map：func makemap(t *maptype, hint int, h *hmap) *hmap
  • 访问某个 key：
  • 返回结果只包括 value：func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer
  • 返回结果包括 bool 结果：func mapaccess2(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, bool)
  • 存入 key：func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer
  • 删除 key：func mapdelete(t *maptype, h *hmap, key unsafe.Pointer)

本篇文章不会带大家将源码通读一遍，但是会将其实现过程以图或者文字形式分析出来，但是建议大家有时间可以根据本篇文章的内容再去自己读一遍源码，如果我这里将所有源码都解释一遍，估计朋友们很快就又忘记了，还不如记住实现流程。所以本文更多的是讲 map 每个操作的过程图，以及其中的部分要点，而不是将源码一行一行的解释出来。

3. 图解 map

3.1 创建map

我们已经知道 map 的数据结构，其实 map 的初始化也无非就是填充各个字段而已：

  • 第一个就是 hash0 字段，此处会随机给一个种子，用在哈希函数计算时使用。关于哈希函数在运行时，Go 会检测 cpu 是否支持 aes，支持则使用 aes hash，否则使用 memhash。位于路径：src/runtime/alg.go 下的 alginit() 函数。
  • 根据参数 hint计算需要的桶数。
  • 根据桶的数量创建一个连续的空间来存储桶的数据。

大体上就是这么一个过程，关于源码中的一些检查项这里就不多废话了，并且源码注释也写的很清楚了。

下面这个图就是一个 map 的主要相关存储结构：

map 主要结构

3.2 定位 key

一个 map 初始化后基本的结构我们已经知道了，接下来就是我们在这个结构中如何添加一个 key 对应的 value。

我们再看一遍每一个桶的结构：

 
 
 
    
  
  
  
  1. type bmap struct { 
    2. 
  
  
  
  2.     topbits  [8]uint8 
    3. 
  
  
  
  3.     keys     [8]keytype 
    4. 
  
  
  
  4.     values   [8]valuetype 
    5. 
  
  
  
  5.     pad      uintptr 
    6. 
  
  
  
  6.     overflow uintptr 
    7. 
  
  
  
  7. } 
    8.

这里的 keys 与 values 字段就是存储 key 和 value 的真正内存的地方，我们可以看到这里每个都是长度为8的数组，也就是说一个桶内存了两个数组，一个存的是 key 列表，另一个是 value 列表，并且每个数据的大小都是8。那么当有第9个元素入桶时，我们就需要创建新的桶了，也就是 overflow 字段指向一个新的 bucket(bmap 结构)。

还有一个字段就是 topbits，也是一个长度为8的数组，其实看到这里我们应该想到，这三个数组长度都相同应该有对应关系了，也就是说 topbits 数组中第一个元素是一个8位大小，我们称之为 高8位，这是我们再回想一下哈希函数，我们的哈希函数的结果取高8位，然后存入 topbits 数组，然后其在数组的索引我们称之为i，那么我们就可以在 keys 和 values 数组的第i个位置存储数据了。

上面是在已知一个桶中添加或者修改元素，那么我们该如何查找这个桶呢?

我们知道在 hmap 中有 buckets 字段，其指向 []bmap 数组。那么我们就需要通过 key 找到对应的 bmap 在 []bmap 中的位置。关于此处的计算大家感兴趣的可以看一下源码，这里就不详细说每一个运算符都是怎么运算的，只说一下大致的流程：hmap 中有一个 B 字段，根据字段 B 的值，以及 key 的 hash 值，计算出目标桶在 []bmap 中的位置(其实就是取了 key 的哈希的后几位作为数组的下标即可)。

现在我们根据一个 key 可以在 hmap 中的 buckets 字段找到对应的 bmap 对象，同时在 bmap 中根据 key 哈希的高八位找到其在 keys 与 values 数组中的位置。这里我们还没有说如果有 overflow 的情况。其实不说想必大家也能猜到了，在我们定位到一个 bmap 时，是不知道其一共有多少个溢出桶的：假设我们有桶 A，A 的 overflow 字段指向桶 B，B 的 overflow 指向桶 C，假设我们此时根据 key 的哈希找到了桶 A，然后 for 循环遍历桶中的 topbits 数组，如果某个高8位的哈希与我们想找的 key 的哈希的高8位相同，就去对应位置的 keys 数组查找对应的 key1，假如 key1 与我们的目标 key 相等，那么直接返回其对应 values 数组中的 value 即可。如果key1 与我们的目标 key 不相等，接着变量桶中其他元素。假设桶中所有元素遍历后没有找到相同的 key，那么此时就要到 A 桶的溢出桶 B 再去遍历，如果 B 中依然找不到再去桶 C 中查找。此时大家可以思考一下如果是你，你会如何实现这部分代码呢?你实现的和 Go 的源码是否一样呢?

当我们知道了上面定位 key 的过程，对于 key 的增删改查过程也就不多说了，因为核心的我们已经掌握了，现在大家可以去看一下源码了，这时大家看源码必定事半功倍。

分享标题：Go语言map解析之key的定位核心流程
标题来源：http://www.mswzjz.com/qtweb/news2/173852.html

网站建设、网络推广公司-创新互联，是专注品牌与效果的网站制作，网络营销seo公司；服务项目有等

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 创新互联

猜你还喜欢下面的内容

网页设计公司知识

同城分类信息

网络整合营销　　 　南充网站建设　　 　长城雪茄　　 　广汉锦华橡塑　　 　成都网站设计　　 　成都模板网站　　 　温江网站建设　　 　成都小程序开发　　 　广东帝美豪门窗　　 　品牌网站定制　　 　成都钢筋机械设备　　 　seo网络营销推广　　 　服务器租用　　 　成都外贸网站建设公司　　 　平山县网站建设　　 　LOGO设计　　 　成都做网站　　 　腾讯云香港空间　　 　成都网站建设　　 　边坡防护网厂家