13518219792
map 是Go语言中基础的数据结构，在日常的使用中经常被用到。但是它底层是如何实现的呢？
创新互联公司是一家专业提供文县企业网站建设,专注与成都网站设计、成都做网站、H5网站设计、小程序制作等业务。10年已为文县众多企业、政府机构等服务。创新互联专业网站制作公司优惠进行中。
总体来说golang的map是hashmap，是使用数组+链表的形式实现的，使用拉链法消除hash冲突。
golang的map由两种重要的结构，hmap和bmap(下文中都有解释)，主要就是hmap中包含一个指向bmap数组的指针，key经过hash函数之后得到一个数，这个数低位用于选择bmap(当作bmap数组指针的下表)，高位用于放在bmap的[8]uint8数组中，用于快速试错。然后一个bmap可以指向下一个bmap(拉链)。
Golang中map的底层实现是一个散列表，因此实现map的过程实际上就是实现散表的过程。在这个散列表中，主要出现的结构体有两个，一个叫 hmap (a header for a go map)，一个叫 bmap (a bucket for a Go map，通常叫其bucket)。这两种结构的样子分别如下所示：
hmap :
图中有很多字段，但是便于理解map的架构，你只需要关心的只有一个，就是标红的字段： buckets数组 。Golang的map中用于存储的结构是bucket数组。而bucket(即bmap)的结构是怎样的呢？
bucket ：
相比于hmap，bucket的结构显得简单一些，标红的字段依然是“核心”，我们使用的map中的key和value就存储在这里。“高位哈希值”数组记录的是当前bucket中key相关的“索引”，稍后会详细叙述。还有一个字段是一个指向扩容后的bucket的指针，使得bucket会形成一个链表结构。例如下图：
由此看出hmap和bucket的关系是这样的：
而bucket又是一个链表，所以，整体的结构应该是这样的：
哈希表的特点是会有一个哈希函数，对你传来的key进行哈希运算，得到唯一的值，一般情况下都是一个数值。Golang的map中也有这么一个哈希函数，也会算出唯一的值，对于这个值的使用，Golang也是很有意思。
Golang把求得的值按照用途一分为二：高位和低位。
如图所示，蓝色为高位，红色为低位。 然后低位用于寻找当前key属于hmap中的哪个bucket，而高位用于寻找bucket中的哪个key。上文中提到：bucket中有个属性字段是“高位哈希值”数组，这里存的就是蓝色的高位值，用来声明当前bucket中有哪些“key”，便于搜索查找。 需要特别指出的一点是：我们map中的key/value值都是存到同一个数组中的。数组中的顺序是这样的:
并不是key0/value0/key1/value1的形式，这样做的好处是：在key和value的长度不同的时候，可 以消除padding(内存对齐)带来的空间浪费 。
现在，我们可以得到Go语言map的整个的结构图了：(hash结果的低位用于选择把KV放在bmap数组中的哪一个bmap中，高位用于key的快速预览，用于快速试错)
map的扩容
当以上的哈希表增长的时候，Go语言会将bucket数组的数量扩充一倍，产生一个新的bucket数组，并将旧数组的数据迁移至新数组。
加载因子
判断扩充的条件，就是哈希表中的加载因子(即loadFactor)。
加载因子是一个阈值，一般表示为：散列包含的元素数 除以 位置总数。是一种“产生冲突机会”和“空间使用”的平衡与折中：加载因子越小，说明空间空置率高，空间使用率小，但是加载因子越大，说明空间利用率上去了，但是“产生冲突机会”高了。
每种哈希表的都会有一个加载因子，数值超过加载因子就会为哈希表扩容。
Golang的map的加载因子的公式是：map长度 / 2^B(这是代表bmap数组的长度，B是取的低位的位数)阈值是6.5。其中B可以理解为已扩容的次数。
当Go的map长度增长到大于加载因子所需的map长度时，Go语言就会将产生一个新的bucket数组，然后把旧的bucket数组移到一个属性字段oldbucket中。注意：并不是立刻把旧的数组中的元素转义到新的bucket当中，而是，只有当访问到具体的某个bucket的时候，会把bucket中的数据转移到新的bucket中。
如下图所示：当扩容的时候，Go的map结构体中，会保存旧的数据，和新生成的数组
上面部分代表旧的有数据的bucket，下面部分代表新生成的新的bucket。蓝色代表存有数据的bucket，橘黄色代表空的bucket。
扩容时map并不会立即把新数据做迁移，而是当访问原来旧bucket的数据的时候，才把旧数据做迁移，如下图：
注意：这里并不会直接删除旧的bucket，而是把原来的引用去掉，利用GC清除内存。
map中数据的删除
如果理解了map的整体结构，那么查找、更新、删除的基本步骤应该都很清楚了。这里不再赘述。
值得注意的是，找到了map中的数据之后，针对key和value分别做如下操作：
1
2
3
4
1、如果``key``是一个指针类型的，则直接将其置为空，等待GC清除；
2、如果是值类型的，则清除相关内存。
3、同理，对``value``做相同的操作。
4、最后把key对应的高位值对应的数组index置为空。
在开始之前，希望你计算一下 Part1 共占用的大小是多少呢？
输出结果：
这么一算， Part1 这一个结构体的占用内存大小为 1+4+1+8+1 = 15 个字节。相信有的小伙伴是这么算的，看上去也没什么毛病
真实情况是怎么样的呢？我们实际调用看看，如下：
输出结果：
最终输出为占用 32 个字节。这与前面所预期的结果完全不一样。这充分地说明了先前的计算方式是错误的。为什么呢？
在这里要提到 “内存对齐” 这一概念，才能够用正确的姿势去计算，接下来我们详细的讲讲它是什么
有的小伙伴可能会认为内存读取，就是一个简单的字节数组摆放
上图表示一个坑一个萝卜的内存读取方式。但实际上 CPU 并不会以一个一个字节去读取和写入内存。相反 CPU 读取内存是 一块一块读取 的，块的大小可以为 2、4、6、8、16 字节等大小。块大小我们称其为 内存访问粒度 。如下图：
在样例中，假设访问粒度为 4。 CPU 是以每 4 个字节大小的访问粒度去读取和写入内存的。这才是正确的姿势
另外作为一个工程师，你也很有必要学习这块知识点哦 :)
在上图中，假设从 Index 1 开始读取，将会出现很崩溃的问题。因为它的内存访问边界是不对齐的。因此 CPU 会做一些额外的处理工作。如下：
从上述流程可得出，不做 “内存对齐” 是一件有点 "麻烦" 的事。因为它会增加许多耗费时间的动作
而假设做了内存对齐，从 Index 0 开始读取 4 个字节，只需要读取一次，也不需要额外的运算。这显然高效很多，是标准的 空间换时间 做法
在不同平台上的编译器都有自己默认的 “对齐系数”，可通过预编译命令 #pragma pack(n) 进行变更，n 就是代指 “对齐系数”。一般来讲，我们常用的平台的系数如下：
另外要注意，不同硬件平台占用的大小和对齐值都可能是不一样的。因此本文的值不是唯一的，调试的时候需按本机的实际情况考虑
输出结果：
在 Go 中可以调用 unsafe.Alignof 来返回相应类型的对齐系数。通过观察输出结果，可得知基本都是 2^n ，最大也不会超过 8。这是因为我手提（64 位）编译器默认对齐系数是 8，因此最大值不会超过这个数
在上小节中，提到了结构体中的成员变量要做字节对齐。那么想当然身为最终结果的结构体，也是需要做字节对齐的
接下来我们一起分析一下，“它” 到底经历了些什么，影响了 “预期” 结果
在每个成员变量进行对齐后，根据规则 2，整个结构体本身也要进行字节对齐，因为可发现它可能并不是 2^n ，不是偶数倍。显然不符合对齐的规则
根据规则 2，可得出对齐值为 8。现在的偏移量为 25，不是 8 的整倍数。因此确定偏移量为 32。对结构体进行对齐
Part1 内存布局：axxx|bbbb|cxxx|xxxx|dddd|dddd|exxx|xxxx
通过本节的分析，可得知先前的 “推算” 为什么错误？
是因为实际内存管理并非 “一个萝卜一个坑” 的思想。而是一块一块。通过空间换时间（效率）的思想来完成这块读取、写入。另外也需要兼顾不同平台的内存操作情况
在上一小节，可得知根据成员变量的类型不同，其结构体的内存会产生对齐等动作。那假设字段顺序不同，会不会有什么变化呢？我们一起来试试吧 :-)
输出结果：
通过结果可以惊喜的发现，只是 “简单” 对成员变量的字段顺序进行改变，就改变了结构体占用大小
接下来我们一起剖析一下 Part2 ，看看它的内部到底和上一位之间有什么区别，才导致了这样的结果？
符合规则 2，不需要额外对齐
Part2 内存布局：ecax|bbbb|dddd|dddd
通过对比 Part1 和 Part2 的内存布局，你会发现两者有很大的不同。如下：
仔细一看， Part1 存在许多 Padding。显然它占据了不少空间，那么 Padding 是怎么出现的呢？
通过本文的介绍，可得知是由于不同类型导致需要进行字节对齐，以此保证内存的访问边界
那么也不难理解，为什么 调整结构体内成员变量的字段顺序 就能达到缩小结构体占用大小的疑问了，是因为巧妙地减少了 Padding 的存在。让它们更 “紧凑” 了。这一点对于加深 Go 的内存布局印象和大对象的优化非常有帮
Go语言中没有“类”的概念，也不支持“类”的继承等面向对象的概念。Go语言中通过结构体的内嵌再配合接口比面向对象具有更高的扩展性和灵活性。
自定义类型
在Go语言中有一些基本的数据类型，如string、整型、浮点型、布尔等数据类型， Go语言中可以使用type关键字来定义自定义类型。
自定义类型是定义了一个全新的类型。我们可以基于内置的基本类型定义，也可以通过struct定义。例如：
通过Type关键字的定义，MyInt就是一种新的类型，它具有int的特性。
类型别名
类型别名是Go1.9版本添加的新功能。
类型别名规定：TypeAlias只是Type的别名，本质上TypeAlias与Type是同一个类型。就像一个孩子小时候有小名、乳名，上学后用学名，英语老师又会给他起英文名，但这些名字都指的是他本人。
type TypeAlias = Type
我们之前见过的rune和byte就是类型别名，他们的定义如下：
类型定义和类型别名的区别
类型别名与类型定义表面上看只有一个等号的差异，我们通过下面的这段代码来理解它们之间的区别。
结果显示a的类型是main.NewInt，表示main包下定义的NewInt类型。b的类型是int。MyInt类型只会在代码中存在，编译完成时并不会有MyInt类型。
Go语言中的基础数据类型可以表示一些事物的基本属性，但是当我们想表达一个事物的全部或部分属性时，这时候再用单一的基本数据类型明显就无法满足需求了，Go语言提供了一种自定义数据类型，可以封装多个基本数据类型，这种数据类型叫结构体，英文名称struct。 也就是我们可以通过struct来定义自己的类型了。
Go语言中通过struct来实现面向对象。
结构体的定义
使用type和struct关键字来定义结构体，具体代码格式如下：
其中：
举个例子，我们定义一个Person（人）结构体，代码如下：
同样类型的字段也可以写在一行，
这样我们就拥有了一个person的自定义类型，它有name、city、age三个字段，分别表示姓名、城市和年龄。这样我们使用这个person结构体就能够很方便的在程序中表示和存储人信息了。
语言内置的基础数据类型是用来描述一个值的，而结构体是用来描述一组值的。比如一个人有名字、年龄和居住城市等，本质上是一种聚合型的数据类型
结构体实例化
只有当结构体实例化时，才会真正地分配内存。也就是必须实例化后才能使用结构体的字段。
基本实例化
举个例子：
我们通过.来访问结构体的字段（成员变量）,例如p1.name和p1.age等。
匿名结构体
在定义一些临时数据结构等场景下还可以使用匿名结构体。
创建指针类型结构体
我们还可以通过使用new关键字对结构体进行实例化，得到的是结构体的地址。 格式如下：
从打印的结果中我们可以看出p2是一个结构体指针。
需要注意的是在Go语言中支持对结构体指针直接使用.来访问结构体的成员。
取结构体的地址实例化
使用对结构体进行取地址操作相当于对该结构体类型进行了一次new实例化操作。
p3.name = "七米"其实在底层是(*p3).name = "七米"，这是Go语言帮我们实现的语法糖。
结构体初始化
没有初始化的结构体，其成员变量都是对应其类型的零值。
使用键值对初始化
使用键值对对结构体进行初始化时，键对应结构体的字段，值对应该字段的初始值。
也可以对结构体指针进行键值对初始化，例如：
当某些字段没有初始值的时候，该字段可以不写。此时，没有指定初始值的字段的值就是该字段类型的零值。
使用值的列表初始化
初始化结构体的时候可以简写，也就是初始化的时候不写键，直接写值：
使用这种格式初始化时，需要注意：
结构体内存布局
结构体占用一块连续的内存。
输出：
【进阶知识点】关于Go语言中的内存对齐推荐阅读:在 Go 中恰到好处的内存对齐
面试题
请问下面代码的执行结果是什么？
构造函数
Go语言的结构体没有构造函数，我们可以自己实现。 例如，下方的代码就实现了一个person的构造函数。 因为struct是值类型，如果结构体比较复杂的话，值拷贝性能开销会比较大，所以该构造函数返回的是结构体指针类型。
调用构造函数
方法和接收者
Go语言中的方法（Method）是一种作用于特定类型变量的函数。这种特定类型变量叫做接收者（Receiver）。接收者的概念就类似于其他语言中的this或者 self。
方法的定义格式如下：
其中，
举个例子：
方法与函数的区别是，函数不属于任何类型，方法属于特定的类型。
指针类型的接收者
指针类型的接收者由一个结构体的指针组成，由于指针的特性，调用方法时修改接收者指针的任意成员变量，在方法结束后，修改都是有效的。这种方式就十分接近于其他语言中面向对象中的this或者self。 例如我们为Person添加一个SetAge方法，来修改实例变量的年龄。
调用该方法：
值类型的接收者
当方法作用于值类型接收者时，Go语言会在代码运行时将接收者的值复制一份。在值类型接收者的方法中可以获取接收者的成员值，但修改操作只是针对副本，无法修改接收者变量本身。
什么时候应该使用指针类型接收者
任意类型添加方法
在Go语言中，接收者的类型可以是任何类型，不仅仅是结构体，任何类型都可以拥有方法。 举个例子，我们基于内置的int类型使用type关键字可以定义新的自定义类型，然后为我们的自定义类型添加方法。
注意事项： 非本地类型不能定义方法，也就是说我们不能给别的包的类型定义方法。
结构体的匿名字段
匿名字段默认采用类型名作为字段名，结构体要求字段名称必须唯一，因此一个结构体中同种类型的匿名字段只能有一个。
嵌套结构体
一个结构体中可以嵌套包含另一个结构体或结构体指针。
嵌套匿名结构体
当访问结构体成员时会先在结构体中查找该字段，找不到再去匿名结构体中查找。
嵌套结构体的字段名冲突
嵌套结构体内部可能存在相同的字段名。这个时候为了避免歧义需要指定具体的内嵌结构体的字段。
结构体的“继承”
Go语言中使用结构体也可以实现其他编程语言中面向对象的继承。
结构体字段的可见性
结构体中字段大写开头表示可公开访问，小写表示私有（仅在定义当前结构体的包中可访问）。
结构体与JSON序列化
JSON(JavaScript Object Notation) 是一种轻量级的数据交换格式。易于人阅读和编写。同时也易于机器解析和生成。JSON键值对是用来保存JS对象的一种方式，键/值对组合中的键名写在前面并用双引号""包裹，使用冒号:分隔，然后紧接着值；多个键值之间使用英文,分隔。
结构体标签（Tag）
Tag是结构体的元信息，可以在运行的时候通过反射的机制读取出来。 Tag在结构体字段的后方定义，由一对反引号包裹起来，具体的格式如下：
`key1:"value1" key2:"value2"`
结构体标签由一个或多个键值对组成。键与值使用冒号分隔，值用双引号括起来。键值对之间使用一个空格分隔。 注意事项： 为结构体编写Tag时，必须严格遵守键值对的规则。结构体标签的解析代码的容错能力很差，一旦格式写错，编译和运行时都不会提示任何错误，通过反射也无法正确取值。例如不要在key和value之间添加空格。
例如我们为Student结构体的每个字段定义json序列化时使用的Tag：
1.平台原因(移植原因)： 不是所有的硬件平台都能访问任意地址上的任意数据的；某些硬件平台只能
在某些地址处取某些特定类型的数据，否则抛出硬件异常。
2.性能原因： 数据结构应该尽可能地在自然边界上对齐。原因在于，为了访问未对齐的内存，处理器需要作两次内存访问；而对齐的内存访问仅需要一次访问。(如果是对齐的，那么CPU不需要跨越两个操作字，不是对齐的则需要访问两个操作字才能拼接出需要的内存地址)
指针的大小一般是一个机器字的大小
通过Go语言的structlayout工具，可以得出下图
这些类型在之前的 slice 、 map 、 interface 已经介绍过了，也特意强调过，makehmap函数返回的是一个指针，因此map的对齐为一个机器字.
回头看看 sync.pool的防止copy的空结构体字段,也是放在第一位，破案了。
计算机结构可能会要求内存地址 进行对齐;也就是说，一个变量的地址是一个因子的倍数，也就是该变量的类型是对齐值。
函数Alignof接受一个表示任何类型变量的表达式作为参数，并以字节为单位返回变量(类型)的对齐值。对于变量x：
这是因为int64在bool之后未对齐。
它是32位对齐的，但不是64位对齐的，因为我们使用的是32位系统，因此实际上只是两个32位值并排在一起。
● 内存对齐是为了cpu更高效访问内存中数据
● 结构体对齐依赖类型的大小保证和对齐保证
● 地址对齐保证是：如果类型 t 的对齐保证是 n，那么类型 t 的每个值的地址在运行时必须是 n 的倍数。
● struct内字段如果填充过多，可以尝试重排，使字段排列更紧密，减少内存浪费
● 零大小字段要避免作为struct最后一个字段，会有内存浪费
● 32位系统上对64位字的原子访问要保证其是8bytes对齐的；当然如果不必要的 话，还是用加锁（mutex）的方式更清晰简单
图解go-内存对齐
doc-pdf
有时候我们需要在完全可控的范围内复用channel，但是关闭了的channel原生语法并没有提供方法打开，所以利用指针再次打开。
channel的结构体在 chan.go 中：
Channel是否关闭取决于 hchan.closed ，0是打开，1是关闭。
方法：让指针指向 hchan.closed 直接修改它的值。
closedOffset为什么是28呢？这个涉及到struct对齐问题， Go内存优化（一）— struct对齐
在上面主要用了指针定位closed值，直接修改标志位。为了保证设置closed值的安全性所以在给它设置值的时候使用runtime.lock上锁。
关于 go:linkname 可以自行百度，在目录下创建一个 *.s 文件可以躲过编译时error： missing function body 。
