1. 部署简单
创新互联总部坐落于成都市区,致力网站建设服务有成都做网站、网站设计、外贸营销网站建设、网络营销策划、网页设计、网站维护、公众号搭建、微信小程序、软件开发等为企业提供一整套的信息化建设解决方案。创造真正意义上的网站建设,为互联网品牌在互动行销领域创造价值而不懈努力!
Go
编译生成的是一个静态可执行文件,除了glibc外没有其他外部依赖。这让部署变得异常方便:目标机器上只需要一个基础的系统和必要的管理、监控工具,完全不需要操心应用所需的各种包、库的依赖关系,大大减轻了维护的负担。
2. 并发性好
Goroutine和channel使得编写高并发的服务端软件变得相当容易,很多情况下完全不需要考虑锁机制以及由此带来的各种问题。单个Go应用也能有效的利用多个CPU核,并行执行的性能好。
3. 良好的语言设计
从学术的角度讲Go语言其实非常平庸,不支持许多高级的语言特性;但从工程的角度讲,Go的设计是非常优秀的:规范足够简单灵活,有其他语言基础的程序员都能迅速上手。更重要的是
Go 自带完善的工具链,大大提高了团队协作的一致性。
4. 执行性能好
虽然不如 C 和 Java,但相比于其他编程语言,其执行性能还是很好的,适合编写一些瓶颈业务,内存占用也非常省。
第十名、R语言
R语言,一种自由软件编程语言与操作环境,主要用于统计分析、绘图、数据挖掘。R基于S语言的一个GNU计划项目,所以也可以当作S语言的一种实现,通常用S语言编写的代码都可以不作修改的在R环境下运行。R的语法是来自Scheme。
提名词
R语言作者,George Ross Ihaka:在奥克兰大学统计系任副教授,是R语言的最初作者。
2
/10
第九名、Python
颁奖词
Python是一种广泛使用的高级编程语言,属于通用型编程语言。作为一种解释型语言,Python的设计哲学强调代码的可读性和简洁的语法。相比于C++或Java,Python让开发者能够用更少的代码表达想法。不管是小型还是大型程序,该语言都试图让程序的结构清晰明了。
提名词
Python语言作者,Guido van Rossum:生于荷兰哈勒姆,计算机程序员,为Python程序设计语言的最初设计者及主要架构师。
3
/10
第八名、C语言
颁奖词
C是一种通用的编程语言,广泛用于系统软件与应用软件的开发。C语言具有高效、灵活、功能丰富、表达力强和较高的可移植性等特点。C语言编译器普遍存在于各种不同的操作系统中,例如Microsoft Windows、macOS、Linux、Unix等。C语言的设计影响了众多后来的编程语言,例如C++、Objective-C、Java、C#等。
提名词
C语言作者,Dennis MacAlistair Ritchie:美国计算机科学家。黑客圈子通常称他为“dmr”。他是C语言的创造者、Unix操作系统的关键开发者,对计算机领域产生了深远影响,并与肯·汤普逊同为1983年图灵奖得主。
4
/10
第七名、Go
颁奖词
Go(又称Golang)是Google开发的一种静态强类型、编译型、并发型,并具有垃圾回收功能的编程语言。Go的语法接近C语言,但对于变量的声明有所不同。Go支持垃圾回收功能。
提名词
Go语言作者,Robert C. Pike:来自加拿大的程序员,曾经加入贝尔实验室,为 UNIX小组的成员。他与肯·汤普逊共同开发了UTF-8。目前为 google的工程师,参与编程语言 Go与Sawzall的研发工作。
5
/10
第六名、JavaScript
颁奖词
JavaScript,通常缩写为JS,是一种高级的,解释执行的编程语言。JavaScript是一门基于原型、函数先行的语言,是一门多范式的语言,它支持面向对象编程,命令式编程,以及函数式编程。它已经由ECMA(欧洲计算机制造商协会)通过ECMAScript实现语言的标准化。它被世界上的绝大多数网站所使用,也被世界主流浏览器(Chrome、IE、Firefox、Safari、Opera)支持。
提名词
JavaScript语言作者,Brendan Eich:美国程序员与企业家,JavaScript主要创造者与架构师,曾任Mozilla公司的首席技术官,并曾短暂担任首席执行官。
6
/10
第五名、Objective-C
颁奖词
Objective-C是一种通用、高级、面向对象的编程语言。它扩展了标准的ANSI C编程语言,将Smalltalk式的消息传递机制加入到ANSI C中。目前主要支持的编译器有GCC和Clang(采用LLVM作为后端)。
提名词
Objective-C作者,Brad Cox:美国计算机科学家。于傅尔曼大学主修化学与数学,于芝加哥大学取得数学生物学博士学位。Objective-C主要作者。
7
/10
第四名、PHP
颁奖词
PHP(全称:PHP:Hypertext Preprocessor,即“PHP:超文本预处理器”)是开源的通用计算机脚本语言,尤其适用于网络开发并可嵌入HTML中使用。PHP的语法借鉴吸收C语言、Java和Perl等流行计算机语言的特点,易于一般程序员学习。PHP的主要目标是允许网络开发人员快速编写动态页面,但PHP也被用于其他很多领域。
提名词
PHP语言作者,Rasmus Lerdorf:出生于格陵兰岛凯凯塔苏瓦克,是一个丹麦程序员,他拥有加拿大国籍。他也是编程语言PHP的创始人,其中PHP的头两个版本是由他编写的,后来他也参与PHP后续版本的开发。
8
/10
第三名、Java
颁奖词
Java是一种广泛使用的计算机编程语言,拥有跨平台、面向对象、泛型编程的特性,广泛应用于企业级Web应用开发和移动应用开发。Java编程语言是个简单、面向对象、分布式、解释性、健壮、安全与系统无关、可移植、高性能、多线程和动态的语言。
提名词
Java语言作者,James Gosling:出生于加拿大,软件专家,Java编程语言的共同创始人之一,一般公认他为“Java之父”。
9
/10
第二名、C++
颁奖词
C++是一种使用广泛的计算机程序设计语言。它是一种通用程序设计语言,支持多重编程模式,例如过程化程序设计、数据抽象、面向对象程序设计、泛型程序设计和设计模式等。
提名词
C++语言作者,Bjarne Stroustrup:生于丹麦奥胡斯郡,计算机科学家。他以创造C++编程语言而闻名,被称为“C++之父”。
10
/10
第一名、Visual Basic .NET
颁奖词
Visual Basic .NET(VB.NET)是.NET Framework框架下的一种多重编程范式高级语言。Visual Basic .NET属Basic系语言,其语法特点是以极具亲和力的英文单词为基础标识,以及与自然语言极其相近的逻辑表达,有时候你会觉得写VB.NET代码就好像在写英文句子一样,从这个角度来说,VB.NET似乎是最高级的一门编程语言,当然在Basic系语言中VB.NET也确实是迄今为止最强大的一门编程语言。
提名词
Visual Basic .NET作者,Alan Cooper:交互设计的提倡者。库珀有些时候被叫做 Visual Basic 之父,虽然大多数的工作是由微软的内部开发团队完成的,但是对于Windows可视化设计工具的创意是来源于库珀的。
本文目录如下,阅读本文后,将一网打尽下面Golang Map相关面试题
Go中的map是一个指针,占用8个字节,指向hmap结构体; 源码 src/runtime/map.go 中可以看到map的底层结构
每个map的底层结构是hmap,hmap包含若干个结构为bmap的bucket数组。每个bucket底层都采用链表结构。接下来,我们来详细看下map的结构
bmap 就是我们常说的“桶”,一个桶里面会最多装 8 个 key,这些 key 之所以会落入同一个桶,是因为它们经过哈希计算后,哈希结果是“一类”的,关于key的定位我们在map的查询和插入中详细说明。在桶内,又会根据 key 计算出来的 hash 值的高 8 位来决定 key 到底落入桶内的哪个位置(一个桶内最多有8个位置)。
bucket内存数据结构可视化如下:
注意到 key 和 value 是各自放在一起的,并不是 key/value/key/value/... 这样的形式。源码里说明这样的好处是在某些情况下可以省略掉 padding字段,节省内存空间。
当 map 的 key 和 value 都不是指针,并且 size 都小于 128 字节的情况下,会把 bmap 标记为不含指针,这样可以避免 gc 时扫描整个 hmap。但是,我们看 bmap 其实有一个 overflow 的字段,是指针类型的,破坏了 bmap 不含指针的设想,这时会把 overflow 移动到 extra 字段来。
map是个指针,底层指向hmap,所以是个引用类型
golang 有三个常用的高级类型 slice 、map、channel, 它们都是 引用类型 ,当引用类型作为函数参数时,可能会修改原内容数据。
golang 中没有引用传递,只有值和指针传递。所以 map 作为函数实参传递时本质上也是值传递,只不过因为 map 底层数据结构是通过指针指向实际的元素存储空间,在被调函数中修改 map,对调用者同样可见,所以 map 作为函数实参传递时表现出了引用传递的效果。
因此,传递 map 时,如果想修改map的内容而不是map本身,函数形参无需使用指针
map 底层数据结构是通过指针指向实际的元素 存储空间 ,这种情况下,对其中一个map的更改,会影响到其他map
map 在没有被修改的情况下,使用 range 多次遍历 map 时输出的 key 和 value 的顺序可能不同。这是 Go 语言的设计者们有意为之,在每次 range 时的顺序被随机化,旨在提示开发者们,Go 底层实现并不保证 map 遍历顺序稳定,请大家不要依赖 range 遍历结果顺序。
map 本身是无序的,且遍历时顺序还会被随机化,如果想顺序遍历 map,需要对 map key 先排序,再按照 key 的顺序遍历 map。
map默认是并发不安全的,原因如下:
Go 官方在经过了长时间的讨论后,认为 Go map 更应适配典型使用场景(不需要从多个 goroutine 中进行安全访问),而不是为了小部分情况(并发访问),导致大部分程序付出加锁代价(性能),决定了不支持。
场景: 2个协程同时读和写,以下程序会出现致命错误:fatal error: concurrent map writes
如果想实现map线程安全,有两种方式:
方式一:使用读写锁 map + sync.RWMutex
方式二:使用golang提供的 sync.Map
sync.map是用读写分离实现的,其思想是空间换时间。和map+RWLock的实现方式相比,它做了一些优化:可以无锁访问read map,而且会优先操作read map,倘若只操作read map就可以满足要求(增删改查遍历),那就不用去操作write map(它的读写都要加锁),所以在某些特定场景中它发生锁竞争的频率会远远小于map+RWLock的实现方式。
golang中map是一个kv对集合。底层使用hash table,用链表来解决冲突 ,出现冲突时,不是每一个key都申请一个结构通过链表串起来,而是以bmap为最小粒度挂载,一个bmap可以放8个kv。在哈希函数的选择上,会在程序启动时,检测 cpu 是否支持 aes,如果支持,则使用 aes hash,否则使用 memhash。
map有3钟初始化方式,一般通过make方式创建
map的创建通过生成汇编码可以知道,make创建map时调用的底层函数是 runtime.makemap 。如果你的map初始容量小于等于8会发现走的是 runtime.fastrand 是因为容量小于8时不需要生成多个桶,一个桶的容量就可以满足
makemap函数会通过 fastrand 创建一个随机的哈希种子,然后根据传入的 hint 计算出需要的最小需要的桶的数量,最后再使用 makeBucketArray 创建用于保存桶的数组,这个方法其实就是根据传入的 B 计算出的需要创建的桶数量在内存中分配一片连续的空间用于存储数据,在创建桶的过程中还会额外创建一些用于保存溢出数据的桶,数量是 2^(B-4) 个。初始化完成返回hmap指针。
找到一个 B,使得 map 的装载因子在正常范围内
Go 语言中读取 map 有两种语法:带 comma 和 不带 comma。当要查询的 key 不在 map 里,带 comma 的用法会返回一个 bool 型变量提示 key 是否在 map 中;而不带 comma 的语句则会返回一个 value 类型的零值。如果 value 是 int 型就会返回 0,如果 value 是 string 类型,就会返回空字符串。
map的查找通过生成汇编码可以知道,根据 key 的不同类型,编译器会将查找函数用更具体的函数替换,以优化效率:
函数首先会检查 map 的标志位 flags。如果 flags 的写标志位此时被置 1 了,说明有其他协程在执行“写”操作,进而导致程序 panic。这也说明了 map 对协程是不安全的。
key经过哈希函数计算后,得到的哈希值如下(主流64位机下共 64 个 bit 位):
m: 桶的个数
从buckets 通过 hash m 得到对应的bucket,如果bucket正在扩容,并且没有扩容完成,则从oldbuckets得到对应的bucket
计算hash所在桶编号:
用上一步哈希值最后的 5 个 bit 位,也就是 01010 ,值为 10,也就是 10 号桶(范围是0~31号桶)
计算hash所在的槽位:
用上一步哈希值哈希值的高8个bit 位,也就是 10010111 ,转化为十进制,也就是151,在 10 号 bucket 中寻找** tophash 值(HOB hash)为 151* 的 槽位**,即为key所在位置,找到了 2 号槽位,这样整个查找过程就结束了。
如果在 bucket 中没找到,并且 overflow 不为空,还要继续去 overflow bucket 中寻找,直到找到或是所有的 key 槽位都找遍了,包括所有的 overflow bucket。
通过上面找到了对应的槽位,这里我们再详细分析下key/value值是如何获取的:
bucket 里 key 的起始地址就是 unsafe.Pointer(b)+dataOffset。第 i 个 key 的地址就要在此基础上跨过 i 个 key 的大小;而我们又知道,value 的地址是在所有 key 之后,因此第 i 个 value 的地址还需要加上所有 key 的偏移。
通过汇编语言可以看到,向 map 中插入或者修改 key,最终调用的是 mapassign 函数。
实际上插入或修改 key 的语法是一样的,只不过前者操作的 key 在 map 中不存在,而后者操作的 key 存在 map 中。
mapassign 有一个系列的函数,根据 key 类型的不同,编译器会将其优化为相应的“快速函数”。
我们只用研究最一般的赋值函数 mapassign 。
map的赋值会附带着map的扩容和迁移,map的扩容只是将底层数组扩大了一倍,并没有进行数据的转移,数据的转移是在扩容后逐步进行的,在迁移的过程中每进行一次赋值(access或者delete)会至少做一次迁移工作。
1.判断map是否为nil
每一次进行赋值/删除操作时,只要oldbuckets != nil 则认为正在扩容,会做一次迁移工作,下面会详细说下迁移过程
根据上面查找过程,查找key所在位置,如果找到则更新,没找到则找空位插入即可
经过前面迭代寻找动作,若没有找到可插入的位置,意味着需要扩容进行插入,下面会详细说下扩容过程
通过汇编语言可以看到,向 map 中删除 key,最终调用的是 mapdelete 函数
删除的逻辑相对比较简单,大多函数在赋值操作中已经用到过,核心还是找到 key 的具体位置。寻找过程都是类似的,在 bucket 中挨个 cell 寻找。找到对应位置后,对 key 或者 value 进行“清零”操作,将 count 值减 1,将对应位置的 tophash 值置成 Empty
再来说触发 map 扩容的时机:在向 map 插入新 key 的时候,会进行条件检测,符合下面这 2 个条件,就会触发扩容:
1、装载因子超过阈值
源码里定义的阈值是 6.5 (loadFactorNum/loadFactorDen),是经过测试后取出的一个比较合理的因子
我们知道,每个 bucket 有 8 个空位,在没有溢出,且所有的桶都装满了的情况下,装载因子算出来的结果是 8。因此当装载因子超过 6.5 时,表明很多 bucket 都快要装满了,查找效率和插入效率都变低了。在这个时候进行扩容是有必要的。
对于条件 1,元素太多,而 bucket 数量太少,很简单:将 B 加 1,bucket 最大数量( 2^B )直接变成原来 bucket 数量的 2 倍。于是,就有新老 bucket 了。注意,这时候元素都在老 bucket 里,还没迁移到新的 bucket 来。新 bucket 只是最大数量变为原来最大数量的 2 倍( 2^B * 2 ) 。
2、overflow 的 bucket 数量过多
在装载因子比较小的情况下,这时候 map 的查找和插入效率也很低,而第 1 点识别不出来这种情况。表面现象就是计算装载因子的分子比较小,即 map 里元素总数少,但是 bucket 数量多(真实分配的 bucket 数量多,包括大量的 overflow bucket)
不难想像造成这种情况的原因:不停地插入、删除元素。先插入很多元素,导致创建了很多 bucket,但是装载因子达不到第 1 点的临界值,未触发扩容来缓解这种情况。之后,删除元素降低元素总数量,再插入很多元素,导致创建很多的 overflow bucket,但就是不会触发第 1 点的规定,你能拿我怎么办?overflow bucket 数量太多,导致 key 会很分散,查找插入效率低得吓人,因此出台第 2 点规定。这就像是一座空城,房子很多,但是住户很少,都分散了,找起人来很困难
对于条件 2,其实元素没那么多,但是 overflow bucket 数特别多,说明很多 bucket 都没装满。解决办法就是开辟一个新 bucket 空间,将老 bucket 中的元素移动到新 bucket,使得同一个 bucket 中的 key 排列地更紧密。这样,原来,在 overflow bucket 中的 key 可以移动到 bucket 中来。结果是节省空间,提高 bucket 利用率,map 的查找和插入效率自然就会提升。
由于 map 扩容需要将原有的 key/value 重新搬迁到新的内存地址,如果有大量的 key/value 需要搬迁,会非常影响性能。因此 Go map 的扩容采取了一种称为“渐进式”的方式,原有的 key 并不会一次性搬迁完毕,每次最多只会搬迁 2 个 bucket。
上面说的 hashGrow() 函数实际上并没有真正地“搬迁”,它只是分配好了新的 buckets,并将老的 buckets 挂到了 oldbuckets 字段上。真正搬迁 buckets 的动作在 growWork() 函数中,而调用 growWork() 函数的动作是在 mapassign 和 mapdelete 函数中。也就是插入或修改、删除 key 的时候,都会尝试进行搬迁 buckets 的工作。先检查 oldbuckets 是否搬迁完毕,具体来说就是检查 oldbuckets 是否为 nil。
如果未迁移完毕,赋值/删除的时候,扩容完毕后(预分配内存),不会马上就进行迁移。而是采取 增量扩容 的方式,当有访问到具体 bukcet 时,才会逐渐的进行迁移(将 oldbucket 迁移到 bucket)
nevacuate 标识的是当前的进度,如果都搬迁完,应该和2^B的长度是一样的
在evacuate 方法实现是把这个位置对应的bucket,以及其冲突链上的数据都转移到新的buckets上。
转移的判断直接通过tophash 就可以,判断tophash中第一个hash值即可
遍历的过程,就是按顺序遍历 bucket,同时按顺序遍历 bucket 中的 key。
map遍历是无序的,如果想实现有序遍历,可以先对key进行排序
为什么遍历 map 是无序的?
如果发生过迁移,key 的位置发生了重大的变化,有些 key 飞上高枝,有些 key 则原地不动。这样,遍历 map 的结果就不可能按原来的顺序了。
如果就一个写死的 map,不会向 map 进行插入删除的操作,按理说每次遍历这样的 map 都会返回一个固定顺序的 key/value 序列吧。但是 Go 杜绝了这种做法,因为这样会给新手程序员带来误解,以为这是一定会发生的事情,在某些情况下,可能会酿成大错。
Go 做得更绝,当我们在遍历 map 时,并不是固定地从 0 号 bucket 开始遍历,每次都是从一个**随机值序号的 bucket 开始遍历,并且是从这个 bucket 的一个 随机序号的 cell **开始遍历。这样,即使你是一个写死的 map,仅仅只是遍历它,也不太可能会返回一个固定序列的 key/value 对了。
基本设计思路:
类型转换、类型断言、动态派发。iface,eface。
反射对象具有的方法:
编译优化:
内部实现:
实现 Context 接口有以下几个类型(空实现就忽略了):
互斥锁的控制逻辑:
设计思路:
(以上为写被读阻塞,下面是读被写阻塞)
总结,读写锁的设计还是非常巧妙的:
设计思路:
WaitGroup 有三个暴露的函数:
部件:
设计思路:
结构:
Once 只暴露了一个方法:
实现:
三个关键点:
细节:
让多协程任务的开始执行时间可控(按顺序或归一)。(Context 是控制结束时间)
设计思路: 通过一个锁和内置的 notifyList 队列实现,Wait() 会生成票据,并将等待协程信息加入链表中,等待控制协程中发送信号通知一个(Signal())或所有(Boardcast())等待者(内部实现是通过票据通知的)来控制协程解除阻塞。
暴露四个函数:
实现细节:
部件:
包: golang.org/x/sync/errgroup
作用:开启 func() error 函数签名的协程,在同 Group 下协程并发执行过程并收集首次 err 错误。通过 Context 的传入,还可以控制在首次 err 出现时就终止组内各协程。
设计思路:
结构:
暴露的方法:
实现细节:
注意问题:
包: "golang.org/x/sync/semaphore"
作用:排队借资源(如钱,有借有还)的一种场景。此包相当于对底层信号量的一种暴露。
设计思路:有一定数量的资源 Weight,每一个 waiter 携带一个 channel 和要借的数量 n。通过队列排队执行借贷。
结构:
暴露方法:
细节:
部件:
细节:
包: "golang.org/x/sync/singleflight"
作用:防击穿。瞬时的相同请求只调用一次,response 被所有相同请求共享。
设计思路:按请求的 key 分组(一个 *call 是一个组,用 map 映射存储组),每个组只进行一次访问,组内每个协程会获得对应结果的一个拷贝。
结构:
逻辑:
细节:
部件:
如有错误,请批评指正。