网站开发PHP程序员招聘,注册公司需要啥资料,微网站微信数据库设计,线上营销课程3. 数组和切片
3.1 数组和切片的区别
Go语言中数组是固定长度的#xff0c;不能动态扩容#xff0c;在编译期就会确定大小。 切片是一种数据结构#xff0c;包含一个底层数组的指针#xff0c;当前切片个数 len 以及切片的最大容量 cap#xff0c; 描述的是一块数组。
…3. 数组和切片
3.1 数组和切片的区别
Go语言中数组是固定长度的不能动态扩容在编译期就会确定大小。 切片是一种数据结构包含一个底层数组的指针当前切片个数 len 以及切片的最大容量 cap 描述的是一块数组。
3.2 切片的扩容策略
切片的扩容都是调用growslice方法不同版本扩容机制也有细微差距。 Go1.17 版本切片在扩容时会进行内存对齐这个和内存分配策略相关。进行内存对齐之后新 slice 的容量是要 大于等于老 slice 容量的 2倍或者1.25倍。 当新切片需要的容量大于两倍扩容的容量则直接按照新切片需要的容量扩容当原 slice 容量小于 1024 的时候新 slice 容量变成原来的 2 倍原 slice 容量超过 1024新 slice 容量变成原来的1.25倍。 在1.18时又改成不和1024比较了而是和256比较。 简单地说就是小切片按照2倍扩容大切片按照1.25倍扩容。 Go官方注释说这么做的目的是能更平滑的过渡。
3.3 Go 中对 nil 的 Slice 和空 Slice 的处理是一致的吗?
首先 Go 的 JSON 标准库对 nil slice 和 空 slice 的处理是不一致。
slice : make([]int,0slice 不为 nil但是 slice 没有值slice 的底层的空间是空的。slice : []int{} slice 的值是 nil可用于需要返回 slice 的函数当函数出现异常的时候保证函数依然会有 nil 的返回值。
4. map
4.1 map 的底层实现
Golang 中 map 的底层实现是一个散列表因此实现 map 的过程实际上就是实现散表的过程。在这个散列表中主要出现的结构体有两个一个叫 hmap(a header for a go map)一个叫 bmap(a bucket for a Go map通常叫其 bucket)。
4.2 map 如何扩容
扩容其实就是一个预分配内容的过程在 map 中的表现是 预分配 bucket。
双倍扩容扩容采取了一种称为“渐进式”的方式原有的 key 并不会一 次性搬迁完毕每次最多只会搬迁 2 个 bucket。等量扩容重新排列极端情况下重新排列也解决不了map 存储就会蜕变成链表性能大大降低此时哈希因子 hash0 的设置可以降低此类极端场景的发生。
4.3 什么时候会发生扩容
触发 map 扩容的时机在向 map 插入新 key 的时候会进行条件检测符合下面这 2 个条件就会触发扩容
装载因子超过阈值overflow 的 bucket 数量过多 对于条件 1元素太多而 bucket 数量太少很简单将 B 加 1bucket 最大数量(2^B)直接变成原来 bucket 数量的 2 倍。于是就有新老 bucket 了。注意这时候元素都在老 bucket 里还没迁移到新的 bucket 来。新 bucket 只是最大数量变为原来最大数量的 2 倍(2^B * 2) 。对于条件 2其实元素没那么多但是 overflow bucket 数特别多说明很多 bucket 都没装满。解决办法就是开辟一个新 bucket 空间将老 bucket 中的元素移动到新 bucket使得同一个 bucket 中的 key 排列地更紧密。这样原来在 overflow bucket 中的 key 可以移动到 bucket 中来。结果是节省空间提高 bucket 利用率map 的查找和插入效率自然就会提升。 4.4 map 什么时候会发生迁移
map 扩容完毕后不会马上就进行迁移。而是采取增量扩容的方式当有访问到具体 bukcet 时才会逐渐的进行迁移将 oldbucket 迁移到 bucket。
4.5 map 查找
Go 语言中 map 采用的是哈希查找表由一个 key 通过哈希函数得到哈希值64 位系统中就生成一个 64bit 的哈希值由这个哈希值将 key 对应存到不同的桶 bucket中当有多个哈希映射到相同的的桶中时使用链表解决哈希冲突。 细节key 经过 hash 后共 64 位根据 hmap 中 B 的值计算它到底要落在哪个桶时桶的数量为 2B 如 B5那么用 64 位最后 5 位表示第几号桶在用hash 值的高 8 位确定在 bucket 中的存储位置当前 bmap 中的 bucket 未找到则查询对应的 overflow bucket对应位置有数据则对比完整的哈希值 确定是否是要查找的数据。如果当前 map 处于数据搬移状态则优先从 oldbuckets 查找。
4.6 map 删除
删除的逻辑相对比较简单核心是找到 key 的具体位置。在 bucket 中挨个 cell 寻找。找到对应位置后对 key 或者 value 进行“清零”操作将 count 值减 1将对应位置的 tophash 值置成 Empty
4.7 为什么遍历map是无序的
遍历的过程就是按顺序遍历 bucket同时按顺序遍历 bucket 中的 key而每个 key 进入 bucket 之前都先进行了哈希散列所以没办法保证遍历的有序性。
4.8 如何实现有序遍历map
可以把 map 的 key 全部拿出来进行排序然后根据 key 去获取 value 。
4.9 为什么Go map是非线程安全的
因为hash map 的内存是按照2的倍数开辟的当前面开辟的内存不够的时候会新开辟一段内存将原来内存的数据转移到新的内存块中这个过程是没有加锁的如果这个时候同时有个读的线程过来获取这块内存数据就会出现安全问题。
4.10 线程安全的map如何实现?
避免map并发读写panic的方式之一就是加锁考虑到读写性能可以使用读写锁提供性能。
4.11 Go sync.map 和原生 map 谁的性能好为什么
在基准测试中在并发安全的情况下sync.Map会比我们常用的map读写锁更加的快快了五倍这是得以于只读read设计减低锁的粒度。但是利用读写锁的话我们存储的不是一个简单数据类型而是一个指针对象那么用普通map读写锁能很好地控制锁的粒度达到更好的操作。
4.12 为什么 Go map 的负载因子是 6.5
源码里定义的阈值的 6.5 (loadFactorNum/loadFactorDen)是经过测试后取出的一个比较合理的因子 因为每个 bucket 有 8 个空位在没有溢出且所有的桶都装满了的情况下装载因子算出来的结果是 8。因此当装载因子超过 6.5 时表明很多 bucket 都快要装满了查找效率和插入效率都变低了。在这个时候进行扩容是有必要的。
