作者：jackshi，騰訊 PCG 后臺(tái)開發(fā)工程師

從C++切換到Go語(yǔ)言一年多了，有必要深入了解一下Go語(yǔ)言內(nèi)置數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)原理，本文結(jié)合示例與Go源碼深入到Go語(yǔ)言的底層實(shí)現(xiàn)。

數(shù)組

定義

數(shù)組是切片和映射的基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)。

數(shù)組是一個(gè)長(zhǎng)度固定的數(shù)據(jù)類型，用于存儲(chǔ)一段具有相同類型元素的連續(xù)塊。

聲明與初始化

var arr [5]int //聲明一個(gè)包含五個(gè)元素的數(shù)組arr := [5]int{1, 2, 3, 4, 5} //字面量聲明arr := [...]int{1, 2, 3, 4, 5} //編譯期自動(dòng)推導(dǎo)數(shù)組長(zhǎng)度arr := [5]int{1:10,3:30} //初始化索引為1和3的元素，其他默認(rèn)值為0

數(shù)組的使用

arr := [5]int{10, 20, 30, 40, 50}arr[2] = 35 //修改索引為2的元素的值var arr1 [3]stringarr2 := [3]string{"red", "yellow", "green"}arr1 = arr2 //數(shù)組拷貝(深拷貝)var arr3 [4]stringarr3 = arr2 //error 數(shù)組個(gè)數(shù)不同var arr [4][2]int //多維數(shù)組arr[1][0] = 20arr[0] = [2]int{1, 2}

函數(shù)間傳遞數(shù)組

