0. 前序

slice,map,channl是我們Go語言中最最常用的幾個(gè)數(shù)據(jù)結(jié)構(gòu)，對(duì)于這些做到知根知底，對(duì)于我們建立知識(shí)體系以及優(yōu)化代碼都有著很重要的意義，所以本文，我們深入這三個(gè)數(shù)據(jù)結(jié)構(gòu)的底層，剖析其設(shè)計(jì)思想。

1. slice

1.1 slice的創(chuàng)建

slice的創(chuàng)建主要有兩種方式，第一種方式是直接創(chuàng)建

var sli []int
sli = make([]int, len, cap) // cap可以省略

//或者
sli := make([]int, len, cap) // cap可以省略

另一種方式是借助array創(chuàng)建：

arr := []int{1,2,3,4,5}
sli := arr[sta:end:cap] // :cap可以省略，以這種方式創(chuàng)建的sli，其cap為sta到arr的最后一位

1.2 數(shù)據(jù)結(jié)構(gòu)

slice底層數(shù)據(jù)結(jié)構(gòu)如下：

type {
    array unsafe.Pointer // 指針
    len int // 現(xiàn)有長(zhǎng)度
    cap int // 容量 
}

在Go語言中，所有的參數(shù)傳遞都是值傳遞，slice也是如此，不過由于其底層的指針，在其傳遞到另一個(gè)函數(shù)后，仍能對(duì)其地址對(duì)應(yīng)位置的值做修改，然而，當(dāng)發(fā)生擴(kuò)容操作時(shí)，由于會(huì)重新分配地址，就會(huì)導(dǎo)致問題的發(fā)生，下面我們就來介紹slice的擴(kuò)容機(jī)制。

1.3 擴(kuò)容機(jī)制

在進(jìn)行append()并且cap不夠用的時(shí)候，會(huì)觸發(fā)擴(kuò)容操作(copy()操作不會(huì)觸發(fā)擴(kuò)容)。

容量的確定:

• 如果期望容量大于當(dāng)前容量的兩倍就會(huì)使用期望容量；
• 如果當(dāng)前切片的長(zhǎng)度小于 1024 就會(huì)將容量翻倍；
• 如果當(dāng)前切片的長(zhǎng)度大于 1024 就會(huì)每次增加 25% 的容量，直到新容量大于期望容量；

上面所說的是一個(gè)容量的初步確定步驟，當(dāng)數(shù)據(jù)類型size為1字節(jié)，8字節(jié)，或者2的倍數(shù)時(shí)，會(huì)根據(jù)內(nèi)存大小進(jìn)行向上取整，進(jìn)行內(nèi)存對(duì)齊，之后返回新的擴(kuò)容大小。

內(nèi)存對(duì)齊的一個(gè)重要原因是因?yàn)镚o進(jìn)行內(nèi)存分配時(shí)是類似于伙伴系統(tǒng)的固定的內(nèi)存塊，對(duì)齊這個(gè)內(nèi)存可以最大化的人利用分配到的空間。

2. map

2.1 map創(chuàng)建

m = make(map[int]int) // 需要注意 make(map)返回的是一個(gè)指針 

2.2 數(shù)據(jù)結(jié)構(gòu)

type hmap {
    count int
    flags uint8 // map當(dāng)前是否處于寫入狀態(tài)等
    B     uint8 // 2的B次冪表示當(dāng)前map中桶的數(shù)量（buckets的長(zhǎng)度）
    noverlow uint16 // map中溢出桶的數(shù)量，當(dāng)溢出桶太多時(shí)，map會(huì)進(jìn)行等量擴(kuò)容
    hash0 uint32 //生成hash的隨機(jī)數(shù)種子
    
    buckets unsafe.Pointer //當(dāng)前map對(duì)應(yīng)的桶的指針
    oldbuckets unsafe.Pointer // 擴(kuò)容時(shí)的舊桶
    nevacuate uintptr //擴(kuò)容時(shí)，用于標(biāo)記當(dāng)前舊桶中小于nevacute的數(shù)據(jù)都已經(jīng)轉(zhuǎn)移到了新桶
    
    extra *mapextra //存儲(chǔ)map的溢出桶
}

Go中的map的數(shù)據(jù)都是存在bmap的數(shù)據(jù)結(jié)構(gòu)中的，最多放8個(gè)kv對(duì)，溢出桶的設(shè)計(jì)與GC有關(guān)系，如果map為內(nèi)聯(lián)數(shù)據(jù)類型時(shí)，map數(shù)據(jù)結(jié)構(gòu)里的指針就只有溢出桶了，這個(gè)時(shí)候就可以避免遍歷map。

2.3 擴(kuò)容機(jī)制

當(dāng)我們插入一個(gè)k-v對(duì)時(shí)，需要確定他應(yīng)該插入到bucket數(shù)組的哪一個(gè)槽中。bucket數(shù)組的長(zhǎng)度為2^B，即2的次冪數(shù)，而2^B-1轉(zhuǎn)換成二進(jìn)制后一定是低位全1，高位全0的形式，因此在進(jìn)行按位與操作后，一定能求得一個(gè)在[0,2^B-1]區(qū)間上的任意一個(gè)數(shù)，也就是數(shù)組中的下標(biāo)位置，相較之下，能獲得比取模更加優(yōu)秀的執(zhí)行效率。

涉及到擴(kuò)容，每一次bucket數(shù)組都會(huì)變?yōu)楝F(xiàn)在的兩倍，方便我們進(jìn)行hash遷移。

map觸發(fā)擴(kuò)容的條件有兩種：

• 負(fù)載因子大于6.5時(shí)（負(fù)載因子 = 鍵數(shù)量 / bucket數(shù)量）
• overflow的數(shù)量達(dá)到2^min(15,B)

等量擴(kuò)容 所謂等量擴(kuò)容，并不是擴(kuò)大容量，而是bucket數(shù)量不變，重新做一遍類似增量擴(kuò)容的搬遷動(dòng)作，把松散的鍵值對(duì)重新排列一次，以使bucket的使用率更高，從而保證更快的存取速度。

3. channl

3.1 數(shù)據(jù)結(jié)構(gòu)

type hchan struct {
    qcount   uint           // total data in the queue
    dataqsiz uint           // size of the circular queue
    buf      unsafe.Pointer // points to an array of dataqsiz elements
    elemsize uint16
    closed   uint32
    elemtype *_type // element type
    sendx    uint   // send index
    recvx    uint   // receive index
    recvq    waitq  // list of recv waiters
    sendq    waitq  // list of send waiters

    // lock protects all fields in hchan, as well as several
    // fields in sudogs blocked on this channel.
    //
    // Do not change another G's status while holding this lock
    // (in particular, do not ready a G), as this can deadlock
    // with stack shrinking.
    lock mutex
}

3.2 過程詳解

channl的入隊(duì)與出隊(duì)操作都是都是加鎖的，以此來保證并發(fā)安全。當(dāng)隊(duì)列滿了再插入數(shù)據(jù)時(shí)，插入線程g會(huì)進(jìn)入wait狀態(tài)并且掛在sendq隊(duì)列上，等取出元素時(shí)會(huì)將其喚醒，空隊(duì)取元素同理。

到此這篇關(guān)于go語言中slice,map,channl底層原理的文章就介紹到這了,更多相關(guān)go slice,map,channl 內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論