面试官说下Golang Slice的底层实现,泪崩了!

网友投稿 897 2022-05-30

1、Go 语言当中数组和切片的区别是什么?

数组:

数组固定长度数组长度是数组类型的一部分,所以[3]int 和[4]int 是两种不同 的数组类型数组需要指定大小,不指定也会根据处初始化对的自动推算出大 小,不可改变数组是通过值传递的

切片: 切片可以改变长度切片是轻量级的数据结构,三个属性,指针,长度,容量不 需要指定大小切片是地址传递(引用传递)可以通过数组来初始化,也可以通 过内置函数 make()来初始化,初始化的时候 len=cap,然后进行扩容。

2、Go 语言当中值传递和地址传递(引用传递)如何运用?有什么区别?

值传递只会把参数的值复制一份放进对应的函数,两个变量的地址不同, 不可相互修改。

地址传递(引用传递)会将变量本身传入对应的函数,在函数中可以对该变 量进行值内容的修改。

3、Go 语言当中数组和切片在传递的时候的区别是什么?

数组是值传递

切片是引用传递

4、Go 语言是如何实现切片扩容的?

func main() {

arr := make([]int, 0)

for i := 0; i < 2000; i++ {

fmt.Println("len 为", len(arr), "cap 为", cap(arr))

arr = append(arr, i)

}

}

我们可以看下结果

依次是0,1,2,4,8,16,32,64,128,256,512,1024

但到了 1024 之后,就变成了1024,1280,1696,2304

每次都是扩容了四分之一左右

面试官:说下Golang Slice的底层实现,泪崩了!

5、看下面代码的 defer 的执行顺序是什么? defer 的作用和特点是什么?

defer 的作用是:

你只需要在调用普通函数或方法前加上关键字 defer,就完成了 defer 所需要 的语法。当 defer 语句被执行时,跟在 defer 后面的函数会被延迟执行。直到 包含该 defer 语句的函数执行完毕时,defer 后的函数才会被执行,不论包含defer 语句的函数是通过 return 正常结束,还是由于 panic 导致的异常结束。你可以在一个函数中执行多条 defer 语句,它们的执行顺序与声明顺序相反。

defer 的常用场景:

defer语句经常被用于处理成对的操作,如打开、关闭、连接、断开连接、加锁、释放锁。

通过defer机制,不论函数逻辑多复杂,都能保证在任何执行路径下,资

源被释放。

释放资源的defer应该直接跟在请求资源的语句后。

6、golang Slice 的底层实现

切片是基于数组实现的,它的底层是数组,它自己本身非常小,可以理解为对底层数组的抽象。因为基于数组实现,所以它的底层的内存是连续分配的,效率非常高,还可以通过索引获得数据,可以迭代以及垃圾回收优化。

切片本身并不是动态数组或者数组指针。它内部实现的数据结构通过指针引用 底层数组,设定相关属性将数据读写操作限定在指定的区域内。切片本身是一 个只读对象,其工作机制类似数组指针的一种封装。

切片对象非常小,是因为它是只有 3 个字段的数据结构:

指向底层数组的指针

切片的长度

切片的容量

7、Golang Slice 的扩容机制,有什么注意点?

Go 中切片扩容的策略是这样的:

首先判断,如果新申请容量大于2倍的旧容量,最终容量就是新申请的容 量

否则判断,如果旧切片的长度小于1024,则最终容量就是旧容量的两倍

否则判断,如果旧切片长度大于等于1024,则最终容量从旧容量开始循环

增加原来的 1/4, 直到最终容量大于等于新申请的容量

如果最终容量计算值溢出,则最终容量就是新申请容量

8、扩容前后的 Slice 是否相同?

情况一:

原数组还有容量可以扩容(实际容量没有填充完),这种情况下,扩容以后的 数组还是指向原来的数组,对一个切片的操作可能影响多个指针指向相同地址 的 Slice。

情况二:

原来数组的容量已经达到了最大值,再想扩容, Go 默认会先开一片内存区 域,把原来的值拷贝过来,然后再执行 append() 操作。这种情况丝毫不影响 原数组。

要复制一个 Slice,最好使用 Copy 函数。

9、Golang 的参数传递、引用类型

