Go源码版本1.13.8

前言

是的，我也是一个PHPer，对于我们PHPer转Gopher的银 ，一定有个困扰：Go语言里每次遍历Map输出元素的顺序并不一致，但是在PHP里却是稳定的。今天我们就来看看这个现象的原因。本篇文章主要从如下节点展开：

  • Go的Map遍历结果“无序”
    • 遍历Map的索引的起点是随机的
  • Go的Map本质上是“无序的”
    • 无序写入
      • 正常写入(非哈希冲突写入)
      • 哈希冲突写入
    • 扩容
      • 成倍扩容迫使元素顺序变化
      • 等量扩容

Go的Map遍历结果“无序”

现象：Go语言里每次遍历Map输出元素的顺序并不一致，但是在PHP里却是稳定的。

关于这个现象我就不过多赘述了，同时我相信大家应该都网上搜过相关的文章，这些文章大多都说明了原因：For ... Range ... 遍历Map的索引的起点是随机的，没错，就是下面这段代码。

但是呢，有没有再推测过Go的作者们这么做背后的真正原因是什么？个人觉着因为：

Go的Map本质上是“无序的”

Go的Map本质上是“无序的”，为什么这么说？

“无序”写入

1. 正常写入(非哈希冲突写入)：是hash到某一个bucket上，而不是按buckets顺序写入。

虽然buckets是一块连续的内存，但是新写入的键值可能写到这个bucket：


也可能写到这个bucket：


2. 哈希冲突写入：如果存在hash冲突，会写到同一个bucket上。

可能写到这个位置：


极限情况，也可能写到这个位置：


更有可能写到溢出桶去：



所以，写数据时，并没有单独维护键值对的顺序。而PHP(version 5)语言通过一个全局链表维护了Map里元素的顺序。

扩容

Go的Map的扩容有两种：

  • 成倍扩容
  • 等量扩容

1. 成倍扩容迫使元素顺序变化

为了简化理解我们对「成倍扩容」的理解，我们假设如下条件：

mapmapbucketbmap结构

同时根据如上的假设，我们得到此map对应的结构图示如下：

什么时候触发成倍扩容？
  • map写操作时
  • (元素数量/bucket数量) > 6.5时

通过下面的代码分析可知：

14:14

成倍扩容的过程如下：

bucketsoldbucketsbucketsbucketsbucketbmapbucketbmapbucketbmap

过程如下图所示(标红部分为本次扩容的bucket)：

15:15


同时，通过上面的分析我们可以得到：成倍扩容迫使元素顺序变化。

2. 等量扩容

什么时候触发等量扩容？

答案见下面的代码：

等量扩容的目的？

同样，为了简化理解我们对「等量扩容」的理解，我们假设如下条件：

mapmapbucketbmap结构bucketbucketsbmapbucketbucketsbmapbmapbmapbmapbmap

同时根据如上的假设，我们得到此map对应的结构图示如下：

为了说明「等量扩容」的作用，我们继续假设：

8:820:2030:30

此时，得到此map对应的结构图示如下：

36:36
36:36

从上图可以看出：

bmapbmapbmap

同时，通过上面的分析我们可以得到：等量扩容并没有改变元素顺序。

结语

通过上文的分析，我们可知Go的Map的特性：

  • 无序写入
  • 成倍扩容迫使元素顺序变化

所以可以说「Go的Map是无序的」。

其次，通过本文我们：

  • 再次回顾了Go的Map遍历结果“无序”的原因
  • 了解了Map的写入过程
  • 了解了Map的「成倍扩容」和「等量扩容」的设计与目的