日本免费高清视频-国产福利视频导航-黄色在线播放国产-天天操天天操天天操天天操|www.shdianci.com

學無先后，達者為師

網站首頁 編程語言 正文

go語言中slice,map,channl底層原理_Golang

作者：??樹獺叔叔???? ? 更新時間： 2022-07-30 編程語言

0. 前序

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

1. slice

1.1 slice的創建

slice的創建主要有兩種方式，第一種方式是直接創建

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

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

另一種方式是借助array創建：

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

1.2 數據結構

slice底層數據結構如下：

type {
    array unsafe.Pointer // 指針
    len int // 現有長度
    cap int // 容量 
}

在Go語言中，所有的參數傳遞都是值傳遞，slice也是如此，不過由于其底層的指針，在其傳遞到另一個函數后，仍能對其地址對應位置的值做修改，然而，當發生擴容操作時，由于會重新分配地址，就會導致問題的發生，下面我們就來介紹slice的擴容機制。

1.3 擴容機制

在進行append()并且cap不夠用的時候，會觸發擴容操作(copy()操作不會觸發擴容)。

容量的確定:

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

上面所說的是一個容量的初步確定步驟，當數據類型size為1字節，8字節，或者2的倍數時，會根據內存大小進行向上取整，進行內存對齊，之后返回新的擴容大小。

內存對齊的一個重要原因是因為Go進行內存分配時是類似于伙伴系統的固定的內存塊，對齊這個內存可以最大化的人利用分配到的空間。

2. map

2.1 map創建

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

2.2 數據結構

type hmap {
    count int
    flags uint8 // map當前是否處于寫入狀態等
    B     uint8 // 2的B次冪表示當前map中桶的數量（buckets的長度）
    noverlow uint16 // map中溢出桶的數量，當溢出桶太多時，map會進行等量擴容
    hash0 uint32 //生成hash的隨機數種子
    
    buckets unsafe.Pointer //當前map對應的桶的指針
    oldbuckets unsafe.Pointer // 擴容時的舊桶
    nevacuate uintptr //擴容時，用于標記當前舊桶中小于nevacute的數據都已經轉移到了新桶
    
    extra *mapextra //存儲map的溢出桶
}

Go中的map的數據都是存在bmap的數據結構中的，最多放8個kv對，溢出桶的設計與GC有關系，如果map為內聯數據類型時，map數據結構里的指針就只有溢出桶了，這個時候就可以避免遍歷map。

2.3 擴容機制

當我們插入一個k-v對時，需要確定他應該插入到bucket數組的哪一個槽中。bucket數組的長度為2^B，即2的次冪數，而2^B-1轉換成二進制后一定是低位全1，高位全0的形式，因此在進行按位與操作后，一定能求得一個在[0,2^B-1]區間上的任意一個數，也就是數組中的下標位置，相較之下，能獲得比取模更加優秀的執行效率。

涉及到擴容，每一次bucket數組都會變為現在的兩倍，方便我們進行hash遷移。

map觸發擴容的條件有兩種：

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

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

3. channl

3.1 數據結構

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的入隊與出隊操作都是都是加鎖的，以此來保證并發安全。當隊列滿了再插入數據時，插入線程g會進入wait狀態并且掛在sendq隊列上，等取出元素時會將其喚醒，空隊取元素同理。

原文鏈接：https://juejin.cn/post/7104301676714000391

欄目分類
最近更新