goland map底层原理

map 是Go语言中基础的数据结构，在日常的使用中经常被用到。但是它底层是如何实现的呢？

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

总体来说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置为空。

底层逻辑这本书怎么样

底层逻辑这本书是十分有用的，可以套用在各个领域。

书的名字是《底层逻辑》，看着标题，着实有力，那作者刘润是如何定义底层逻辑的呢？“只有不同之中的相同之处，变化背后不变的东西，才是底层逻辑。只有底层逻辑，才是有生命力的。”

底层逻辑看起来很有价值，任何事物都是基本规律的叠加，认清基本规律是大有益处的。就好比计算机技术，能够深挖基本功是未来能够做得好的关键。正所谓世界是不断变化的，变化是表象，而实质是不变的基本规律在不停的演绎。

本书分为了五个章节，分别是：是非对错、思考问题、个体进化，理解他人和社会协作五个方面，看着名字感觉是有些关联，但它们之间没有什么关系，内容是刘润在罗胖得到上开课的重新组织，并没有进行分解和提炼，对于读者而言，完全可以分开阅读。

底层逻辑相当于基本原理，它需要不断的升高问题的维度，将（同一或多个领域的）不同问题中的共性进行抽象和提炼，并将得到的结论带回到各个问题中去解释它们，这种V字型的思考模式是很重要的。

得到的结论不见的是一个让人惊叹的观点，所以有人用一个专有、惊奇且违反常理的结论来示图告诉你这是本质，这是底层逻辑，你就要小心了，因为以偏概全往往是现代公知们的常用手段，这点在本书中也或多或少存在。

观点思考

本书有许多有意思的观点，这些观点将会被笔者归纳到某个小的范围，然后在这个范围内进行探讨，可能是对观点的赞同，也有可能是批判。

底层逻辑方法论

书中提到：底层逻辑 + 环境变量 = 方法论。

这是刘润提到的一个公式，他想表达的是底层逻辑是不变的，而外部不同的场景才是变化的，只有两者的结合才能得到某个（场景）领域的核心要点，也就是方法论。

这个公式无疑是着重体现了底层逻辑的重要性，初一看有点感觉，是那么一回事，但仔细想，这个不一定对，

原因主要有两点：第一，公式简单的认为方法论就是底层逻辑在不同环境的投影，这点无疑是不承认学科或场景的多样性和特殊性；第二，这里的底层逻辑假设真实存在，那就要求它有哲学般的普适性，否则无法涵盖众多颂域。

底层逻辑是重要的，但它们是属于各自领域的，自然科学都无法将不同领域的所有问题归结到某一些底层逻辑。能看出某些不同领或中有相似逻辑，但不能说这相似逻辑是同一个，或者是在相同底层逻辑在不同领域中的投影，而是说现阶段没有发现它们的区别，也许它们属于公共领域（或父领域）中的逻辑。

多视角看问题

书中提到：一个人心中，应该有三种“对错观”：（1）法学家对错观；（2）经济学家对错观；（3）商人对错观。其中法学家讲究证据，谁的错谁承担，经济学家认为谁社会总成本低就是谁的错，而商人认为谁损失大就是谁的错。

作为一名程序员，时常会遇到故障，不论自己遇到的，还是看别人遇到的，常听到：这是遇到前人埋的雷了。这时候怎么处理呢？找前人？还是出问题的人自己负责？后来发现，基本都是出问题的人自己承担。这就是一种经济学家的处理方式，总成本最低。

三种对错观，提醒我们对于事情需要有多个视角去看，而这三种对错观是希望告诉我们，这不是为看似不合理的决定找台阶下，更多的是提醒自己视野开阔些，内心平和些。

事情都是人来做的，我这里想提出基于人和事的三个看法，这三个看法（或观点）是递进关系，它们是：

（1）人和人是不同的，人是分阶级的，处于各自阶级的人，只要本着客观且实事求是的思考，所做的行为都是可以理解的；

（2）不同阶级，会有各自的世界观，会有各自追求的生活和做事的理念，它们会有很大不同，阶级之间的坦诚对话在历史上看来，往往是暴力；

