登录
首页 >  Golang >  Go教程

go语言扩容方法有哪些

来源:亿速云

时间:2023-03-02 09:50:58 149浏览 收藏

golang学习网今天将给大家带来《go语言扩容方法有哪些》,感兴趣的朋友请继续看下去吧!以下内容将会涉及到go语言等等知识点,如果你是正在学习Golang或者已经是大佬级别了,都非常欢迎也希望大家都能给我建议评论哈~希望能帮助到大家!

这篇文章主要介绍“go语言扩容方法有哪些”,在日常操作中,相信很多人在go语言扩容方法有哪些问题上存在疑惑,小编查阅了各式资料,整理出简单好用的操作方法,希望对大家解答”go语言扩容方法有哪些”的疑惑有所帮助!接下来,请跟着小编一起来学习吧!

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

Slice扩容

触发

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

原理

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

机制

V1.8之前:

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

  • 如果原Slice容量小于1024,则新Slice容量将扩大为原来的2倍;

  • 如果原Slice容量大于等于1024,则新Slice容量将扩大为原来的1.25倍;

// 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之后:

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

  • 如果原Slice容量小于256,则新Slice容量将扩大为原来的2倍;

  • 如果原Slice容量大于等于256,则新Slice容量将扩大为原来的  新容量 = (原容量+3*256)/4

// 只关心扩容规则的简化版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扩容

触发扩容的条件有二个:

  • 负载因子 > 6.5时,也即平均每个bucket存储的键值对达到6.5个。增量扩容

  • overflow数量 > 2^15时,也即overflow数量超过32768时。等量扩容/重排

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

增量扩容

  • 当负载因子过大时,新开辟buckets空间,bucket数量为之前的 2 倍

  • 新空间被buckets引用,之前的旧空间被oldbuckets引用

  • 之后逐渐将 oldbuckets中的数据 搬迁到 新开辟的 buckets空间中去

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

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

go语言扩容方法有哪些

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

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

go语言扩容方法有哪些

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

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

go语言扩容方法有哪些

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

等量扩容/重排

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

go语言扩容方法有哪些

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

到此,关于“go语言扩容方法有哪些”的学习就结束了,希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习,快去试试吧!若想继续学习更多相关知识,请继续关注golang学习网,小编会继续努力为大家带来更多实用的文章!

理论要掌握,实操不能落!以上关于《go语言扩容方法有哪些》的详细介绍,大家都掌握了吧!如果想要继续提升自己的能力,那么就来关注golang学习网公众号吧!

声明:本文转载于:亿速云 如有侵犯,请联系study_golang@163.com删除
相关阅读
更多>
最新阅读
更多>
课程推荐
更多>
评论列表