语文建设投稿网站,南昌做网站的公司多不多,地方做什么网站,天元建设集团有限公司第六建筑工程公司1 Slice
Slice底层实现原理
切片是基于数组实现的#xff0c;它的底层是数组#xff0c;它自己本身非常小#xff0c;可以理解为对底层数组的抽象。因为基于数组实现#xff0c;所以它的底层的内存是连续分配的#xff0c;效率非常高#xff0c;还可以通过索引获得数据…1 Slice
Slice底层实现原理
切片是基于数组实现的它的底层是数组它自己本身非常小可以理解为对底层数组的抽象。因为基于数组实现所以它的底层的内存是连续分配的效率非常高还可以通过索引获得数据可以迭代以及垃圾回收优化。 切片本身并不是动态数组或者数组指针。它内部实现的数据结构通过指针引用底层数组设定相关属性将数据读写操作限定在指定的区域内。切片本身是一 个只读对象其工作机制类似数组指针的一种封装。 切片对象非常小是因为它是只有 3 个字段的数据结构
指向底层数组的指针切片的长度切片的容量
Slice扩容机制
在使用 append 向 slice 追加元素时若 slice 空间不足则会发生扩容扩容会重新分配一块更大的内存将原 slice 拷贝到新 slice 然后返回新 slice。扩容后再将数据追加进去。 扩容操作只对容量扩容后的 slice 长度不变容量变化规则如下
若 slice 容量小于1024个元素那么扩容的时候slice的cap就翻番乘以2一旦元素个数超过1024个元素增长因子就变成1.25即每次增加原来容量的四分之一。 若 slice 容量够用则将新元素追加进去slice.len返回原 slice 若 slice 容量不够用将 slice 先扩容扩容得到新 slice将新元素追加进新 sliceslice.len返回新 slice。
Slice与数组区别
array是固定长度的数组使用前必须确定数组长度是值类型。 slice是一个引用类型是一个动态的指向数组切片的指针。 slice是一个不定长的总是指向底层的数组array的数据结构可以动态扩容。 创建方式不一样Slice使用make创建或者根据数组创建。 作为函数参数时数组传递的是数组的副本而slice传递的是指针。
2 Map
Map底层实现原理
Golang 中 map 的底层实现是一个散列表因此实现 map 的过程实际上就是实现散表的过程。在这个散列表中主要出现的结构体有两个一个叫 hmap(a header for a go map)一个叫 bmap(a bucket for a Go map通常叫其 bucket)。 hmap 哈希表 hmap是Go map的底层实现每个hmap内都含有多个bmapbuckets桶、oldbuckets旧桶、overflow溢出桶既每个哈希表都由多个桶组成。
buckets buckets是一个指针指向一个bmap数组存储多个桶。oldbuckets oldbuckets是一个指针指向一个bmap数组存储多个旧桶用于扩容。overflow overflow是一个指针指向一个元素个数为2的数组数组的类型是一个指针指向一个sliceslice的元素是桶(bmap)的地址这些桶都是溢出桶。为什么有两个因为Go map在哈希冲突过多时会发生扩容操作。[0]表示当前使用的溢出桶集合[1]是在发生扩容时保存了旧的溢出桶集合。overflow存在的意义在于防止溢出桶被gc。bmap 哈希桶 bmap是一个隶属于hmap的结构体一个桶bmap可以存储8个键值对。如果有第9个键值对被分配到该桶那就需要再创建一个桶通过overflow指针将两个桶连接起来。在hmap中多个bmap桶通过overflow指针相连组成一个链表。
Map进行有序的排序
map每次遍历,都会从一个随机值序号的桶,再从其中随机的cell开始遍历,并且扩容后,原来桶中的key会落到其他桶中,本身就会造成失序 如果想顺序遍历map,先把key放到切片排序,再按照key的顺序遍历map。 或者可以先把map中的key通过sort包排序再遍历map。
map 为什么是不安全的
Go map 默认是并发不安全的同时对 map 进行并发读写的时程序会 panic原因如下Go 官方经过长时间的讨论认为 map 适配的场景应该是简单的不需要从多个 gorountine 中进行安全访问的而不是为了小部分情况并发访问导致大部分程序付出锁的代价因此决定了不支持。 map 在扩缩容时需要进行数据迁移迁移的过程并没有采用锁机制防止并发操作而是会对某个标识位标记为 1表示此时正在迁移数据。如果有其他 goroutine 对 map 也进行写操作当它检测到标识位为 1 时将会直接 panic。 如果想实现map线程安全有两种方式 方式一使用读写锁 map sync.RWMutex 方式二使用golang提供的 sync.Map
Map扩容策略
扩容时机 向 map 插入新 key 的时候会进行条件检测符合下面这 2 个条件就会触发扩容 扩容条件
超过负载 map元素个数 6.5负载因子 * 桶个数
溢出桶太多
当桶总数2^15时如果溢出桶总数桶总数则认为溢出桶过多 当桶总数215时如果溢出桶总数215则认为溢出桶过多 扩容机制
双倍扩容针对条件1新建一个buckets数组新的buckets大小是原来的2倍然后旧buckets数据搬迁到新的buckets。
等量扩容针对条件2并不扩大容量buckets数量维持不变重新做一遍类似双倍扩容的搬迁动作把松散的键值对重新排列一次使得同一个 bucket 中的 key 排列地更紧密节省空间提高 bucket 利用率进而保证更快的存取。
渐进式扩容 插入修改删除key的时候都会尝试进行搬迁桶的工作每次都会检查oldbucket是否nil如果不是nil则每次搬迁2个桶蚂蚁搬家一样渐进式扩容
Map和Slice区别
数组数组是一个由固定长度的特定类型元素组成的序列一个数组可以由零个或多个元素组成。声明方式var a [3]int slice切片Slice切片代表变长的序列序列中每个元素都有相同的类型slice的语法和数组很像只是没有固定长度而已。 map在Go语言中一个map就是一个哈希表的引用是一个无序的key/value对的集合
Map总结
map是引用类型 map遍历是无序的 map是非线程安全的 map的哈希冲突解决方式是链表法 map的扩容不是一定会新增空间也有可能是只是做了内存整理 map的迁移是逐步进行的在每次赋值时会做至少一次迁移工作 map中删除key有可能导致出现很多空的kv这会导致迁移操作如果可以避免尽量避免