（3）客观事物存在于不同阶级共存的世界中，因此对于一件事物（或事情），它的发展和走向，是不同阶级角力的结果，而这个结果体现出了复杂性和矛盾性。

可以看到，我们在现实世界中看到的任何事情，比如：东航事故的无疾而终，美国MAGA冲击国会大厦等，看似荒谬或充满了无力感，但如果结合这三个看法以及多视角看问题，就会发现，这都很正常。

【golang详解】go语言GMP(GPM)原理和调度

Goroutine调度是一个很复杂的机制，下面尝试用简单的语言描述一下Goroutine调度机制，想要对其有更深入的了解可以去研读一下源码。

首先介绍一下GMP什么意思：

G ----------- goroutine: 即Go协程，每个go关键字都会创建一个协程。

M ---------- thread内核级线程，所有的G都要放在M上才能运行。

P ----------- processor处理器，调度G到M上，其维护了一个队列，存储了所有需要它来调度的G。

Goroutine 调度器P和 OS 调度器是通过 M 结合起来的，每个 M 都代表了 1 个内核线程，OS 调度器负责把内核线程分配到 CPU 的核上执行

模型图：

避免频繁的创建、销毁线程，而是对线程的复用。

1）work stealing机制

当本线程无可运行的G时，尝试从其他线程绑定的P偷取G，而不是销毁线程。

2）hand off机制

当本线程M0因为G0进行系统调用阻塞时，线程释放绑定的P，把P转移给其他空闲的线程执行。进而某个空闲的M1获取P，继续执行P队列中剩下的G。而M0由于陷入系统调用而进被阻塞，M1接替M0的工作，只要P不空闲，就可以保证充分利用CPU。M1的来源有可能是M的缓存池，也可能是新建的。当G0系统调用结束后，根据M0是否能获取到P，将会将G0做不同的处理：

如果有空闲的P，则获取一个P，继续执行G0。

如果没有空闲的P，则将G0放入全局队列，等待被其他的P调度。然后M0将进入缓存池睡眠。

如下图

GOMAXPROCS设置P的数量，最多有GOMAXPROCS个线程分布在多个CPU上同时运行

在Go中一个goroutine最多占用CPU 10ms，防止其他goroutine被饿死。

具体可以去看另一篇文章

【Golang详解】go语言调度机制 抢占式调度

当创建一个新的G之后优先加入本地队列，如果本地队列满了，会将本地队列的G移动到全局队列里面，当M执行work stealing从其他P偷不到G时，它可以从全局G队列获取G。

协程经历过程

我们创建一个协程 go func()经历过程如下图：

说明：

这里有两个存储G的队列，一个是局部调度器P的本地队列、一个是全局G队列。新创建的G会先保存在P的本地队列中，如果P的本地队列已经满了就会保存在全局的队列中；处理器本地队列是一个使用数组构成的环形链表，它最多可以存储 256 个待执行任务。

G只能运行在M中，一个M必须持有一个P，M与P是1：1的关系。M会从P的本地队列弹出一个可执行状态的G来执行，如果P的本地队列为空，就会想其他的MP组合偷取一个可执行的G来执行；

一个M调度G执行的过程是一个循环机制；会一直从本地队列或全局队列中获取G

上面说到P的个数默认等于CPU核数，每个M必须持有一个P才可以执行G，一般情况下M的个数会略大于P的个数，这多出来的M将会在G产生系统调用时发挥作用。类似线程池，Go也提供一个M的池子，需要时从池子中获取，用完放回池子，不够用时就再创建一个。

work-stealing调度算法：当M执行完了当前P的本地队列队列里的所有G后，P也不会就这么在那躺尸啥都不干，它会先尝试从全局队列队列寻找G来执行，如果全局队列为空，它会随机挑选另外一个P，从它的队列里中拿走一半的G到自己的队列中执行。

如果一切正常，调度器会以上述的那种方式顺畅地运行，但这个世界没这么美好，总有意外发生，以下分析goroutine在两种例外情况下的行为。

Go runtime会在下面的goroutine被阻塞的情况下运行另外一个goroutine：

用户态阻塞/唤醒