var arr [1e6]intfunc foo1(arr [1e6]int) { //每次拷貝整個(gè)數(shù)組 ...}func foo2(arr *[1e6]int) { //傳遞指針，效率更高 ...}

切片

切片是一種數(shù)據(jù)結(jié)構(gòu)，便于使用和管理數(shù)據(jù)集合。切片是圍繞動(dòng)態(tài)數(shù)組的概念構(gòu)建的，可以按需自動(dòng)增長(zhǎng)和縮小。

內(nèi)部實(shí)現(xiàn)

type SliceHeader struct { Data uintptr Len int Cap int}

編譯期間的切片是 Slice 類型的，但是在運(yùn)行時(shí)切片由 SliceHeader結(jié)構(gòu)體表示，其中Data 字段是指向數(shù)組的指針，Len表示當(dāng)前切片的長(zhǎng)度，而 Cap表示當(dāng)前切片的容量，也就是Data數(shù)組的大小。

創(chuàng)建和初始化

slice := make([]string, 5) //創(chuàng)建一個(gè)字符串切片，長(zhǎng)度和容量都是5個(gè)元素slice := make([]int, 3, 5) //創(chuàng)建一個(gè)整型切片，長(zhǎng)度為3個(gè)元素，容量為5個(gè)元素slice := make([]string, 5, 3) //error 容量需要小于長(zhǎng)度slice := []string{"Red", "Yellow", "Green"} //使用字面量聲明var slice []int //創(chuàng)建nil整型切片slice := make([]int, 0) //使用make創(chuàng)建空的整型切片slice := []int{} //使用切片字面量創(chuàng)建空的整型切片不管是使用nil切片還是空切片，對(duì)其調(diào)用內(nèi)置函數(shù)append、len、cap效果都一樣，盡量使用len函數(shù)來(lái)判斷切片是否為空

賦值和切片

slice := []int{1, 2, 3, 4, 5} //創(chuàng)建一個(gè)整型切片，長(zhǎng)度和容量都是5slice[2] = 30 //修改索引為2的元素的值，slice當(dāng)前結(jié)果為{1, 2, 30, 4, 5}newSlice := slice[1:3] //創(chuàng)建一個(gè)新切片，長(zhǎng)度為2個(gè)元素，容量為4個(gè)元素對(duì)底層數(shù)組容量是k的切片slice[i:j]來(lái)說(shuō)：長(zhǎng)度：j - i容量：k - inewSlice[0] = 20 //由于newSlice與slice底層共享一個(gè)數(shù)組，因此slice當(dāng)前結(jié)果為{1, 20, 30, 4, 5}newSlice[3] = 40 //error 雖然容量足夠，但超過長(zhǎng)度限制，會(huì)觸發(fā)panic

切片增長(zhǎng)

slice := []int{1, 2, 3, 4, 5}newSlice := slice[1:3] //cap(newSlice) : 4 newSlice = append(newSlice, 60) // slice當(dāng)前結(jié)果為{1, 2, 3, 60, 5} //newSlice的append操作影響了slice的結(jié)果，可以嘗試 newSlice := slice[1:3:3]再看看結(jié)果newSlice = append(newSlice, []int{70, 80}...) //slice當(dāng)前結(jié)果仍為{1, 2, 3, 60, 5} len(newSlice) : 5 cap(newSlice) : 8func growslice(et *_type, old slice, cap int) slice { ... newcap := old.cap doublecap := newcap + newcap if cap > doublecap { newcap = cap } else { if old.cap < 1024 { newcap = doublecap } else { for 0 < newcap && newcap < cap { newcap += newcap / 4 } if newcap <= 0 { newcap = cap } } } ...}

在分配內(nèi)存空間之前需要先確定新的切片容量，Go 語(yǔ)言根據(jù)切片的當(dāng)前容量選擇不同的策略進(jìn)行擴(kuò)容：

如果期望容量大于當(dāng)前容量的兩倍就會(huì)使用期望容量； 如果當(dāng)前切片的長(zhǎng)度小于 1024 就會(huì)將容量翻倍； 如果當(dāng)前切片的長(zhǎng)度大于 1024 就會(huì)每次增加 25% 的容量，直到新容量大于期望容量； 這里只是確定切片的大致容量，接下來(lái)還需要根據(jù)切片中元素的大小對(duì)它們進(jìn)行對(duì)齊，當(dāng)數(shù)組中元素所占的字節(jié)大小為 1、8 或者 2 的倍數(shù)時(shí)，運(yùn)行時(shí)會(huì)使用如下所示的代碼對(duì)其內(nèi)存

func growslice(et *_type, old slice, cap int) slice { ... var overflow bool var lenmem, newlenmem, capmem uintptr switch { case et.size == 1: lenmem = uintptr(old.len) newlenmem = uintptr(cap) capmem = roundupsize(uintptr(newcap)) overflow = uintptr(newcap) > maxAlloc newcap = int(capmem) case et.size == sys.PtrSize: lenmem = uintptr(old.len) * sys.PtrSize newlenmem = uintptr(cap) * sys.PtrSize capmem = roundupsize(uintptr(newcap) * sys.PtrSize) overflow = uintptr(newcap) > maxAlloc/sys.PtrSize newcap = int(capmem / sys.PtrSize) case isPowerOfTwo(et.size): var shift uintptr if sys.PtrSize == 8 { // Mask shift for better code generation. shift = uintptr(sys.Ctz64(uint64(et.size))) & 63 } else { shift = uintptr(sys.Ctz32(uint32(et.size))) & 31 } lenmem = uintptr(old.len) << shift newlenmem = uintptr(cap) << shift capmem = roundupsize(uintptr(newcap) << shift) overflow = uintptr(newcap) > (maxAlloc >> shift) newcap = int(capmem >> shift) default: lenmem = uintptr(old.len) * et.size newlenmem = uintptr(cap) * et.size capmem, overflow = math.MulUintptr(et.size, uintptr(newcap)) capmem = roundupsize(capmem) newcap = int(capmem / et.size) } ...}

runtime.roundupsize函數(shù)會(huì)將待申請(qǐng)的內(nèi)存向上取整，取整時(shí)會(huì)使用內(nèi)存分配中介紹的runtime.class_to_size數(shù)組，使用該數(shù)組中的整數(shù)可以提高內(nèi)存的分配效率并減少碎片。

func growslice(et *_type, old slice, cap int) slice { ... if overflow || capmem > maxAlloc { panic(errorString("growslice: cap out of range")) } var p unsafe.Pointer if et.ptrdata == 0 { p = mallocgc(capmem, nil, false) memclrNoHeapPointers(add(p, newlenmem), capmem-newlenmem) } else { p = mallocgc(capmem, et, true) if lenmem > 0 && writeBarrier.enabled { bulkBarrierPreWriteSrcOnly(uintptr(p), uintptr(old.array), lenmem-et.size+et.ptrdata) } } memmove(p, old.array, lenmem) return slice{p, old.len, newcap}}

如果切片中元素不是指針類型，那么就會(huì)調(diào)用memclrNoHeapPointers將超出切片當(dāng)前長(zhǎng)度的位置清空并在最后使用memmove將原數(shù)組內(nèi)存中的內(nèi)容拷貝到新申請(qǐng)的內(nèi)存中。

runtime.growslice函數(shù)最終會(huì)返回一個(gè)新的 slice 結(jié)構(gòu)，其中包含了新的數(shù)組指針、大小和容量，這個(gè)返回的三元組最終會(huì)改變?cè)械那衅?#xff0c;幫助 append 完成元素追加的功能。

示例：

var arr []int64arr = append(arr, 1, 2, 3, 4, 5)fmt.Println(cap(arr))

當(dāng)我們執(zhí)行如上所示的代碼時(shí)，會(huì)觸發(fā) runtime.growslice 函數(shù)擴(kuò)容 arr 切片并傳入期望的新容量 5，這時(shí)期望分配的內(nèi)存大小為 40 字節(jié)；不過因?yàn)榍衅械脑卮笮〉扔?sys.PtrSize，所以運(yùn)行時(shí)會(huì)調(diào)用 runtime.roundupsize 對(duì)內(nèi)存的大小向上取整 48 字節(jié)，所以經(jīng)過計(jì)算新切片的容量為 48 / 8 = 6 。

拷貝切片

切片的拷貝雖然不是一個(gè)常見的操作類型，但是卻是我們學(xué)習(xí)切片實(shí)現(xiàn)原理必須要談及的一個(gè)問題，當(dāng)我們使用 copy(a, b) 的形式對(duì)切片進(jìn)行拷貝時(shí)，編譯期間的 cmd/compile/internal/gc.copyany 函數(shù)也會(huì)分兩種情況進(jìn)行處理，如果當(dāng)前 copy 不是在運(yùn)行時(shí)調(diào)用的，copy(a, b) 會(huì)被直接轉(zhuǎn)換成下面的代碼：

n := len(a)if n > len(b) { n = len(b)}if a.ptr != b.ptr { memmove(a.ptr, b.ptr, n*sizeof(elem(a))) }

其中 memmove 會(huì)負(fù)責(zé)對(duì)內(nèi)存進(jìn)行拷貝，在其他情況下，編譯器會(huì)使用 runtime.slicecopy 函數(shù)替換運(yùn)行期間調(diào)用的 copy，例如：go copy(a, b)：

func slicecopy(to, fm slice, width uintptr) int { if fm.len == 0 || to.len == 0 { return 0 } n := fm.len if to.len < n { n = to.len } if width == 0 { return n } ... size := uintptr(n) * width if size == 1 { *(*byte)(to.array) = *(*byte)(fm.array) } else { memmove(to.array, fm.array, size) } return n}

上述函數(shù)的實(shí)現(xiàn)非常直接，兩種不同的拷貝方式一般都會(huì)通過 memmove將整塊內(nèi)存中的內(nèi)容拷貝到目標(biāo)的內(nèi)存區(qū)域中。

迭代切片

slice := []int{1, 2, 3, 4, 5}for index, value := range slice { value += 10 fmt.Printf("index:%d value:%d", index, value)}fmt.Println(slice) // {1, 2, 3, 4, 5}==var value intfor index := 0; index < len(slice); index ++ { value = slice[index] }

函數(shù)間傳遞切片

slice := make([]int, 1e6)slice = foo(slice)func foo(slice []int) []int { ... return slice}

在64位架構(gòu)的機(jī)器上，一個(gè)切片需要24字節(jié)內(nèi)存，數(shù)組指針、長(zhǎng)度、容量分別占用8字節(jié)，在函數(shù)間傳遞24字節(jié)數(shù)據(jù)會(huì)非常快速簡(jiǎn)單，這也是切片效率高的原因。

映射

映射是一種數(shù)據(jù)結(jié)構(gòu)，用于存儲(chǔ)一系列無(wú)序的鍵值對(duì)。

映射是一個(gè)集合，可以使用類似處理數(shù)組和切片的方式迭代，但映射是無(wú)序的集合，每次迭代映射的時(shí)候順序也可能不一樣。

創(chuàng)建和初始化

dict := make(map[string]int) dict := map[string]string{"Red":"#da1337", "Orange":"#e95a22"} //字面量方式

使用映射

colors := make(map[string]string) //創(chuàng)建一個(gè)空映射colors["Red"] = "#da1337" //賦值var colors map[string]stringcolors["Red"] = "#da1337" //errorvalue, ok := colors["Blue"] //判斷鍵是否存在if ok { fmt.Println(value)}value := colors["Blue"] //判斷讀取到的值是否空值if value != "" { fmt.Println(value)}

函數(shù)間傳遞映射

func removeColor(colors map[string]string, key string) { delete(colors, key)}func main(){ colors := map[string]string{ "AliceBlue" : "#f0f8ff", "Coral" : "#ff7F50", } for key, value := range colors { fmt.Printf("Key: %s Value: %s", key, value) } removeColor(colors, "Coral") for key, value := range colors { fmt.Printf("Key: %s Value: %s", key, value) }}

內(nèi)存模型

Go語(yǔ)言采用的是哈希查找表，并且使用鏈表解決哈希沖突。

// hashmap的簡(jiǎn)稱type hmap struct { count int //元素個(gè)數(shù) flags uint8 //標(biāo)記位 B uint8 //buckets的對(duì)數(shù) log_2 noverflow uint16 //overflow的bucket的近似數(shù) hash0 uint32 //hash種子 buckets unsafe.Pointer //指向buckets數(shù)組的指針，數(shù)組個(gè)數(shù)為2^B oldbuckets unsafe.Pointer //擴(kuò)容時(shí)使用，buckets長(zhǎng)度是oldbuckets的兩倍 nevacuate uintptr //擴(kuò)容進(jìn)度，小于此地址的buckets已經(jīng)遷移完成 extra *mapextra //擴(kuò)展信息}//當(dāng)map的key和value都不是指針，并且size都小于128字節(jié)的情況下，會(huì)把 bmap 標(biāo)記為不含指針，這樣可以避免gc時(shí)掃描整個(gè)hmap。但是，我們看bmap其實(shí)有一個(gè)overflow的字段，是指針類型的，破壞了bmap不含指針的設(shè)想，這時(shí)會(huì)把overflow移動(dòng)到extra字段來(lái)。type mapextra struct { overflow *[]*bmap oldoverflow *[]*bmap nextOverflow *bmap}// buckettype bmap struct { tophash [bucketCnt]uint8 //bucketCnt = 8 // keys [8]keytype // values [8]valuetype // pad uintptr // overflow uintptr}

bmap就是桶的數(shù)據(jù)結(jié)構(gòu)，每個(gè)桶最多存儲(chǔ)8個(gè)key-value對(duì)，所有的key都是經(jīng)過hash后有相同的尾部，在桶內(nèi)，根據(jù)hash值的高8位來(lái)決定桶中的位置。

注意到key和value是各自在一起的，不是key/value/key/value/...的方式，這樣的好處是某些情況下可以省略padding字段，節(jié)省內(nèi)存空間

如map[int64]int8，按照key/value/key/value/... 這樣的模式存儲(chǔ)，每一個(gè)key/value對(duì)之后都要額外 padding7個(gè)字節(jié)；而將所有的key，value 分別綁定到一起，key/key/.../value/value/...，只需在最后添加padding。

每個(gè)bucket設(shè)計(jì)成最多只能放8個(gè)key-value對(duì)，如果有第9個(gè) key-value落入當(dāng)前的bucket，那就需要再構(gòu)建一個(gè)bucket，通過overflow指針連接起來(lái)。

map的擴(kuò)容

裝載因子：loadFactor := count / (2^B) count是map中元素的個(gè)數(shù)，2^B表示bucket數(shù)量

符合下面兩個(gè)條件會(huì)觸發(fā)擴(kuò)容： 1)裝載因子超過閾值：源碼里定義的閾值為6.5 2)overflow的bucket數(shù)量過多：當(dāng)B>15時(shí)，overflow的bucket數(shù)量超過2^15^，否則超過2^B^

