本文目录如下,阅读本文后,将一网打尽下面Golang Map相关面试题
每个map的底层结构是hmap,hmap包含若干个结构为bmap的bucket数组.每个bucket底层都采用链表结构.此时此刻呢,我们来详细看下map的结构
bucket内存数据结构可视化如下:
注意到 key 和 value 是各自放在一起的,并不是 key/value/key/value/... 这样的形式.源码里说明这样的好处是在某些情况下可以省略掉 padding字段,节省内存空间.
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 中进行安全访问),而不是为了小部分情况(并发访问),导致大部分程序付出加锁代价(性能),决定了不支持.
如果想实现map线程安全,有两种方式:
方式一:使用读写锁 map + sync.RWMutex
方式二:使用golang提供的 sync.Map
sync.map是用读写分离实现的,其思想是空间换时间.和map+RWLock的实现方式相比,它做了一些优化:可以无锁访问read map,而且会优先操作read map,倘若只操作read map就可以满足要求(增删改查遍历),那就不用去操作write map(它的读写都要加锁),所以在某些特定场景中它发生锁竞争的频率会远远小于map+RWLock的实现方式.
找到一个 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 对协程是不安全的.
m: 桶的个数
从buckets 通过 hash m 得到对应的bucket,如果bucket正在扩容,并且没有扩容完成,则从oldbuckets得到对应的bucket
计算hash所在桶编号:
计算hash所在的槽位:
如果在 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)会至少做一次迁移工作.
①判断map是否为nil
每一次进行赋值/删除操作时,只要oldbuckets != nil 则认为正在扩容,会做一次迁移工作,下面会详细说下迁移过程
根据上面查找过程,查找key所在位置,如果找到则更新,没找到则找空位插入即可
经过前面迭代寻找动作,若没有找到可插入的位置,意味着需要扩容进行插入,下面会详细说下扩容过程
通过汇编语言可以看到,向 map 中删除 key,最终调用的是 mapdelete 函数
删除的逻辑相对比较简单,大多函数在赋值操作中已经用到过,核心还是找到 key 的具体位置.寻找过程都是类似的,在 bucket 中挨个 cell 寻找.找到对应位置后,对 key 或者 value 进行"清零"操作,将 count 值减 1,将对应位置的 tophash 值置成 Empty
①.、装载因子超过阈值
在装载因子比较小的情况下,这时候 map 的查找和插入效率也很低,而第 1 点识别不出来这种情况.表面现象就是计算装载因子的分子比较小,即 map 里元素总数少,但是 bucket 数量多(真实分配的 bucket 数量多,包括大量的 overflow bucket)
上面说的 hashGrow() 函数实际上并没有真正地"搬迁",它只是分配好了新的 buckets,并将老的 buckets 挂到了 oldbuckets 字段上.真正搬迁 buckets 的动作在 growWork() 函数中,而调用 growWork() 函数的动作是在 mapassign 和 mapdelete 函数中.也就是插入或修改、删除 key 的时候,都会尝试进行搬迁 buckets 的工作.先检查 oldbuckets 是否搬迁完毕,具体来说就是检查 oldbuckets 是否为 nil.
如果未迁移完毕,赋值/删除的时候,扩容完毕后(预分配内存),不会马上就进行迁移.而是采取 增量扩容 的方式,当有访问到具体 bukcet 时,才会逐渐的进行迁移(将 oldbucket 迁移到 bucket)
在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 对了.
①.、简单易学.
Go语言天生支持并发,可以充分利用多核,轻松地使用并发. 这是Go语言最大的特点.
描述
Go的语法接近C语言,但对于变量的声明有所不同.Go支持垃圾回收功能.Go的并行模型是以东尼-霍尔的通信顺序进程(CSP)为基础,采取类似模型的其他语言包括Occam和Limbo,但它也具有Pi运算的特征,比如通道传输.
与C++相比,Go并不包括如枚举、异常处理、继承、泛型、断言、虚函数等功能,但增加了 切片(Slice) 型、并发、管道、垃圾回收、接口(Interface)等特性的语言级支持.
go的另外一个"劣势"就是能玩的花样太少,崇尚一个事情只有一个或少数几种写法.这不符合某些开发人员炫技的心理需求.于是就被诟病为是资质平平的程序员才会去用的语言.
类型 在变量名后边
也可不显式声明类型, 类型推断, 但是是静态语言, name一开始放字符串就不能再赋值数字
方法,属性 分开 方法名首字母大写就是就是外部可调的
面向对象设计的一个重要原则:"优先使用组合而不是继承"
Dog 也是Animal , 要复用Animal 的属性和方法,
只需要在结构体 type 里面写 Animal
入口也是main, 用用试试
多态, 有这个方法就是这个接口的实现, 具体的类 不需要知道自己实现了什么接口,
使用: 在一个函数调用之前加上关键字go 就启动了一个goroutine
创建一个goroutine,它会被加入到一个全局的运行队列当中,
调度器 会把他们分配给某个 逻辑处理器 的队列,
一个逻辑处理器 绑定到一个 操作系统线程 ,在上面运行goroutine,
如果goroutine需要读写文件, 阻塞 ,就脱离逻辑处理器 直接 goroutine - 系统线程 绑定
编译成同名.exe 来执行, 不通过虚拟机, 直接是机器码, 和C 一样, 所以非常快
但是也有自动垃圾回收,每个exe文件当中已经包含了一个类似于虚拟机的runtime,进行goroutine的调度
默认是静态链接的,那个exe会把运行时所需要的所有东西都加进去,这样就可以把exe复制到任何地方去运行了, 所以呢 生成的 .exe 文件非常大
在使用Go语言的时候,碰到了需要对数组进行去重操作的问题.Java语言有Set集合这个数据结构,可以很方便的将数组转为集合,但是Go语言没有Set,如果仅仅是因为去重操作就手动实现一个Set太繁琐了.可以根据Go语言中的map的特性来简单实现一下
这个是对字符串数组去重操作.可以根据需要的类型稍作修改即可.需要注意的是只支持可以作为map键的结构进行去重!
①.、数组是多个 相同类型 的数据的组合,一个数组一旦声明/定义了,其 长度是固定的,不能动态变化 .
? ? ? 数值类型数组:?默认值为 0
? ? ? 字符串数组:? ? ? ?默认值为 ""
? ? ? bool数组:? ? ? ? ? ?默认值为 false
? ? ? (1)声明数组并开辟空间
①.0、长度是数组类型的一部分,在传递函数参数时,需要考虑数组的长度,看以下案例:
以上就是土嘎嘎小编为大家整理的为什么go语言不能集合相关主题介绍,如果您觉得小编更新的文章只要能对粉丝们有用,就是我们最大的鼓励和动力,不要忘记讲本站分享给您身边的朋友哦!!