go语言扩容方法有哪些

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

10年积累的网站设计制作、成都网站设计经验,可以快速应对客户对网站的新想法和需求。提供各种问题对应的解决方案。让选择我们的客户得到更好、更有力的网络服务。我虽然不认识你,你也不认识我。但先做网站设计后付款的网站建设流程,更有望奎免费网站建设让你可以放心的选择与我们合作。

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语言扩容方法有哪些”的学习就结束了,希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习,快去试试吧!若想继续学习更多相关知识,请继续关注创新互联网站,小编会继续努力为大家带来更多实用的文章!


标题名称:go语言扩容方法有哪些
本文来源:http://myzitong.com/article/gcospg.html