Go 语言中所有的传参都是值传递(传值),都是一个副本,一个拷贝。因为拷 贝的内容有时候是非引用类型(int、string、struct 等这些),这样就在函 数中就无法修改原内容数据;有的是引用类型(指针、map、slice、chan等 这些),这样就可以修改原内容数据。

Golang 的引用类型包括 slice、map 和 channel。它们有复杂的内部结构,除 了申请内存外,还需要初始化相关属性。内置函数 new 计算类型大小,为其分 配零值内存,返回指针。而 make 会被编译器翻译成具体的创建函数,由其分 配内存和初始化成员结构,返回对象而非指针。

10、Golang Map 底层实现

Golang 中 map 的底层实现是一个散列表,因此实现 map 的过程实际上就是实现 散表的过程。在这个散列表中,主要出现的结构体有两个,一个叫 hmap(a header for a go map),一个叫 bmap(a bucket for a Go map,通常叫其bucket)。

11、Golang Map 如何扩容

装载因子:count/2^B

触发条件:

1. 装填因子是否大于6.5

2. overflow bucket 是否太多

解决方法:

1. 双倍扩容:扩容采取了一种称为“渐进式”地方式,原有的 key 并不会一

次性搬迁完毕,每次最多只会搬迁 2 个 bucket

2. 等量扩容:重新排列,极端情况下,重新排列也解决不了,map成了链表,

性能大大降低,此时哈希种子 hash0 的设置,可以降低此类极端场景的发 生。

12、Golang Map 查找

Go 语言中 map 采用的是哈希查找表,由一个 key 通过哈希函数得到哈希值,64位系统中就生成一个 64bit 的哈希值,由这个哈希值将 key 对应到不同的桶 (bucket)中,当有多个哈希映射到相同的的桶中时,使用链表解决哈希冲 突。key 经过 hash 后共 64 位,根据 hmap 中 B 的值,计算它到底要落在哪个桶 时,桶的数量为 2^B,如 B=5,那么用 64 位最后 5 位表示第几号桶,在用 hash值的高 8 位确定在 bucket 中的存储位置,当前 bmap 中的 bucket 未找到,则查 询对应的 overflow bucket,对应位置有数据则对比完整的哈希值,确定是否 是要查找的数据。

如果两个不同的 key 落在的同一个桶上,hash 冲突使用链表法接近,遍历bucket 中的 key 如果当前处于 map 进行了扩容,处于数据搬移状态,则优先从oldbuckets 查找。

13、介绍一下 Channel

Go 语言中,不要通过共享内存来通信,而要通过通信来实现内存共享。Go 的CSP(Communicating Sequential Process)并发模型,中文可以叫做通信顺序进 程,是通过 goroutine 和 channel 来实现的。

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

14、Go 语言的 Channel 特性?

给一个 nil channel 发送数据,造成永远阻塞

从一个 nil channel 接收数据,造成永远阻塞

给一个已经关闭的 channel 发送数据,引起 panic

从一个已经关闭的 channel 接收数据,如果缓冲区中为空,则返回一个零值

无缓冲的channel是同步的,而有缓冲的channel是非同步的

关闭一个 nil channel 将会发生 panic

15、Channel 的 ring buffer 实现

channel 中使用了 ring buffer(环形缓冲区) 来缓存写入的数据。ring buffer 有很多好处,而且非常适合用来实现 FIFO 式的固定长度队列。在 channel 中,ring buffer 的实现如下:

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

我们可以直接使用 buf[recvx]来读取到队列的第一个元素,使用 buf[sendx] = x 来将元素放到队尾。

最后:

点击下方名片链接,关注 「码农编程进阶笔记 」微信公众号,在微信聊天对话框回复「go电子书」「黑马Go语言」或者直接长按左下图海报中的二维码,可获取最新golang电子书和视频资源

Go 数据结构

版权声明:本文内容由网络用户投稿,版权归原作者所有,本站不拥有其著作权,亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容,请联系我们jiasou666@gmail.com 处理,核实后本网站将在24小时内删除侵权内容。

上一篇:性能基础之CPU、物理核、逻辑核概念与关系
下一篇:一文纵览向量检索
相关文章