• 技术文章 >后端开发 >Golang

    go语言扩容方法有哪几种

    青灯夜游青灯夜游2023-01-16 16:11:58原创47

    go语言扩容方法有:1、Slice扩容,在使用append向Slice追加元素时,如果Slice空间不足,将会触发Slice扩容;2、Map扩容。触发Map扩容的条件有二个:1、负载因子大于6.5时,也即平均每个bucket存储的键值对达到6.5个;2、overflow数量大于2^15时,也即overflow数量超过32768时。

    本教程操作环境:windows7系统、GO 1.18版本、Dell G3电脑。

    Slice扩容

    触发

    使用append向Slice追加元素时,如果Slice空间不足,将会触发Slice扩容

    原理

    扩容实际上是重新分配一块更大的内存,将原Slice数据拷贝进新Slice,然后返回新Slice,扩容后再将数据追加进去。

    机制

    V1.8之前:

    扩容容量的选择遵循以下规则:

    // 1.17及以前的版本中
    // old指切片的旧容量, cap指期望的新容量
    func growslice(old, cap int) int {
        newcap := old
        doublecap := newcap + newcap
        // 如果期望容量大于旧容量的2倍,则直接使用期望容量作为最终容量
        if cap > doublecap {
            newcap = cap
        } else {
            // 如果旧容量小于1024,则直接翻倍
            if old < 1024 {
                newcap = doublecap
            } else {
                // 每次增长大约1.25倍
                for 0 < newcap && newcap < cap {
                    newcap += newcap / 4
                }
                if newcap <= 0 {
                    newcap = cap
                }
            }
        }
        // 这里忽略了对齐操作
        return newcap
    }

    V1.8之后:

    新扩容容量的选择遵循以下规则:(拥有更平滑的扩容系数)

    // 只关心扩容规则的简化版growslice
    func growslice(old, cap int) int {
        newcap := old
        doublecap := newcap + newcap
        if cap > doublecap {
            newcap = cap
        } else {
            const threshold = 256 // 不同点1
            if old < threshold {
                newcap = doublecap
            } else {
                for 0 < newcap && newcap < cap {
                    newcap += (newcap + 3*threshold) / 4 // 不同点2
                }
                if newcap <= 0 {
                    newcap = cap
                }
            }
        }
        return newcap
    }

    Map扩容

    触发扩容的条件有二个:

    注意:创建溢出桶不属于扩容机制

    增量扩容

    考虑到如果map存储了数以亿计的key-value,一次性搬迁将会造成比较大的延时,Go采用逐步搬迁策略,即每次访问map时都会触发一次搬迁,每次搬迁2个键值对当oldbuckets中的键值对全部搬迁完毕后,删除oldbuckets。

    下图展示了包含一个bucket满载的map(为了描述方便,图中bucket省略了value区域):

    当前map存储了7个键值对,只有1个bucket。此时负载因子为7 > 6.5。再次插入数据时将会触发扩容操作,扩容之后再将新插入键写入新的bucket。注意,因为负载因子的触发,不是创建溢出桶

    当第8个键值对插入时,将会触发扩容扩容后示意图如下:

    后续对map的访问操作会触发迁移,将oldbuckets中的键值对逐步的搬迁过来。

    搬迁完成后的示意图如下:

    数据搬迁过程中原bucket中的键值对将存在于新bucket的前面,新插入的键值对将存在于新bucket的后面。

    等量扩容/重排

    所谓等量扩容,实际上并不是扩大容量,buckets数量不变,重新做一遍类似增量扩容的搬迁动作,把松散的键值对重新排列一次,以使bucket的使用率更高,进而保证更快的存取。
    在极端场景下,比如不断地增删,而键值对正好集中在一小部分的bucket,这样会造成overflow的bucket数量增多,但负载因子又不高,从而无法执行增量搬迁的情况,如下图所示:

    上图可见,overflow的bucket中大部分是空的,访问效率会很差。此时进行一次等量扩容,即buckets数量不变,经过重新组织后overflow的bucket数量会减少,即节省了空间又会提高访问效率。

    【相关推荐:Go视频教程编程教学

    以上就是go语言扩容方法有哪几种的详细内容,更多请关注php中文网其它相关文章!

    声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn核实处理。
    专题推荐:Golang go语言
    上一篇:go语言中join方法有什么用 下一篇:自己动手写 PHP MVC 框架(40节精讲/巨细/新人进阶必看)

    相关文章推荐

    • go语言怎么比较字符串• golang怎么添加list元素• golang循环遍历map的方式有几种• go语言怎么获取map元素• go语言中list怎么删除元素• go语言变量有几种作用域
    1/1

    PHP中文网