扫一扫下方二维码,关注本站官方公众号
获取永久解锁本站全部文章的验证码
还能不定期领现金红包

Go面试看这里了~(四)-Go语言中文社区

Go面试看这里了~(四)


原文地址:Go面试看这里了~(四)

1、map底层实现?

map底层实现是一个散列表,因此实现map的过程就是实现散列表的过程,其中主要有两个结构体,hmap和bmap,来看下源码:

//map结构体是hmap,是hashmap的缩写type hmap struct {    count      int            //元素个数,调用len(map)时直接返回    flags      uint8          //标志map当前状态,正在删除元素、添加元素.....    B          uint8          //单元(buckets)的对数 B=5表示能容纳32个元素    noverflow  uint16         //单元(buckets)溢出数量,如果一个单元能存8个key,此时存储了9个,溢出了,就需要再增加一个单元    hash0      uint32         //哈希种子    buckets    unsafe.Pointer //指向单元(buckets)数组,大小为2^B,可以为nil    oldbuckets unsafe.Pointer //扩容的时候,buckets长度会是oldbuckets的两倍    nevacute   uintptr        //指示扩容进度,小于此buckets迁移完成    extra      *mapextra      //与gc相关 可选字段}//a bucket for a Go maptype bmap struct {    // 每个元素hash值的高8位,如果tophash[0] < minTopHash,表示这个桶的搬迁状态    tophash [bucketCnt]uint8    // 接下来是8个key、8个value,但是我们不能直接看到;为了优化对齐,go采用了key放在一起,value放在一起的存储方式,    // 再接下来是hash冲突发生时,下一个溢出桶的地址}//实际上编辑期间会动态生成一个新的结构体type bmap struct {    topbits  [8]uint8    keys     [8]keytype    values   [8]valuetype    pad      uintptr    overflow uintptr}

上述代码中的bmap可理解为常说的【桶】,桶里面会最多装 8 个 key,这些 key 之所以会落入同一个桶,是因为它们经过哈希计算后,哈希结果是“一类”的,在桶内,又会根据 key 计算出来的 hash 值的高 8 位来决定 key 到底落入桶内的哪个位置(一个桶内最多有8个位置)。

hmap结构图如下:

上图中最重要的是buckets数组,用于存储的结构,再来看bmap的结构图,如下:

上图中最重要的就是【字节数组】,map的key和value就存储在此处,【高位哈希值】用于记录当前bucket中key相关的索引,最后一个字段【pointer】指向的是扩容后的bucket的指针,使得bucket形成一个链表结构,大体结构图如下:

汇总来看的话,hmap和bmap的关系如下:

又因为bucket是链表结构,所以整体关系如下:

2、map扩容?

验证是否需要扩容的关键就是哈希表中的加载因子(loadFactor),是一个阈值,一般为散列包含的元素数除以位置总数得出来的结果,是产生冲突机会和空间使用的平衡和折中,loadFactor越小说明空间空置率高,空间使用率小,反之则表示空间使用率高,但是产生冲突的机会也就随之而增加。

每种哈希表都会有一个加载因子,数值超过加载因子就会为哈希表扩容,Go的map加载因子公式是:map长度除以2的B次方(B为map已扩容的次数)。

触发map扩容的条件如下:

  1. 加载因子大于6.5。

  2. 使用了太多的溢出桶时(溢出桶使用的太多会导致map处理速度降低)。

B<=15,已使用的溢出桶个数>=2的B次方时,引发等量扩容。

B>15,已使用的溢出桶个数>=2的15次方时,引发等量扩容。

扩容方法如下:

  1. 双倍扩容:使用渐进式的方式,原有key不会一次搬迁完毕,每次最多只搬迁2个bucket。

  2. 等量扩容:重新排列,极端情况下map成为链表时,重新排列也没用,此时哈希种子hash0的设置可减少此类状况。

3、map查找元素?

map采用哈希查找表,有一个key通过哈希函数得到哈希值,64位系统中就生成一个64bit的哈希值,由此key对应到不同的bucket(桶),当有多个哈希值同时映射到一个桶时,使用链表解决冲突。

key经过hash后共64位,根据hmap中B的值,计算此值要对应到哪个桶,桶的数量为2的B次方,如B=5,则用64位后5位表示第几号桶,之后用hash值的高8位确定在bucket中的存储位置,当前bmap中未找到则查询对应的overflow bucket对应的位置是否有数据,有则与完整的哈希值进行对比,确认是否是需要查询的数据。

如不同key对应同一桶,hash冲突用链表解决,遍历bucket中的key,如正处于map扩容,处于数据搬迁状态,则优先从oldbuckets查找。

4、介绍一下channel?

Go尽量不用共享内存来通信,通过通信来实现内存共享,CSP并发模型,也就是通信顺序进程,是通过goroutine和channel来实现的。

channel收发消息遵循先进先出,分为有缓存和无缓冲,channel大致有buffer(当前缓冲区为0时,是个ring buffer)、sendx和recvx收发的位置(ring buffer记录实现)、sendq、recvq,当前channel因缓冲区不足而阻塞队列、使用双向链表存储、mutex锁控制并发等。

5、channel特性?

  1. 向nil channel发送数据会造成永远阻塞。

  2. 读nil channel内的数据会造成永远阻塞。

  3. 给已关闭的channel发送数据会引起panic。

  4. 读已关闭的channel,如缓冲区为空,则返回零值。

  5. 无缓冲channel是同步的,有缓冲的channel是非同步的。

  6. 关闭一个nil会发生panic。

6、channel的ring buffer实现?

channel使用ring buffer(环形缓冲区)来缓存写入的数据,非常适合实现先进先出式的固定长度队列,ring buffer实现如下:

hchan有recvx和sendx这两个与buffer相关的变量,sendx表示buffer中可写的index,recvx表示buffer中可读的index,从recvx到sendx之间的元素表示正常存入buffer的元素。

使用buf[recvx]读取队列第一个元素,buf[sendx]=x意为来将x放入队列尾部。

7、mutex的几种状态?

  1. mutexLocked:互斥锁的锁定状态。

  2. mutexWoken:从正常模式被唤醒。

  3. mutexStarving:当前互斥锁进入饥饿状态。

  4. waitersCount:当前互斥锁上等待的goroutine数目。

至此,本次分享就结束了,后期会慢慢补充。

以上仅为个人观点,不一定准确,能帮到各位那是最好的。

好啦,到这里本文就结束了,喜欢的话就来个三连击吧。

以上均为个人认知,如有侵权,请联系删除。

版权声明1:本文来源CSDN,感谢博主原创文章,遵循 CC 4.0 by-sa 版权协议,转载请附上原文出处链接和本声明。
原文链接:https://blog.csdn.net/luyaran/article/details/121348759
站方申明:本站部分内容来自社区用户分享,若涉及侵权,请联系站方删除。
  • 发表于 2021-12-11 17:35
  • 阅读 ( 876 )
  • 分类:面试题

0 条评论

请先 登录 后评论

官方社群