增加桶搬遷示例：

const ( bucketCntBits = 3 bucketCnt = 1 << bucketCntBits loadFactorNum = 13 loadFactorDen = 2)func bucketShift(b uint8) uintptr { return uintptr(1) << (b & (sys.PtrSize*8 - 1))}func overLoadFactor(count int, B uint8) bool { return count > bucketCnt && uintptr(count) > loadFactorNum*(bucketShift(B)/loadFactorDen)}func tooManyOverflowBuckets(noverflow uint16, B uint8) bool { if B > 15 { B = 15 } return noverflow >= uint16(1)< newbit { stop = newbit } for h.nevacuate != stop && bucketEvacuated(t, h, h.nevacuate) { h.nevacuate++ } if h.nevacuate == newbit { // newbit == # of oldbuckets // 搬遷完成，釋放舊的桶數(shù)據(jù) h.oldbuckets = nil if h.extra != nil { h.extra.oldoverflow = nil } h.flags &^= sameSizeGrow }}

map的創(chuàng)建

//注：go:nosplit該指令指定文件中聲明的下一個(gè)函數(shù)不得包含堆棧溢出檢查。簡(jiǎn)單來(lái)講，就是這個(gè)函數(shù)跳過堆棧溢出的檢查//go:nosplit 快速得到隨機(jī)數(shù) 參考論文：https://www.jstatsoft.org/article/view/v008i14/xorshift.pdffunc fastrand() uint32 { mp := getg().m s1, s0 := mp.fastrand[0], mp.fastrand[1] s1 ^= s1 << 17 s1 = s1 ^ s0 ^ s1>>7 ^ s0>>16 mp.fastrand[0], mp.fastrand[1] = s0, s1 return s0 + s1}func makemap(t *maptype, hint int, h *hmap) *hmap { mem, overflow := math.MulUintptr(uintptr(hint), t.bucket.size) if overflow || mem > maxAlloc { hint = 0 } // 初始化 if h == nil { h = new(hmap) } h.hash0 = fastrand() // 計(jì)算合適的桶個(gè)數(shù)B B := uint8(0) for overLoadFactor(hint, B) { B++ } h.B = B // 分配哈希表 if h.B != 0 { var nextOverflow *bmap h.buckets, nextOverflow = makeBucketArray(t, h.B, nil) if nextOverflow != nil { h.extra = new(mapextra) h.extra.nextOverflow = nextOverflow } } return h}// makeBucketArray initializes a backing array for map buckets.func makeBucketArray(t *maptype, b uint8, dirtyalloc unsafe.Pointer) ( buckets unsafe.Pointer, nextOverflow *bmap) { base := bucketShift(b) nbuckets := base // 對(duì)于比較小的b，不額外申請(qǐng)過載空間 if b >= 4 { nbuckets += bucketShift(b - 4) sz := t.bucket.size * nbuckets up := roundupsize(sz) if up != sz { nbuckets = up / t.bucket.size } } if dirtyalloc == nil { buckets = newarray(t.bucket, int(nbuckets)) } else { buckets = dirtyalloc size := t.bucket.size * nbuckets if t.bucket.ptrdata != 0 { memclrHasPointers(buckets, size) } else { memclrNoHeapPointers(buckets, size) } } if base != nbuckets { nextOverflow = (*bmap)(add(buckets, base*uintptr(t.bucketsize))) last := (*bmap)(add(buckets, (nbuckets-1)*uintptr(t.bucketsize))) last.setoverflow(t, (*bmap)(buckets)) } return buckets, nextOverflow}

key的定位

key經(jīng)過hash后得到一個(gè)64位整數(shù)，使用最后B位判斷該key落入到哪個(gè)桶中，如果桶相同，說(shuō)明有hash碰撞，在該桶中遍歷尋找，采用hash值的高8位來(lái)快速比較，來(lái)看一個(gè)示例：

再來(lái)看一下源碼：

const ( emptyRest = 0 // this cell is empty, and there are no more non-empty cells at higher indexes or overflows. emptyOne = 1 // this cell is empty evacuatedX = 2 // key/elem is valid. Entry has been evacuated to first half of larger table. evacuatedY = 3 // same as above, but evacuated to second half of larger table. evacuatedEmpty = 4 // cell is empty, bucket is evacuated. minTopHash = 5 // minimum tophash for a normal filled cell)//計(jì)算hash值的高8位func tophash(hash uintptr) uint8 { top := uint8(hash >> (sys.PtrSize*8 - 8)) if top < minTopHash { top += minTopHash } return top}//p指針偏移x位func add(p unsafe.Pointer, x uintptr) unsafe.Pointer { return unsafe.Pointer(uintptr(p) + x)}const PtrSize = 4 << (^uintptr(0) >> 63) // 64位環(huán)境下是 8//獲取下一個(gè)桶節(jié)點(diǎn)func (b *bmap) overflow(t *maptype) *bmap { return *(**bmap)(add(unsafe.Pointer(b), uintptr(t.bucketsize)-sys.PtrSize))}//判斷是否搬遷完成func evacuated(b *bmap) bool { h := b.tophash[0] return h > emptyOne && h < minTopHash}func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer{}func mapaccess2(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, bool){}func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer { // ...... //h為空或數(shù)量為0返回空值 if h == nil || h.count == 0 { if t.hashMightPanic() { t.hasher(key, 0) // see issue https://github.com/golang/go/issues/23734 } return unsafe.Pointer(&zeroVal[0]) } //讀寫沖突 if h.flags&hashWriting != 0 { throw("concurrent map read and map write") } //對(duì)請(qǐng)求key計(jì)算hash值 hash := t.hasher(key, uintptr(h.hash0)) //獲取桶的掩碼，如B=5,m=31即二進(jìn)制(11111) m := bucketMask(h.B) //定位到對(duì)應(yīng)的桶 b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize))) //判斷是否處于擴(kuò)容中 if c := h.oldbuckets; c != nil { if !h.sameSizeGrow() { // There used to be half as many buckets; mask down one more power of two. m >>= 1 } oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize))) if !evacuated(oldb) { b = oldb } } //計(jì)算hash值的前8位 top := tophash(hash)bucketloop: for ; b != nil; b = b.overflow(t) { for i := uintptr(0); i < bucketCnt; i++ { if b.tophash[i] != top { if b.tophash[i] == emptyRest { break bucketloop } continue } //定位到key的位置 k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize)) if t.indirectkey() { //對(duì)于指針需要解引用 k = *((*unsafe.Pointer)(k)) } if t.key.equal(key, k) { //定位到value的位置 e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize)) if t.indirectelem() { //對(duì)于指針需要解引用 e = *((*unsafe.Pointer)(e)) } return e } } } return unsafe.Pointer(&zeroVal[0])}

map的賦值

const hashWriting = 4 // a goroutine is writing to the map// 判斷是否是空節(jié)點(diǎn)func isEmpty(x uint8) bool { return x <= emptyOne // x <= 1}func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer { if h == nil { panic(plainError("assignment to entry in nil map")) } //省略條件判斷 if h.flags&hashWriting != 0 { throw("concurrent map writes") } hash := t.hasher(key, uintptr(h.hash0)) // Set hashWriting after calling t.hasher, since t.hasher may panic, // in which case we have not actually done a write. h.flags ^= hashWriting if h.buckets == nil { h.buckets = newobject(t.bucket) // newarray(t.bucket, 1) }again: bucket := hash & bucketMask(h.B) if h.growing() { growWork(t, h, bucket) } b := (*bmap)(add(h.buckets, bucket*uintptr(t.bucketsize))) top := tophash(hash) var inserti *uint8 var insertk unsafe.Pointer var elem unsafe.Pointerbucketloop: for { for i := uintptr(0); i < bucketCnt; i++ { if b.tophash[i] != top { if isEmpty(b.tophash[i]) && inserti == nil { inserti = &b.tophash[i] insertk = add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize)) elem = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize)) } if b.tophash[i] == emptyRest { break bucketloop } continue } k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize)) if t.indirectkey() { k = *((*unsafe.Pointer)(k)) } if !t.key.equal(key, k) { continue } // already have a mapping for key. Update it. if t.needkeyupdate() { typedmemmove(t.key, k, key) } elem = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize)) goto done } ovf := b.overflow(t) if ovf == nil { break } b = ovf } //沒有找到key，需要分配空間，先判斷是否需要擴(kuò)容，需擴(kuò)容則重新計(jì)算 if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) { hashGrow(t, h) goto again // Growing the table invalidates everything, so try again } if inserti == nil { newb := h.newoverflow(t, b) inserti = &newb.tophash[0] insertk = add(unsafe.Pointer(newb), dataOffset) elem = add(insertk, bucketCnt*uintptr(t.keysize)) } // store new key/elem at insert position if t.indirectkey() { kmem := newobject(t.key) *(*unsafe.Pointer)(insertk) = kmem insertk = kmem } if t.indirectelem() { vmem := newobject(t.elem) *(*unsafe.Pointer)(elem) = vmem } typedmemmove(t.key, insertk, key) *inserti = top h.count++done: if h.flags&hashWriting == 0 { throw("concurrent map writes") } h.flags &^= hashWriting if t.indirectelem() { elem = *((*unsafe.Pointer)(elem)) } return elem}

map的刪除

func mapdelete(t *maptype, h *hmap, key unsafe.Pointer) { //... 忽略檢查 if h == nil || h.count == 0 { if t.hashMightPanic() { t.hasher(key, 0) // see issue 23734 } return } if h.flags&hashWriting != 0 { throw("concurrent map writes") } hash := t.hasher(key, uintptr(h.hash0)) // Set hashWriting after calling t.hasher, since t.hasher may panic, // in which case we have not actually done a write (delete). h.flags ^= hashWriting bucket := hash & bucketMask(h.B) if h.growing() { growWork(t, h, bucket) } b := (*bmap)(add(h.buckets, bucket*uintptr(t.bucketsize))) bOrig := b top := tophash(hash)search: for ; b != nil; b = b.overflow(t) { for i := uintptr(0); i < bucketCnt; i++ { if b.tophash[i] != top { if b.tophash[i] == emptyRest { //遍歷到最后仍未找到 break search } continue } k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize)) k2 := k if t.indirectkey() { k2 = *((*unsafe.Pointer)(k2)) } if !t.key.equal(key, k2) { //比較key是否一致 continue } // Only clear key if there are pointers in it. if t.indirectkey() { *(*unsafe.Pointer)(k) = nil } else if t.key.ptrdata != 0 { memclrHasPointers(k, t.key.size) } e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize)) if t.indirectelem() { *(*unsafe.Pointer)(e) = nil } else if t.elem.ptrdata != 0 { memclrHasPointers(e, t.elem.size) } else { memclrNoHeapPointers(e, t.elem.size) } //將tophash標(biāo)記置為空值 b.tophash[i] = emptyOne if i == bucketCnt-1 { if b.overflow(t) != nil && b.overflow(t).tophash[0] != emptyRest { goto notLast } } else { if b.tophash[i+1] != emptyRest { goto notLast } } for { b.tophash[i] = emptyRest if i == 0 { if b == bOrig { break // beginning of initial bucket, we're done. } // Find previous bucket, continue at its last entry. c := b for b = bOrig; b.overflow(t) != c; b = b.overflow(t) { } i = bucketCnt - 1 } else { i-- } if b.tophash[i] != emptyOne { break } } notLast: h.count-- // Reset the hash seed to make it more difficult for attackers to // repeatedly trigger hash collisions. See issue 25237. if h.count == 0 { h.hash0 = fastrand() } break search } } if h.flags&hashWriting == 0 { throw("concurrent map writes") } h.flags &^= hashWriting}

map的遍歷

先來(lái)看個(gè)示例： 從紅色位置開始，先遍歷3號(hào)桶的e，然后是3號(hào)桶鏈接的f和g，接著遍歷到0號(hào)桶，由于0號(hào)桶未搬遷，只遍歷其中屬于0號(hào)桶的b和c，接著到1號(hào)桶的h，最后是2號(hào)桶的a和d。

遍歷結(jié)果：e->f->g->b->c->h->a->d

源碼執(zhí)行流程圖：

// 哈希遍歷結(jié)構(gòu)體type hiter struct { key unsafe.Pointer // Must be in first position. Write nil to indicate iteration end (see cmd/compile/internal/gc/range.go). elem unsafe.Pointer // Must be in second position (see cmd/compile/internal/gc/range.go). t *maptype h *hmap buckets unsafe.Pointer // bucket ptr at hash_iter initialization time bptr *bmap // current bucket overflow *[]*bmap // keeps overflow buckets of hmap.buckets alive oldoverflow *[]*bmap // keeps overflow buckets of hmap.oldbuckets alive startBucket uintptr // bucket iteration started at offset uint8 // intra-bucket offset to start from during iteration (should be big enough to hold bucketCnt-1) wrapped bool // already wrapped around from end of bucket array to beginning B uint8 i uint8 bucket uintptr checkBucket uintptr}func mapiterinit(t *maptype, h *hmap, it *hiter) { if raceenabled && h != nil { callerpc := getcallerpc() racereadpc(unsafe.Pointer(h), callerpc, funcPC(mapiterinit)) } if h == nil || h.count == 0 { return } if unsafe.Sizeof(hiter{})/sys.PtrSize != 12 { throw("hash_iter size incorrect") // see cmd/compile/internal/gc/reflect.go } it.t = t it.h = h it.B = h.B it.buckets = h.buckets if t.bucket.ptrdata == 0 { h.createOverflow() it.overflow = h.extra.overflow it.oldoverflow = h.extra.oldoverflow } // 定位到隨機(jī)位置 r := uintptr(fastrand()) if h.B > 31-bucketCntBits { r += uintptr(fastrand()) << 31 } it.startBucket = r & bucketMask(h.B) it.offset = uint8(r >> h.B & (bucketCnt - 1)) it.bucket = it.startBucket if old := h.flags; old&(iterator|oldIterator) != iterator|oldIterator { atomic.Or8(&h.flags, iterator|oldIterator) } mapiternext(it)}func mapiternext(it *hiter) { h := it.h if raceenabled { callerpc := getcallerpc() racereadpc(unsafe.Pointer(h), callerpc, funcPC(mapiternext)) } if h.flags&hashWriting != 0 { throw("concurrent map iteration and map write") } t := it.t bucket := it.bucket b := it.bptr i := it.i checkBucket := it.checkBucketnext: if b == nil { if bucket == it.startBucket && it.wrapped { // end of iteration it.key = nil it.elem = nil return } if h.growing() && it.B == h.B { oldbucket := bucket & it.h.oldbucketmask() b = (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.bucketsize))) if !evacuated(b) { checkBucket = bucket } else { b = (*bmap)(add(it.buckets, bucket*uintptr(t.bucketsize))) checkBucket = noCheck } } else { b = (*bmap)(add(it.buckets, bucket*uintptr(t.bucketsize))) checkBucket = noCheck } bucket++ if bucket == bucketShift(it.B) { bucket = 0 it.wrapped = true } i = 0 } for ; i < bucketCnt; i++ { offi := (i + it.offset) & (bucketCnt - 1) if isEmpty(b.tophash[offi]) || b.tophash[offi] == evacuatedEmpty { continue } k := add(unsafe.Pointer(b), dataOffset+uintptr(offi)*uintptr(t.keysize)) if t.indirectkey() { k = *((*unsafe.Pointer)(k)) } e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+uintptr(offi)*uintptr(t.elemsize)) if checkBucket != noCheck && !h.sameSizeGrow() { if t.reflexivekey() || t.key.equal(k, k) { hash := t.hasher(k, uintptr(h.hash0)) if hash&bucketMask(it.B) != checkBucket { continue } } else { if checkBucket>>(it.B-1) != uintptr(b.tophash[offi]&1) { continue } } } if (b.tophash[offi] != evacuatedX && b.tophash[offi] != evacuatedY) || !(t.reflexivekey() || t.key.equal(k, k)) { it.key = k if t.indirectelem() { e = *((*unsafe.Pointer)(e)) } it.elem = e } else { rk, re := mapaccessK(t, h, k) if rk == nil { continue // key has been deleted } it.key = rk it.elem = re } it.bucket = bucket if it.bptr != b { // avoid unnecessary write barrier; see issue 14921 it.bptr = b } it.i = i + 1 it.checkBucket = checkBucket return } b = b.overflow(t) i = 0 goto next}

管道

基本概念

不要通過共享內(nèi)存來(lái)通信，而要通過通信來(lái)實(shí)現(xiàn)內(nèi)存共享。 Do not communicate by sharing memory; instead, share memory by communicating.

chan T // 聲明一個(gè)雙向通道chan

示例

func goRoutineA(a

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

// 管道type hchan struct { qcount uint // 元素的數(shù)量 dataqsiz uint // 緩沖區(qū)的大小 buf unsafe.Pointer // 指向緩沖區(qū)的指針 elemsize uint16 // 每個(gè)元素的大小 closed uint32 // 管道狀態(tài) elemtype *_type // 元素類型 sendx uint // 發(fā)送的索引 recvx uint // 接收的索引 recvq waitq // 等待接收的隊(duì)列 sendq waitq // 等待發(fā)送的隊(duì)列 lock mutex //互斥鎖}// 等待隊(duì)列type waitq struct { first *sudog last *sudog}type sudog struct { g *g next *sudog prev *sudog elem unsafe.Pointer // data element (may point to stack) ... isSelect bool ... c *hchan // channel}func goroutineA(a

chan的創(chuàng)建

const ( maxAlign = 8 hchanSize = unsafe.Sizeof(hchan{}) + uintptr(-int(unsafe.Sizeof(hchan{}))&(maxAlign-1)))func makechan(t *chantype, size int) *hchan { elem := t.elem // ... 忽略檢查和對(duì)齊 mem, overflow := math.MulUintptr(elem.size, uintptr(size)) if overflow || mem > maxAlloc-hchanSize || size < 0 { panic(plainError("makechan: size out of range")) } var c *hchan switch { case mem == 0: // 無(wú)緩沖區(qū)，只分配chan c = (*hchan)(mallocgc(hchanSize, nil, true)) // 用于競(jìng)態(tài)檢測(cè) c.buf = c.raceaddr() case elem.ptrdata == 0: // 元素不包含指針，一次調(diào)用分配chan和緩沖區(qū) c = (*hchan)(mallocgc(hchanSize+mem, nil, true)) c.buf = add(unsafe.Pointer(c), hchanSize) default: // 元素包含指針，兩次調(diào)用分配 c = new(hchan) c.buf = mallocgc(mem, elem, true) } c.elemsize = uint16(elem.size) c.elemtype = elem c.dataqsiz = uint(size) lockInit(&c.lock, lockRankHchan) return c}

chan的接收

ch := make(chan int, 3)ch 0 { t0 = cputicks() } lock(&c.lock) if c.closed != 0 && c.qcount == 0 { // ... 忽略競(jìng)態(tài)檢查 unlock(&c.lock) if ep != nil { typedmemclr(c.elemtype, ep) } return true, false } //等待發(fā)送隊(duì)列里有g(shù)oroutine存在，調(diào)用recv函數(shù)處理 if sg := c.sendq.dequeue(); sg != nil { recv(c, sg, ep, func() { unlock(&c.lock) }, 3) return true, true } // 緩沖型，buf里有元素，可以正常接收 if c.qcount > 0 { // 直接從循環(huán)數(shù)組里找到要接收的元素 qp := chanbuf(c, c.recvx) // ... 忽略競(jìng)態(tài)檢查 if ep != nil { typedmemmove(c.elemtype, ep, qp) } // 清理掉循環(huán)數(shù)組里相應(yīng)位置的值 typedmemclr(c.elemtype, qp) // 接收游標(biāo)向前移動(dòng) c.recvx++ // 接收游標(biāo)歸零 if c.recvx == c.dataqsiz { c.recvx = 0 } // buf 數(shù)組里的元素個(gè)數(shù)減 1 c.qcount-- unlock(&c.lock) return true, true } if !block { // 非阻塞接收，解鎖。selected返回false，因?yàn)闆]有接收到值 unlock(&c.lock) return false, false } // 接下來(lái)就是處理要被阻塞的情況，構(gòu)造一個(gè)sudog gp := getg() mysg := acquireSudog() mysg.releasetime = 0 if t0 != 0 { mysg.releasetime = -1 } // 待接收數(shù)據(jù)的地址保存下來(lái) mysg.elem = ep mysg.waitlink = nil gp.waiting = mysg mysg.g = gp mysg.isSelect = false mysg.c = c gp.param = nil // 進(jìn)入channel 的等待接收隊(duì)列 c.recvq.enqueue(mysg) // 將當(dāng)前 goroutine 掛起 atomic.Store8(&gp.parkingOnChan, 1) gopark(chanparkcommit, unsafe.Pointer(&c.lock), waitReasonChanReceive, traceEvGoBlockRecv, 2) // 被喚醒了，接著從這里繼續(xù)執(zhí)行一些掃尾工作 if mysg != gp.waiting { throw("G waiting list is corrupted") } gp.waiting = nil gp.activeStackChans = false if mysg.releasetime > 0 { blockevent(mysg.releasetime-t0, 2) } success := mysg.success gp.param = nil mysg.c = nil releaseSudog(mysg) return true, success}

chanrecv接收管道c，將接收到的數(shù)據(jù)寫入到ep 如果ep為空，則忽略接收到的數(shù)據(jù) 如果block == false，且沒有元素就緒，返回(false, false) 否則，如果c關(guān)閉了，將ep置0，返回(true, false) 否則，將接收到的數(shù)據(jù)填充到ep中，返回(true, true)

func recv(c *hchan, sg *sudog, ep unsafe.Pointer, unlockf func(), skip int) { if c.dataqsiz == 0 { // ... 忽略競(jìng)態(tài)檢查 if ep != nil { // 直接拷貝數(shù)據(jù)，從 sender goroutine -> receiver goroutine recvDirect(c.elemtype, sg, ep) } } else { // 緩沖型的 channel，但 buf 已滿。 // 將循環(huán)數(shù)組 buf 隊(duì)首的元素拷貝到接收數(shù)據(jù)的地址 // 將發(fā)送者的數(shù)據(jù)入隊(duì)。實(shí)際上這時(shí) revx 和 sendx 值相等 // 找到接收游標(biāo) qp := chanbuf(c, c.recvx) // ... 忽略競(jìng)態(tài)檢查 // 將接收游標(biāo)處的數(shù)據(jù)拷貝給接收者 if ep != nil { typedmemmove(c.elemtype, ep, qp) } // 將發(fā)送者數(shù)據(jù)拷貝到 buf typedmemmove(c.elemtype, qp, sg.elem) // 更新游標(biāo)值 c.recvx++ if c.recvx == c.dataqsiz { c.recvx = 0 } c.sendx = c.recvx // c.sendx = (c.sendx+1) % c.dataqsiz } sg.elem = nil gp := sg.g unlockf() gp.param = unsafe.Pointer(sg) sg.success = true if sg.releasetime != 0 { sg.releasetime = cputicks() } // 喚醒發(fā)送的 goroutine。需要等到調(diào)度器的光臨 goready(gp, skip+1)}func recvDirect(t *_type, sg *sudog, dst unsafe.Pointer) { src := sg.elem typeBitsBulkBarrier(t, uintptr(dst), uintptr(src), t.size) memmove(dst, src, t.size)}

管道的發(fā)送

//判斷緩沖區(qū)是否滿了，有兩種可能// 1. channel 是非緩沖型的，且等待接收隊(duì)列里沒有 goroutine// 2. channel 是緩沖型的，但循環(huán)數(shù)組已經(jīng)裝滿了元素func full(c *hchan) bool { if c.dataqsiz == 0 { return c.recvq.first == nil } return c.qcount == c.dataqsiz}func chansend(c *hchan, ep unsafe.Pointer, block bool, callerpc uintptr) bool { if c == nil { if !block { return false } gopark(nil, nil, waitReasonChanSendNilChan, traceEvGoStop, 2) throw("unreachable") } // ... 忽略競(jìng)態(tài)檢查 // 對(duì)于不阻塞的 send，快速檢測(cè)失敗場(chǎng)景 // 如果channel未關(guān)閉且channel沒有多余的緩沖空間，返回false if !block && c.closed == 0 && full(c) { return false } var t0 int64 if blockprofilerate > 0 { t0 = cputicks() } //加鎖 lock(&c.lock) //嘗試向已經(jīng)關(guān)閉的channel發(fā)送數(shù)據(jù)會(huì)觸發(fā)panic if c.closed != 0 { unlock(&c.lock) panic(plainError("send on closed channel")) } // 如果接收隊(duì)列里有g(shù)oroutine，直接將要發(fā)送的數(shù)據(jù)拷貝到接收goroutine if sg := c.recvq.dequeue(); sg != nil { send(c, sg, ep, func() { unlock(&c.lock) }, 3) return true } // 對(duì)于緩沖型的channel，如果還有緩沖空間 if c.qcount < c.dataqsiz { // qp指向buf的sendx位置 qp := chanbuf(c, c.sendx) // ... 忽略競(jìng)態(tài)檢查 // 將數(shù)據(jù)從ep處拷貝到qp typedmemmove(c.elemtype, qp, ep) // 發(fā)送游標(biāo)值加 1 c.sendx++ // 如果發(fā)送游標(biāo)值等于容量值，游標(biāo)值歸0 if c.sendx == c.dataqsiz { c.sendx = 0 } // 緩沖區(qū)的元素?cái)?shù)量加一 c.qcount++ // 解鎖 unlock(&c.lock) return true } if !block { unlock(&c.lock) return false } // channel滿了，發(fā)送方會(huì)被阻塞。接下來(lái)會(huì)構(gòu)造一個(gè)sudog gp := getg() mysg := acquireSudog() mysg.releasetime = 0 if t0 != 0 { mysg.releasetime = -1 } mysg.elem = ep mysg.waitlink = nil mysg.g = gp mysg.isSelect = false mysg.c = c gp.waiting = mysg gp.param = nil // 當(dāng)前 goroutine 進(jìn)入發(fā)送等待隊(duì)列 c.sendq.enqueue(mysg) // 當(dāng)前 goroutine 被掛起 atomic.Store8(&gp.parkingOnChan, 1) gopark(chanparkcommit, unsafe.Pointer(&c.lock), waitReasonChanSend, traceEvGoBlockSend, 2) // 保持活躍 KeepAlive(ep) // 從這里開始被喚醒了(channel有機(jī)會(huì)可以發(fā)送了) if mysg != gp.waiting { throw("G waiting list is corrupted") } gp.waiting = nil gp.activeStackChans = false closed := !mysg.success gp.param = nil if mysg.releasetime > 0 { blockevent(mysg.releasetime-t0, 2) } mysg.c = nil releaseSudog(mysg) if closed { if c.closed == 0 { throw("chansend: spurious wakeup") } // 被喚醒后，channel關(guān)閉了，觸發(fā)panic panic(plainError("send on closed channel")) } return true}func send(c *hchan, sg *sudog, ep unsafe.Pointer, unlockf func(), skip int) { // ... 忽略競(jìng)態(tài)檢查 if sg.elem != nil { sendDirect(c.elemtype, sg, ep) sg.elem = nil } gp := sg.g unlockf() gp.param = unsafe.Pointer(sg) sg.success = true if sg.releasetime != 0 { sg.releasetime = cputicks() } goready(gp, skip+1)}func sendDirect(t *_type, sg *sudog, src unsafe.Pointer) { // src 在當(dāng)前 goroutine 的棧上，dst 是另一個(gè) goroutine 的棧 // 直接進(jìn)行內(nèi)存"搬遷" // 如果目標(biāo)地址的棧發(fā)生了棧收縮，當(dāng)我們讀出了 sg.elem 后 // 就不能修改真正的 dst 位置的值了 // 因此需要在讀和寫之前加上一個(gè)屏障 dst := sg.elem typeBitsBulkBarrier(t, uintptr(dst), uintptr(src), t.size) memmove(dst, src, t.size)}

管道的關(guān)閉

func closechan(c *hchan) { // 關(guān)閉空channel會(huì)觸發(fā)panic if c == nil { panic(plainError("close of nil channel")) } lock(&c.lock) if c.closed != 0 { unlock(&c.lock) // 關(guān)閉已經(jīng)關(guān)閉的channel會(huì)觸發(fā)panic panic(plainError("close of closed channel")) } // ... 忽略競(jìng)態(tài)檢查 //設(shè)置管道已關(guān)閉 c.closed = 1 var glist gList // 將channel所有等待接收隊(duì)列的里sudog釋放 for { sg := c.recvq.dequeue() if sg == nil { break } // 如果elem不為空，說(shuō)明此receiver未忽略接收數(shù)據(jù) // 給它賦一個(gè)相應(yīng)類型的零值 if sg.elem != nil { typedmemclr(c.elemtype, sg.elem) sg.elem = nil } if sg.releasetime != 0 { sg.releasetime = cputicks() } gp := sg.g gp.param = unsafe.Pointer(sg) sg.success = false // ... 忽略競(jìng)態(tài)檢查 glist.push(gp) } // 將channel所有等待發(fā)送隊(duì)列的里sudog釋放 for { sg := c.sendq.dequeue() if sg == nil { break } sg.elem = nil if sg.releasetime != 0 { sg.releasetime = cputicks() } gp := sg.g gp.param = unsafe.Pointer(sg) sg.success = false // ... 忽略競(jìng)態(tài)檢查 glist.push(gp) } unlock(&c.lock) // 遍歷鏈表執(zhí)行釋放 for !glist.empty() { gp := glist.pop() gp.schedlink = 0 goready(gp, 3) }}

管道的使用

參考文獻(xiàn)

• 《Go語(yǔ)言實(shí)戰(zhàn)》
• 《Go語(yǔ)言學(xué)習(xí)筆記》
• 《Go并發(fā)編程實(shí)戰(zhàn)》
• 《Go語(yǔ)言核心編程》
• 《Go程序設(shè)計(jì)語(yǔ)言》
• go語(yǔ)言源碼
• 深度解密Go語(yǔ)言之slice
• 深度解密Go語(yǔ)言之map
• 深度解密Go語(yǔ)言之channel
• Go 語(yǔ)言設(shè)計(jì)與實(shí)現(xiàn)
• Diving Deep Into The Golang Channels
• 并發(fā)與并行 · Concurrency in Go 中文筆記 · 看云

出處:https://zhuanlan.zhihu.com/p/341945051

總結(jié)

以上是生活随笔為你收集整理的go 判断元素是否在slice_Go内置数据结构原理的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。