map 是Go語(yǔ)言中基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu),在日常的使用中經(jīng)常被用到。但是它底層是如何實(shí)現(xiàn)的呢?
十多年的化州網(wǎng)站建設(shè)經(jīng)驗(yàn),針對(duì)設(shè)計(jì)、前端、開發(fā)、售后、文案、推廣等六對(duì)一服務(wù),響應(yīng)快,48小時(shí)及時(shí)工作處理。營(yíng)銷型網(wǎng)站的優(yōu)勢(shì)是能夠根據(jù)用戶設(shè)備顯示端的尺寸不同,自動(dòng)調(diào)整化州建站的顯示方式,使網(wǎng)站能夠適用不同顯示終端,在瀏覽器中調(diào)整網(wǎng)站的寬度,無(wú)論在任何一種瀏覽器上瀏覽網(wǎng)站,都能展現(xiàn)優(yōu)雅布局與設(shè)計(jì),從而大程度地提升瀏覽體驗(yàn)。創(chuàng)新互聯(lián)建站從事“化州網(wǎng)站設(shè)計(jì)”,“化州網(wǎng)站推廣”以來(lái),每個(gè)客戶項(xiàng)目都認(rèn)真落實(shí)執(zhí)行。
總體來(lái)說(shuō)golang的map是hashmap,是使用數(shù)組+鏈表的形式實(shí)現(xiàn)的,使用拉鏈法消除hash沖突。
golang的map由兩種重要的結(jié)構(gòu),hmap和bmap(下文中都有解釋),主要就是hmap中包含一個(gè)指向bmap數(shù)組的指針,key經(jīng)過(guò)hash函數(shù)之后得到一個(gè)數(shù),這個(gè)數(shù)低位用于選擇bmap(當(dāng)作bmap數(shù)組指針的下表),高位用于放在bmap的[8]uint8數(shù)組中,用于快速試錯(cuò)。然后一個(gè)bmap可以指向下一個(gè)bmap(拉鏈)。
Golang中map的底層實(shí)現(xiàn)是一個(gè)散列表,因此實(shí)現(xiàn)map的過(guò)程實(shí)際上就是實(shí)現(xiàn)散表的過(guò)程。在這個(gè)散列表中,主要出現(xiàn)的結(jié)構(gòu)體有兩個(gè),一個(gè)叫 hmap (a header for a go map),一個(gè)叫 bmap (a bucket for a Go map,通常叫其bucket)。這兩種結(jié)構(gòu)的樣子分別如下所示:
hmap :
圖中有很多字段,但是便于理解map的架構(gòu),你只需要關(guān)心的只有一個(gè),就是標(biāo)紅的字段: buckets數(shù)組 。Golang的map中用于存儲(chǔ)的結(jié)構(gòu)是bucket數(shù)組。而bucket(即bmap)的結(jié)構(gòu)是怎樣的呢?
bucket :
相比于hmap,bucket的結(jié)構(gòu)顯得簡(jiǎn)單一些,標(biāo)紅的字段依然是“核心”,我們使用的map中的key和value就存儲(chǔ)在這里?!案呶还V怠睌?shù)組記錄的是當(dāng)前bucket中key相關(guān)的“索引”,稍后會(huì)詳細(xì)敘述。還有一個(gè)字段是一個(gè)指向擴(kuò)容后的bucket的指針,使得bucket會(huì)形成一個(gè)鏈表結(jié)構(gòu)。例如下圖:
由此看出hmap和bucket的關(guān)系是這樣的:
而bucket又是一個(gè)鏈表,所以,整體的結(jié)構(gòu)應(yīng)該是這樣的:
哈希表的特點(diǎn)是會(huì)有一個(gè)哈希函數(shù),對(duì)你傳來(lái)的key進(jìn)行哈希運(yùn)算,得到唯一的值,一般情況下都是一個(gè)數(shù)值。Golang的map中也有這么一個(gè)哈希函數(shù),也會(huì)算出唯一的值,對(duì)于這個(gè)值的使用,Golang也是很有意思。
Golang把求得的值按照用途一分為二:高位和低位。
如圖所示,藍(lán)色為高位,紅色為低位。 然后低位用于尋找當(dāng)前key屬于hmap中的哪個(gè)bucket,而高位用于尋找bucket中的哪個(gè)key。上文中提到:bucket中有個(gè)屬性字段是“高位哈希值”數(shù)組,這里存的就是藍(lán)色的高位值,用來(lái)聲明當(dāng)前bucket中有哪些“key”,便于搜索查找。 需要特別指出的一點(diǎn)是:我們map中的key/value值都是存到同一個(gè)數(shù)組中的。數(shù)組中的順序是這樣的:
并不是key0/value0/key1/value1的形式,這樣做的好處是:在key和value的長(zhǎng)度不同的時(shí)候,可 以消除padding(內(nèi)存對(duì)齊)帶來(lái)的空間浪費(fèi) 。
現(xiàn)在,我們可以得到Go語(yǔ)言map的整個(gè)的結(jié)構(gòu)圖了:(hash結(jié)果的低位用于選擇把KV放在bmap數(shù)組中的哪一個(gè)bmap中,高位用于key的快速預(yù)覽,用于快速試錯(cuò))
map的擴(kuò)容
當(dāng)以上的哈希表增長(zhǎng)的時(shí)候,Go語(yǔ)言會(huì)將bucket數(shù)組的數(shù)量擴(kuò)充一倍,產(chǎn)生一個(gè)新的bucket數(shù)組,并將舊數(shù)組的數(shù)據(jù)遷移至新數(shù)組。
加載因子
判斷擴(kuò)充的條件,就是哈希表中的加載因子(即loadFactor)。
加載因子是一個(gè)閾值,一般表示為:散列包含的元素?cái)?shù) 除以 位置總數(shù)。是一種“產(chǎn)生沖突機(jī)會(huì)”和“空間使用”的平衡與折中:加載因子越小,說(shuō)明空間空置率高,空間使用率小,但是加載因子越大,說(shuō)明空間利用率上去了,但是“產(chǎn)生沖突機(jī)會(huì)”高了。
每種哈希表的都會(huì)有一個(gè)加載因子,數(shù)值超過(guò)加載因子就會(huì)為哈希表擴(kuò)容。
Golang的map的加載因子的公式是:map長(zhǎng)度 / 2^B(這是代表bmap數(shù)組的長(zhǎng)度,B是取的低位的位數(shù))閾值是6.5。其中B可以理解為已擴(kuò)容的次數(shù)。
當(dāng)Go的map長(zhǎng)度增長(zhǎng)到大于加載因子所需的map長(zhǎng)度時(shí),Go語(yǔ)言就會(huì)將產(chǎn)生一個(gè)新的bucket數(shù)組,然后把舊的bucket數(shù)組移到一個(gè)屬性字段oldbucket中。注意:并不是立刻把舊的數(shù)組中的元素轉(zhuǎn)義到新的bucket當(dāng)中,而是,只有當(dāng)訪問(wèn)到具體的某個(gè)bucket的時(shí)候,會(huì)把bucket中的數(shù)據(jù)轉(zhuǎn)移到新的bucket中。
如下圖所示:當(dāng)擴(kuò)容的時(shí)候,Go的map結(jié)構(gòu)體中,會(huì)保存舊的數(shù)據(jù),和新生成的數(shù)組
上面部分代表舊的有數(shù)據(jù)的bucket,下面部分代表新生成的新的bucket。藍(lán)色代表存有數(shù)據(jù)的bucket,橘黃色代表空的bucket。
擴(kuò)容時(shí)map并不會(huì)立即把新數(shù)據(jù)做遷移,而是當(dāng)訪問(wèn)原來(lái)舊bucket的數(shù)據(jù)的時(shí)候,才把舊數(shù)據(jù)做遷移,如下圖:
注意:這里并不會(huì)直接刪除舊的bucket,而是把原來(lái)的引用去掉,利用GC清除內(nèi)存。
map中數(shù)據(jù)的刪除
如果理解了map的整體結(jié)構(gòu),那么查找、更新、刪除的基本步驟應(yīng)該都很清楚了。這里不再贅述。
值得注意的是,找到了map中的數(shù)據(jù)之后,針對(duì)key和value分別做如下操作:
1
2
3
4
1、如果``key``是一個(gè)指針類型的,則直接將其置為空,等待GC清除;
2、如果是值類型的,則清除相關(guān)內(nèi)存。
3、同理,對(duì)``value``做相同的操作。
4、最后把key對(duì)應(yīng)的高位值對(duì)應(yīng)的數(shù)組index置為空。
Goroutine調(diào)度是一個(gè)很復(fù)雜的機(jī)制,下面嘗試用簡(jiǎn)單的語(yǔ)言描述一下Goroutine調(diào)度機(jī)制,想要對(duì)其有更深入的了解可以去研讀一下源碼。
首先介紹一下GMP什么意思:
G ----------- goroutine: 即Go協(xié)程,每個(gè)go關(guān)鍵字都會(huì)創(chuàng)建一個(gè)協(xié)程。
M ---------- thread內(nèi)核級(jí)線程,所有的G都要放在M上才能運(yùn)行。
P ----------- processor處理器,調(diào)度G到M上,其維護(hù)了一個(gè)隊(duì)列,存儲(chǔ)了所有需要它來(lái)調(diào)度的G。
Goroutine 調(diào)度器P和 OS 調(diào)度器是通過(guò) M 結(jié)合起來(lái)的,每個(gè) M 都代表了 1 個(gè)內(nèi)核線程,OS 調(diào)度器負(fù)責(zé)把內(nèi)核線程分配到 CPU 的核上執(zhí)行
模型圖:
避免頻繁的創(chuàng)建、銷毀線程,而是對(duì)線程的復(fù)用。
1)work stealing機(jī)制
當(dāng)本線程無(wú)可運(yùn)行的G時(shí),嘗試從其他線程綁定的P偷取G,而不是銷毀線程。
2)hand off機(jī)制
當(dāng)本線程M0因?yàn)镚0進(jìn)行系統(tǒng)調(diào)用阻塞時(shí),線程釋放綁定的P,把P轉(zhuǎn)移給其他空閑的線程執(zhí)行。進(jìn)而某個(gè)空閑的M1獲取P,繼續(xù)執(zhí)行P隊(duì)列中剩下的G。而M0由于陷入系統(tǒng)調(diào)用而進(jìn)被阻塞,M1接替M0的工作,只要P不空閑,就可以保證充分利用CPU。M1的來(lái)源有可能是M的緩存池,也可能是新建的。當(dāng)G0系統(tǒng)調(diào)用結(jié)束后,根據(jù)M0是否能獲取到P,將會(huì)將G0做不同的處理:
如果有空閑的P,則獲取一個(gè)P,繼續(xù)執(zhí)行G0。
如果沒(méi)有空閑的P,則將G0放入全局隊(duì)列,等待被其他的P調(diào)度。然后M0將進(jìn)入緩存池睡眠。
如下圖
GOMAXPROCS設(shè)置P的數(shù)量,最多有GOMAXPROCS個(gè)線程分布在多個(gè)CPU上同時(shí)運(yùn)行
在Go中一個(gè)goroutine最多占用CPU 10ms,防止其他goroutine被餓死。
具體可以去看另一篇文章
【Golang詳解】go語(yǔ)言調(diào)度機(jī)制 搶占式調(diào)度
當(dāng)創(chuàng)建一個(gè)新的G之后優(yōu)先加入本地隊(duì)列,如果本地隊(duì)列滿了,會(huì)將本地隊(duì)列的G移動(dòng)到全局隊(duì)列里面,當(dāng)M執(zhí)行work stealing從其他P偷不到G時(shí),它可以從全局G隊(duì)列獲取G。
協(xié)程經(jīng)歷過(guò)程
我們創(chuàng)建一個(gè)協(xié)程 go func()經(jīng)歷過(guò)程如下圖:
說(shuō)明:
這里有兩個(gè)存儲(chǔ)G的隊(duì)列,一個(gè)是局部調(diào)度器P的本地隊(duì)列、一個(gè)是全局G隊(duì)列。新創(chuàng)建的G會(huì)先保存在P的本地隊(duì)列中,如果P的本地隊(duì)列已經(jīng)滿了就會(huì)保存在全局的隊(duì)列中;處理器本地隊(duì)列是一個(gè)使用數(shù)組構(gòu)成的環(huán)形鏈表,它最多可以存儲(chǔ) 256 個(gè)待執(zhí)行任務(wù)。
G只能運(yùn)行在M中,一個(gè)M必須持有一個(gè)P,M與P是1:1的關(guān)系。M會(huì)從P的本地隊(duì)列彈出一個(gè)可執(zhí)行狀態(tài)的G來(lái)執(zhí)行,如果P的本地隊(duì)列為空,就會(huì)想其他的MP組合偷取一個(gè)可執(zhí)行的G來(lái)執(zhí)行;
一個(gè)M調(diào)度G執(zhí)行的過(guò)程是一個(gè)循環(huán)機(jī)制;會(huì)一直從本地隊(duì)列或全局隊(duì)列中獲取G
上面說(shuō)到P的個(gè)數(shù)默認(rèn)等于CPU核數(shù),每個(gè)M必須持有一個(gè)P才可以執(zhí)行G,一般情況下M的個(gè)數(shù)會(huì)略大于P的個(gè)數(shù),這多出來(lái)的M將會(huì)在G產(chǎn)生系統(tǒng)調(diào)用時(shí)發(fā)揮作用。類似線程池,Go也提供一個(gè)M的池子,需要時(shí)從池子中獲取,用完放回池子,不夠用時(shí)就再創(chuàng)建一個(gè)。
work-stealing調(diào)度算法:當(dāng)M執(zhí)行完了當(dāng)前P的本地隊(duì)列隊(duì)列里的所有G后,P也不會(huì)就這么在那躺尸啥都不干,它會(huì)先嘗試從全局隊(duì)列隊(duì)列尋找G來(lái)執(zhí)行,如果全局隊(duì)列為空,它會(huì)隨機(jī)挑選另外一個(gè)P,從它的隊(duì)列里中拿走一半的G到自己的隊(duì)列中執(zhí)行。
如果一切正常,調(diào)度器會(huì)以上述的那種方式順暢地運(yùn)行,但這個(gè)世界沒(méi)這么美好,總有意外發(fā)生,以下分析goroutine在兩種例外情況下的行為。
Go runtime會(huì)在下面的goroutine被阻塞的情況下運(yùn)行另外一個(gè)goroutine:
用戶態(tài)阻塞/喚醒
當(dāng)goroutine因?yàn)閏hannel操作或者network I/O而阻塞時(shí)(實(shí)際上golang已經(jīng)用netpoller實(shí)現(xiàn)了goroutine網(wǎng)絡(luò)I/O阻塞不會(huì)導(dǎo)致M被阻塞,僅阻塞G,這里僅僅是舉個(gè)栗子),對(duì)應(yīng)的G會(huì)被放置到某個(gè)wait隊(duì)列(如channel的waitq),該G的狀態(tài)由_Gruning變?yōu)開Gwaitting,而M會(huì)跳過(guò)該G嘗試獲取并執(zhí)行下一個(gè)G,如果此時(shí)沒(méi)有可運(yùn)行的G供M運(yùn)行,那么M將解綁P,并進(jìn)入sleep狀態(tài);當(dāng)阻塞的G被另一端的G2喚醒時(shí)(比如channel的可讀/寫通知),G被標(biāo)記為,嘗試加入G2所在P的runnext(runnext是線程下一個(gè)需要執(zhí)行的 Goroutine。), 然后再是P的本地隊(duì)列和全局隊(duì)列。
系統(tǒng)調(diào)用阻塞
當(dāng)M執(zhí)行某一個(gè)G時(shí)候如果發(fā)生了阻塞操作,M會(huì)阻塞,如果當(dāng)前有一些G在執(zhí)行,調(diào)度器會(huì)把這個(gè)線程M從P中摘除,然后再創(chuàng)建一個(gè)新的操作系統(tǒng)的線程(如果有空閑的線程可用就復(fù)用空閑線程)來(lái)服務(wù)于這個(gè)P。當(dāng)M系統(tǒng)調(diào)用結(jié)束時(shí)候,這個(gè)G會(huì)嘗試獲取一個(gè)空閑的P執(zhí)行,并放入到這個(gè)P的本地隊(duì)列。如果獲取不到P,那么這個(gè)線程M變成休眠狀態(tài), 加入到空閑線程中,然后這個(gè)G會(huì)被放入全局隊(duì)列中。
隊(duì)列輪轉(zhuǎn)
可見(jiàn)每個(gè)P維護(hù)著一個(gè)包含G的隊(duì)列,不考慮G進(jìn)入系統(tǒng)調(diào)用或IO操作的情況下,P周期性的將G調(diào)度到M中執(zhí)行,執(zhí)行一小段時(shí)間,將上下文保存下來(lái),然后將G放到隊(duì)列尾部,然后從隊(duì)列中重新取出一個(gè)G進(jìn)行調(diào)度。
除了每個(gè)P維護(hù)的G隊(duì)列以外,還有一個(gè)全局的隊(duì)列,每個(gè)P會(huì)周期性地查看全局隊(duì)列中是否有G待運(yùn)行并將其調(diào)度到M中執(zhí)行,全局隊(duì)列中G的來(lái)源,主要有從系統(tǒng)調(diào)用中恢復(fù)的G。之所以P會(huì)周期性地查看全局隊(duì)列,也是為了防止全局隊(duì)列中的G被餓死。
除了每個(gè)P維護(hù)的G隊(duì)列以外,還有一個(gè)全局的隊(duì)列,每個(gè)P會(huì)周期性地查看全局隊(duì)列中是否有G待運(yùn)行并將其調(diào)度到M中執(zhí)行,全局隊(duì)列中G的來(lái)源,主要有從系統(tǒng)調(diào)用中恢復(fù)的G。之所以P會(huì)周期性地查看全局隊(duì)列,也是為了防止全局隊(duì)列中的G被餓死。
M0
M0是啟動(dòng)程序后的編號(hào)為0的主線程,這個(gè)M對(duì)應(yīng)的實(shí)例會(huì)在全局變量rutime.m0中,不需要在heap上分配,M0負(fù)責(zé)執(zhí)行初始化操作和啟動(dòng)第一個(gè)G,在之后M0就和其他的M一樣了
G0
G0是每次啟動(dòng)一個(gè)M都會(huì)第一個(gè)創(chuàng)建的goroutine,G0僅用于負(fù)責(zé)調(diào)度G,G0不指向任何可執(zhí)行的函數(shù),每個(gè)M都會(huì)有一個(gè)自己的G0,在調(diào)度或系統(tǒng)調(diào)用時(shí)會(huì)使用G0的??臻g,全局變量的G0是M0的G0
一個(gè)G由于調(diào)度被中斷,此后如何恢復(fù)?
中斷的時(shí)候?qū)⒓拇嫫骼锏臈P畔ⅲ4娴阶约旱腉對(duì)象里面。當(dāng)再次輪到自己執(zhí)行時(shí),將自己保存的棧信息復(fù)制到寄存器里面,這樣就接著上次之后運(yùn)行了。
我這里只是根據(jù)自己的理解進(jìn)行了簡(jiǎn)單的介紹,想要詳細(xì)了解有關(guān)GMP的底層原理可以去看Go調(diào)度器 G-P-M 模型的設(shè)計(jì)者的文檔或直接看源碼
參考: ()
()
1、數(shù)組是多個(gè) 相同類型 的數(shù)據(jù)的組合,一個(gè)數(shù)組一旦聲明/定義了,其 長(zhǎng)度是固定的,不能動(dòng)態(tài)變化 。
2、var arr []int? ? 這時(shí)arr就是一個(gè)slice 切片 。
3、數(shù)組中的元素可以是任何數(shù)據(jù)類型,包括值類型和引用類型,但是 不能混用 。
4、數(shù)組創(chuàng)建后,如果沒(méi)有賦值,有默認(rèn)值如下:
? ? 數(shù)值類型數(shù)組:????默認(rèn)值為 0
? ? 字符串?dāng)?shù)組:? ? ? ?默認(rèn)值為 ""
? ? bool數(shù)組:? ? ? ? ? ?默認(rèn)值為 false
5、使用數(shù)組的步驟:
? ? (1)聲明數(shù)組并開辟空間
? ? (3)給數(shù)組各個(gè)元素賦值
? ? (3)使用數(shù)組
6、數(shù)組的下標(biāo)是從0開始的。
7、數(shù)組下標(biāo)必須在指定范圍內(nèi)使用,否則報(bào)panic:數(shù)組越界,比如var arr [5]int的有效下標(biāo)為0~4.
8、Go的數(shù)組屬于 值類型 ,在默認(rèn)情況下是 值傳遞 ,因此會(huì)進(jìn)行值拷貝。 數(shù)組間不會(huì)相互影響。
9、如想在其他函數(shù)中去修改原來(lái)的數(shù)組,可以使用 引用傳遞 (指針?lè)绞?。
10、長(zhǎng)度是數(shù)組類型的一部分,在傳遞函數(shù)參數(shù)時(shí),需要考慮數(shù)組的長(zhǎng)度,看以下案例:
題1:編譯錯(cuò)誤,因?yàn)椴荒馨裑3]int類型傳遞給[]int類型,前者是數(shù)組,后者是切片;
題2:編譯錯(cuò)誤,因?yàn)椴荒馨裑3]int類型傳遞給[4]int類型;
題3:編譯正確,因?yàn)閇3]int類型傳給[3]int類型合法。
數(shù)組是一個(gè)由 固定長(zhǎng)度 的 特定類型元素 組成的序列,一個(gè)數(shù)組可以由零個(gè)或多個(gè)元素組成。 數(shù)組是值類型
數(shù)組的每個(gè)元素都可以通過(guò)索引下標(biāo)來(lái)訪問(wèn),索引下標(biāo)的范圍是從0開始到數(shù)組長(zhǎng)度減1的位置,內(nèi)置函數(shù) len() 可以返回?cái)?shù)組中元素的個(gè)數(shù)。
2.類型的打印,結(jié)果的第二種打印方式
3.對(duì)元素的修改或者賦值
4.判斷數(shù)組是否相等:長(zhǎng)度、類型
4.數(shù)組的地址:連續(xù)存儲(chǔ)的空間
5.數(shù)組的賦值、地址、取值
6.數(shù)組的默認(rèn)值
7.數(shù)組的初始化
8.數(shù)組的逆置
9.求數(shù)組的最大值、最小值、平均值
10.對(duì)數(shù)組字符串進(jìn)行連接
11.冒泡排序法的實(shí)現(xiàn)
12.數(shù)組做函數(shù)的參數(shù)
13.二維數(shù)組:賦值和地址
14.二維數(shù)組:打印和輸出
15. 指針數(shù)組,每一個(gè)元素都是地址
17.數(shù)組的內(nèi)存分配