当goroutine因为channel操作或者network I/O而阻塞时（实际上golang已经用netpoller实现了goroutine网络I/O阻塞不会导致M被阻塞，仅阻塞G，这里仅仅是举个栗子），对应的G会被放置到某个wait队列(如channel的waitq)，该G的状态由_Gruning变为_Gwaitting，而M会跳过该G尝试获取并执行下一个G，如果此时没有可运行的G供M运行，那么M将解绑P，并进入sleep状态；当阻塞的G被另一端的G2唤醒时（比如channel的可读/写通知），G被标记为，尝试加入G2所在P的runnext（runnext是线程下一个需要执行的 Goroutine。）， 然后再是P的本地队列和全局队列。

系统调用阻塞

当M执行某一个G时候如果发生了阻塞操作，M会阻塞，如果当前有一些G在执行，调度器会把这个线程M从P中摘除，然后再创建一个新的操作系统的线程(如果有空闲的线程可用就复用空闲线程)来服务于这个P。当M系统调用结束时候，这个G会尝试获取一个空闲的P执行，并放入到这个P的本地队列。如果获取不到P，那么这个线程M变成休眠状态， 加入到空闲线程中，然后这个G会被放入全局队列中。

队列轮转

可见每个P维护着一个包含G的队列，不考虑G进入系统调用或IO操作的情况下，P周期性的将G调度到M中执行，执行一小段时间，将上下文保存下来，然后将G放到队列尾部，然后从队列中重新取出一个G进行调度。

除了每个P维护的G队列以外，还有一个全局的队列，每个P会周期性地查看全局队列中是否有G待运行并将其调度到M中执行，全局队列中G的来源，主要有从系统调用中恢复的G。之所以P会周期性地查看全局队列，也是为了防止全局队列中的G被饿死。

除了每个P维护的G队列以外，还有一个全局的队列，每个P会周期性地查看全局队列中是否有G待运行并将其调度到M中执行，全局队列中G的来源，主要有从系统调用中恢复的G。之所以P会周期性地查看全局队列，也是为了防止全局队列中的G被饿死。

M0

M0是启动程序后的编号为0的主线程，这个M对应的实例会在全局变量rutime.m0中，不需要在heap上分配，M0负责执行初始化操作和启动第一个G，在之后M0就和其他的M一样了

G0

G0是每次启动一个M都会第一个创建的goroutine，G0仅用于负责调度G，G0不指向任何可执行的函数，每个M都会有一个自己的G0，在调度或系统调用时会使用G0的栈空间，全局变量的G0是M0的G0

一个G由于调度被中断，此后如何恢复？

中断的时候将寄存器里的栈信息，保存到自己的G对象里面。当再次轮到自己执行时，将自己保存的栈信息复制到寄存器里面，这样就接着上次之后运行了。

我这里只是根据自己的理解进行了简单的介绍，想要详细了解有关GMP的底层原理可以去看Go调度器 G-P-M 模型的设计者的文档或直接看源码

参考： ()

()

《Go语言实战》epub下载在线阅读，求百度网盘云资源

《Go语言实战》（威廉·肯尼迪 (William Kennedy)）电子书网盘下载免费在线阅读

链接：

提取码：1234

书名：Go语言实战

作者：威廉·肯尼迪 (William Kennedy)

译者：李兆海

豆瓣评分：7.7

出版社：人民邮电出版社

出版年份：2017-3-1

页数：224

内容简介：

Go语言结合了底层系统语言的能力以及现代语言的高级特性，旨在降低构建简单、可靠、高效软件的门槛。本书向读者提供一个专注、全面且符合语言习惯的视角。Go语言实战同时关注语言的规范和实现，涉及的内容包括语法、类型系统、并发、管道、测试，以及其他一些主题。

作者简介：

William Kennedy，是一位熟练的软件开发者，也是博客GoingGo.Net的作者。

Brian Ketelsen和Erik St. Martin是全球Go语言大会GopherCon的组织者，也是Go语言框架Skynet的联合作者。

李兆海，多年专注于后端分布式网络服务开发，曾使用过多个流行后端技术和相关架构实践，是Go语言和Docker的早期使用者和推广者，《第1本Docker书》的译者。作为项目技术负责人，成功开发了百万用户级直播系统。