已經(jīng)有好多程序員都把Go語言描述為是一種所見即所得(WYSIWYG)的編程語言。這是說,代碼要做的事和它在字面上表達(dá)的意思是完全一致的。 在這些新語言中,包含D,Go,Rust和Vala語言,Go曾一度出現(xiàn)在TIOBE的排行榜上面。與其他新語言相比,Go的魅力明顯要大很多。Go的成熟特征會(huì)得到許多開發(fā)者的欣賞,而不僅僅是因?yàn)槠淇浯笃湓~的曝光度。下面我們來一起探討一下谷歌開發(fā)的Go語言以及談?wù)凣o為什么會(huì)吸引眾多開發(fā)者: 快速簡單的編譯 Go編譯速度很快,如此快速的編譯使它很容易作為腳本語言使用。關(guān)于編譯速度快主要有以下幾個(gè)原因:首先,Go不使用頭文件;其次如果一個(gè)模塊是依賴A的,這反過來又取決于B,在A里面的需求改變只需重新編譯原始模塊和與A相依賴的地方;最后,對(duì)象模塊里面包含了足夠的依賴關(guān)系信息,所以編譯器不需要重新創(chuàng)建文件。你只需要簡單地編譯主模塊,項(xiàng)目中需要的其他部分就會(huì)自動(dòng)編譯,很酷,是不是? 通過返回?cái)?shù)值列表來處理錯(cuò)誤信息 目前,在本地語言里面處理錯(cuò)誤的方式主要有兩種:直接返回代碼或者拋異常。這兩種都不是最理想的處理方式。其中返回代碼是非常令人沮喪的,因?yàn)榉祷氐腻e(cuò)誤代碼經(jīng)常與從函數(shù)中返回的數(shù)據(jù)相沖突。Go允許函數(shù)返回多個(gè)值來解決這個(gè)問題。這個(gè)從函數(shù)里面返回的值,可以用來檢查定義的類型是否正確并且可以隨時(shí)隨地對(duì)函數(shù)的返回值進(jìn)行檢查。如果你對(duì)錯(cuò)誤值不關(guān)心,你可以不必檢查。在這兩種情況下,常規(guī)的返回值都是可用的。 簡化的成分(優(yōu)先于繼承) 通過使用接口,類型是有資格成為對(duì)象中一員的,就像Java指定行為一樣。例如在標(biāo)準(zhǔn)庫里面的IO包,定義一個(gè)Writer來指定一個(gè)方法,一個(gè)Writer函數(shù),其中輸入?yún)?shù)是字節(jié)數(shù)組并且返回整數(shù)類型值或者錯(cuò)誤類型。任何類型實(shí)現(xiàn)一個(gè)帶有相同簽名的Writer方法是對(duì)IO的完全實(shí)現(xiàn),Writer接口。這種是解耦代碼而不是優(yōu)雅。它還簡化了模擬對(duì)象來進(jìn)行單元測試。例如你想在數(shù)據(jù)庫對(duì)象中測試一個(gè)方法,在標(biāo)準(zhǔn)語言中,你通常需要?jiǎng)?chuàng)建一個(gè)數(shù)據(jù)庫對(duì)象,并且需要進(jìn)行大量的初始化和協(xié)議來模擬對(duì)象。在Go里面,如果該方法需要實(shí)現(xiàn)一個(gè)接口,你可以創(chuàng)建任何對(duì)該接口有用的對(duì)象,所以,你創(chuàng)建了MockDatabase,這是很小的對(duì)象,只實(shí)現(xiàn)了幾個(gè)需要運(yùn)行和模擬的接口——沒有構(gòu)造函數(shù),沒有附件功能,只是一些方法。 簡化的并發(fā)性 相對(duì)于其他語言,并發(fā)性在Go里面顯得更加容易。把‘go’關(guān)鍵字放在任意函數(shù)前面然后那個(gè)函數(shù)就會(huì)在其go-routine自動(dòng)運(yùn)行(一個(gè)很輕的線程)。go-routines是通過通道進(jìn)行交流并且基本上封鎖了所有的隊(duì)列消息。普通工具對(duì)相互排斥是有用,但是Go通過使用通道來踢掉并發(fā)性任務(wù)和坐標(biāo)更加容易。 優(yōu)秀的錯(cuò)誤消息 所有與Go相似的語言,自身作出的診斷都是無法與Go相媲美的。例如,一個(gè)死鎖程序,在Go運(yùn)行時(shí)會(huì)通知你目前哪個(gè)線程導(dǎo)致了這種死鎖。編譯的錯(cuò)誤信息是非常詳細(xì)全面和有用的。 其他 這里還有許多其他吸引人的地方,下面就一概而過的介紹一下,比如高階函數(shù)、垃圾回收、哈希映射和可擴(kuò)展的數(shù)組內(nèi)置語言(部分語言語法,而不是作為一個(gè)庫)等等。 當(dāng)然,Go并不是完美無瑕。在工具方面還有些不成熟的地方和用戶社區(qū)較小等,但是隨著谷歌語言的不斷發(fā)展,肯定會(huì)有整治措施出來。盡管許多語言,尤其是D、Rust和Vala旨在簡化C++并且對(duì)其進(jìn)行簡化,但它們給人的感覺仍是“C++看上去要更好”。
成都創(chuàng)新互聯(lián)公司專注于站前企業(yè)網(wǎng)站建設(shè),響應(yīng)式網(wǎng)站建設(shè),商城建設(shè)。站前網(wǎng)站建設(shè)公司,為站前等地區(qū)提供建站服務(wù)。全流程按需網(wǎng)站建設(shè),專業(yè)設(shè)計(jì),全程項(xiàng)目跟蹤,成都創(chuàng)新互聯(lián)公司專業(yè)和態(tài)度為您提供的服務(wù)
【Go語言的優(yōu)勢】
可直接編譯成機(jī)器碼,不依賴其他庫,glibc的版本有一定要求,部署就是扔一個(gè)文件上去就完成了。
靜態(tài)類型語言,但是有動(dòng)態(tài)語言的感覺,靜態(tài)類型的語言就是可以在編譯的時(shí)候檢查出來隱藏的大多數(shù)問題,動(dòng)態(tài)語言的感覺就是有很多的包可以使用,寫起來的效率很高。
語言層面支持并發(fā),這個(gè)就是Go最大的特色,天生的支持并發(fā),我曾經(jīng)說過一句話,天生的基因和整容是有區(qū)別的,大家一樣美麗,但是你喜歡整容的還是天生基因的美麗呢?Go就是基因里面支持的并發(fā),可以充分的利用多核,很容易的使用并發(fā)。
內(nèi)置runtime,支持垃圾回收,這屬于動(dòng)態(tài)語言的特性之一吧,雖然目前來說GC不算完美,但是足以應(yīng)付我們所能遇到的大多數(shù)情況,特別是Go1.1之后的GC。
簡單易學(xué),Go語言的作者都有C的基因,那么Go自然而然就有了C的基因,那么Go關(guān)鍵字是25個(gè),但是表達(dá)能力很強(qiáng)大,幾乎支持大多數(shù)你在其他語言見過的特性:繼承、重載、對(duì)象等。
豐富的標(biāo)準(zhǔn)庫,Go目前已經(jīng)內(nèi)置了大量的庫,特別是網(wǎng)絡(luò)庫非常強(qiáng)大,我最愛的也是這部分。
內(nèi)置強(qiáng)大的工具,Go語言里面內(nèi)置了很多工具鏈,最好的應(yīng)該是gofmt工具,自動(dòng)化格式化代碼,能夠讓團(tuán)隊(duì)review變得如此的簡單,代碼格式一模一樣,想不一樣都很困難。
跨編譯,如果你寫的Go代碼不包含cgo,那么就可以做到window系統(tǒng)編譯linux的應(yīng)用,如何做到的呢?Go引用了plan9的代碼,這就是不依賴系統(tǒng)的信息。
內(nèi)嵌C支持,前面說了作者是C的作者,所以Go里面也可以直接包含c代碼,利用現(xiàn)有的豐富的C庫。
GO語言由Google公司開發(fā),并于2009年開源,對(duì)比Java、Python、C等語言,GO尤其擅長并發(fā)編程,性能堪比C語言,開發(fā)效率比肩Python,被譽(yù)為21世紀(jì)的C語言。GO語言在云計(jì)算、大數(shù)據(jù)、微服務(wù)、高并發(fā)領(lǐng)域,應(yīng)用非常廣泛。BAT大廠正在把GO作為新項(xiàng)目開發(fā)的首選語言。
部署簡單。Go編譯生成的是一個(gè)靜態(tài)可執(zhí)行文件,除了glibc外沒有其他外部依賴。這讓部署變得異常方便:目標(biāo)機(jī)器上只需要一個(gè)基礎(chǔ)的系統(tǒng)和必要的管理、監(jiān)控工具,完全不需要操心應(yīng)用所需的各種包、庫的依賴關(guān)系,大大減輕了維護(hù)的負(fù)擔(dān)。這和Python有著巨大的區(qū)別。由于歷史的原因,Python的部署工具生態(tài)相當(dāng)混亂【比如setuptools,distutils,pip,
buildout的不同適用場合以及兼容性問題】。官方PyPI源又經(jīng)常出問題,需要搭建私有鏡像,而維護(hù)這個(gè)鏡像又要花費(fèi)不少時(shí)間和精力。
并發(fā)性好。Goroutine和channel使得編寫高并發(fā)的服務(wù)端軟件變得相當(dāng)容易,很多情況下完全不需要考慮鎖機(jī)制以及由此帶來的各種問題。單個(gè)Go應(yīng)用也能有效的利用多個(gè)CPU核,并行執(zhí)行的性能好。這和Python也是天壤之比。多線程和多進(jìn)程的服務(wù)端程序編寫起來并不簡單,而且由于全局鎖GIL的原因,多線程的Python程序并不能有效利用多核,只能用多進(jìn)程的方式部署;如果用標(biāo)準(zhǔn)庫里的multiprocessing包又會(huì)對(duì)監(jiān)控和管理造成不少的挑戰(zhàn)【我們用的supervisor管理進(jìn)程,對(duì)fork支持不好】。部署Python應(yīng)用的時(shí)候通常是每個(gè)CPU核部署一個(gè)應(yīng)用,這會(huì)造成不少資源的浪費(fèi),比如假設(shè)某個(gè)Python應(yīng)用啟動(dòng)后需要占用100MB內(nèi)存,而服務(wù)器有32個(gè)CPU核,那么留一個(gè)核給系統(tǒng)、運(yùn)行31個(gè)應(yīng)用副本就要浪費(fèi)3GB的內(nèi)存資源。
良好的語言設(shè)計(jì)。從學(xué)術(shù)的角度講Go語言其實(shí)非常平庸,不支持許多高級(jí)的語言特性;但從工程的角度講,Go的設(shè)計(jì)是非常優(yōu)秀的:規(guī)范足夠簡單靈活,有其他語言基礎(chǔ)的程序員都能迅速上手。更重要的是Go自帶完善的工具鏈,大大提高了團(tuán)隊(duì)協(xié)作的一致性。比如gofmt自動(dòng)排版Go代碼,很大程度上杜絕了不同人寫的代碼排版風(fēng)格不一致的問題。把編輯器配置成在編輯存檔的時(shí)候自動(dòng)運(yùn)行g(shù)ofmt,這樣在編寫代碼的時(shí)候可以隨意擺放位置,存檔的時(shí)候自動(dòng)變成正確排版的代碼。此外還有g(shù)ofix,
govet等非常有用的工具。
執(zhí)行性能好。雖然不如C和Java,但通常比原生Python應(yīng)用還是高一個(gè)數(shù)量級(jí)的,適合編寫一些瓶頸業(yè)務(wù)。內(nèi)存占用也非常省。
golang方法(method)返回值提取結(jié)構(gòu)體(struct)取不到地址的原因是,①返回值并沒有保存到變量中,返回值本身只是臨時(shí)保存在程序運(yùn)行的堆棧的某個(gè)不確定位置,不能取地址;②實(shí)參取地址用的操作符是是,而形參聲明變量類型為指針,需要地址值用的才是*;③聲明形參為指針的參數(shù)的實(shí)參只能為地址值。
故先把修改后的代碼列出,修改要點(diǎn)是把“*NewPerson1().Speak()”改為“var b=NewPerson1();(b).Speak()”,同時(shí)把“NewPerson2().Speak()”改成“var a=NewPerson2();(a).Speak()”,代碼列出如下:
package main;
import "fmt";
type PersonA struct{
name string
}
func (p *PersonA) Speak () {
fmt.Println ( "person speak" ,p.name)
}
func (p PersonA) Walk ( ){
fmt . Println ( "person walk",p.name)}
func NewPerson1()(p PersonA){
return PersonA{"new Person1"}}
func NewPerson2()(p PersonA){
return PersonA{"new Person2"}}
func main () {
var a=NewPerson2 (); (a).Speak ();?
a .Walk ();
fmt. Println ("--------------------")?;
var b=NewPerson1 ();(b).Speak ();
b.Walk ()}
go代碼調(diào)試效果
關(guān)于指針變量的使用這一點(diǎn)go語言和其他有指針的程序語言如c語言是一樣的,從來只有返回值為地址/指針,而從沒有在賦值前給返回值取地址這種運(yùn)算,類似的錯(cuò)誤晚點(diǎn)再整理。
不一樣的是,go語言更簡單go語言函數(shù)可以使用結(jié)構(gòu)體或者結(jié)構(gòu)體的指針(pointer)以傳遞結(jié)構(gòu)體參數(shù),而且和c語言不一樣的是,go語言沒有區(qū)分結(jié)構(gòu)體指針和結(jié)構(gòu)體訪問成員的運(yùn)算符,go語言只有“.”適用于兩種情況,而沒有c語言為結(jié)構(gòu)體指針專門準(zhǔn)備的“-”運(yùn)算符。
可以使用結(jié)構(gòu)體指針,作為結(jié)構(gòu)體的方法的參數(shù)以指代自身嗎,
本文目錄如下,閱讀本文后,將一網(wǎng)打盡下面Golang Map相關(guān)面試題
Go中的map是一個(gè)指針,占用8個(gè)字節(jié),指向hmap結(jié)構(gòu)體; 源碼 src/runtime/map.go 中可以看到map的底層結(jié)構(gòu)
每個(gè)map的底層結(jié)構(gòu)是hmap,hmap包含若干個(gè)結(jié)構(gòu)為bmap的bucket數(shù)組。每個(gè)bucket底層都采用鏈表結(jié)構(gòu)。接下來,我們來詳細(xì)看下map的結(jié)構(gòu)
bmap 就是我們常說的“桶”,一個(gè)桶里面會(huì)最多裝 8 個(gè) key,這些 key 之所以會(huì)落入同一個(gè)桶,是因?yàn)樗鼈兘?jīng)過哈希計(jì)算后,哈希結(jié)果是“一類”的,關(guān)于key的定位我們?cè)趍ap的查詢和插入中詳細(xì)說明。在桶內(nèi),又會(huì)根據(jù) key 計(jì)算出來的 hash 值的高 8 位來決定 key 到底落入桶內(nèi)的哪個(gè)位置(一個(gè)桶內(nèi)最多有8個(gè)位置)。
bucket內(nèi)存數(shù)據(jù)結(jié)構(gòu)可視化如下:
注意到 key 和 value 是各自放在一起的,并不是 key/value/key/value/... 這樣的形式。源碼里說明這樣的好處是在某些情況下可以省略掉 padding字段,節(jié)省內(nèi)存空間。
當(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 字段來。
map是個(gè)指針,底層指向hmap,所以是個(gè)引用類型
golang 有三個(gè)常用的高級(jí)類型 slice 、map、channel, 它們都是 引用類型 ,當(dāng)引用類型作為函數(shù)參數(shù)時(shí),可能會(huì)修改原內(nèi)容數(shù)據(jù)。
golang 中沒有引用傳遞,只有值和指針傳遞。所以 map 作為函數(shù)實(shí)參傳遞時(shí)本質(zhì)上也是值傳遞,只不過因?yàn)?map 底層數(shù)據(jù)結(jié)構(gòu)是通過指針指向?qū)嶋H的元素存儲(chǔ)空間,在被調(diào)函數(shù)中修改 map,對(duì)調(diào)用者同樣可見,所以 map 作為函數(shù)實(shí)參傳遞時(shí)表現(xiàn)出了引用傳遞的效果。
因此,傳遞 map 時(shí),如果想修改map的內(nèi)容而不是map本身,函數(shù)形參無需使用指針
map 底層數(shù)據(jù)結(jié)構(gòu)是通過指針指向?qū)嶋H的元素 存儲(chǔ)空間 ,這種情況下,對(duì)其中一個(gè)map的更改,會(huì)影響到其他map
map 在沒有被修改的情況下,使用 range 多次遍歷 map 時(shí)輸出的 key 和 value 的順序可能不同。這是 Go 語言的設(shè)計(jì)者們有意為之,在每次 range 時(shí)的順序被隨機(jī)化,旨在提示開發(fā)者們,Go 底層實(shí)現(xiàn)并不保證 map 遍歷順序穩(wěn)定,請(qǐng)大家不要依賴 range 遍歷結(jié)果順序。
map 本身是無序的,且遍歷時(shí)順序還會(huì)被隨機(jī)化,如果想順序遍歷 map,需要對(duì) map key 先排序,再按照 key 的順序遍歷 map。
map默認(rèn)是并發(fā)不安全的,原因如下:
Go 官方在經(jīng)過了長時(shí)間的討論后,認(rèn)為 Go map 更應(yīng)適配典型使用場景(不需要從多個(gè) goroutine 中進(jìn)行安全訪問),而不是為了小部分情況(并發(fā)訪問),導(dǎo)致大部分程序付出加鎖代價(jià)(性能),決定了不支持。
場景: 2個(gè)協(xié)程同時(shí)讀和寫,以下程序會(huì)出現(xiàn)致命錯(cuò)誤:fatal error: concurrent map writes
如果想實(shí)現(xiàn)map線程安全,有兩種方式:
方式一:使用讀寫鎖 map + sync.RWMutex
方式二:使用golang提供的 sync.Map
sync.map是用讀寫分離實(shí)現(xiàn)的,其思想是空間換時(shí)間。和map+RWLock的實(shí)現(xiàn)方式相比,它做了一些優(yōu)化:可以無鎖訪問read map,而且會(huì)優(yōu)先操作read map,倘若只操作read map就可以滿足要求(增刪改查遍歷),那就不用去操作write map(它的讀寫都要加鎖),所以在某些特定場景中它發(fā)生鎖競爭的頻率會(huì)遠(yuǎn)遠(yuǎn)小于map+RWLock的實(shí)現(xiàn)方式。
golang中map是一個(gè)kv對(duì)集合。底層使用hash table,用鏈表來解決沖突 ,出現(xiàn)沖突時(shí),不是每一個(gè)key都申請(qǐng)一個(gè)結(jié)構(gòu)通過鏈表串起來,而是以bmap為最小粒度掛載,一個(gè)bmap可以放8個(gè)kv。在哈希函數(shù)的選擇上,會(huì)在程序啟動(dòng)時(shí),檢測 cpu 是否支持 aes,如果支持,則使用 aes hash,否則使用 memhash。
map有3鐘初始化方式,一般通過make方式創(chuàng)建
map的創(chuàng)建通過生成匯編碼可以知道,make創(chuàng)建map時(shí)調(diào)用的底層函數(shù)是 runtime.makemap 。如果你的map初始容量小于等于8會(huì)發(fā)現(xiàn)走的是 runtime.fastrand 是因?yàn)槿萘啃∮?時(shí)不需要生成多個(gè)桶,一個(gè)桶的容量就可以滿足
makemap函數(shù)會(huì)通過 fastrand 創(chuàng)建一個(gè)隨機(jī)的哈希種子,然后根據(jù)傳入的 hint 計(jì)算出需要的最小需要的桶的數(shù)量,最后再使用 makeBucketArray 創(chuàng)建用于保存桶的數(shù)組,這個(gè)方法其實(shí)就是根據(jù)傳入的 B 計(jì)算出的需要?jiǎng)?chuàng)建的桶數(shù)量在內(nèi)存中分配一片連續(xù)的空間用于存儲(chǔ)數(shù)據(jù),在創(chuàng)建桶的過程中還會(huì)額外創(chuàng)建一些用于保存溢出數(shù)據(jù)的桶,數(shù)量是 2^(B-4) 個(gè)。初始化完成返回hmap指針。
找到一個(gè) B,使得 map 的裝載因子在正常范圍內(nèi)
Go 語言中讀取 map 有兩種語法:帶 comma 和 不帶 comma。當(dāng)要查詢的 key 不在 map 里,帶 comma 的用法會(huì)返回一個(gè) bool 型變量提示 key 是否在 map 中;而不帶 comma 的語句則會(huì)返回一個(gè) value 類型的零值。如果 value 是 int 型就會(huì)返回 0,如果 value 是 string 類型,就會(huì)返回空字符串。
map的查找通過生成匯編碼可以知道,根據(jù) key 的不同類型,編譯器會(huì)將查找函數(shù)用更具體的函數(shù)替換,以優(yōu)化效率:
函數(shù)首先會(huì)檢查 map 的標(biāo)志位 flags。如果 flags 的寫標(biāo)志位此時(shí)被置 1 了,說明有其他協(xié)程在執(zhí)行“寫”操作,進(jìn)而導(dǎo)致程序 panic。這也說明了 map 對(duì)協(xié)程是不安全的。
key經(jīng)過哈希函數(shù)計(jì)算后,得到的哈希值如下(主流64位機(jī)下共 64 個(gè) bit 位):
m: 桶的個(gè)數(shù)
從buckets 通過 hash m 得到對(duì)應(yīng)的bucket,如果bucket正在擴(kuò)容,并且沒有擴(kuò)容完成,則從oldbuckets得到對(duì)應(yīng)的bucket
計(jì)算hash所在桶編號(hào):
用上一步哈希值最后的 5 個(gè) bit 位,也就是 01010 ,值為 10,也就是 10 號(hào)桶(范圍是0~31號(hào)桶)
計(jì)算hash所在的槽位:
用上一步哈希值哈希值的高8個(gè)bit 位,也就是 10010111 ,轉(zhuǎn)化為十進(jìn)制,也就是151,在 10 號(hào) bucket 中尋找** tophash 值(HOB hash)為 151* 的 槽位**,即為key所在位置,找到了 2 號(hào)槽位,這樣整個(gè)查找過程就結(jié)束了。
如果在 bucket 中沒找到,并且 overflow 不為空,還要繼續(xù)去 overflow bucket 中尋找,直到找到或是所有的 key 槽位都找遍了,包括所有的 overflow bucket。
通過上面找到了對(duì)應(yīng)的槽位,這里我們?cè)僭敿?xì)分析下key/value值是如何獲取的:
bucket 里 key 的起始地址就是 unsafe.Pointer(b)+dataOffset。第 i 個(gè) key 的地址就要在此基礎(chǔ)上跨過 i 個(gè) key 的大小;而我們又知道,value 的地址是在所有 key 之后,因此第 i 個(gè) value 的地址還需要加上所有 key 的偏移。
通過匯編語言可以看到,向 map 中插入或者修改 key,最終調(diào)用的是 mapassign 函數(shù)。
實(shí)際上插入或修改 key 的語法是一樣的,只不過前者操作的 key 在 map 中不存在,而后者操作的 key 存在 map 中。
mapassign 有一個(gè)系列的函數(shù),根據(jù) key 類型的不同,編譯器會(huì)將其優(yōu)化為相應(yīng)的“快速函數(shù)”。
我們只用研究最一般的賦值函數(shù) mapassign 。
map的賦值會(huì)附帶著map的擴(kuò)容和遷移,map的擴(kuò)容只是將底層數(shù)組擴(kuò)大了一倍,并沒有進(jìn)行數(shù)據(jù)的轉(zhuǎn)移,數(shù)據(jù)的轉(zhuǎn)移是在擴(kuò)容后逐步進(jìn)行的,在遷移的過程中每進(jìn)行一次賦值(access或者delete)會(huì)至少做一次遷移工作。
1.判斷map是否為nil
每一次進(jìn)行賦值/刪除操作時(shí),只要oldbuckets != nil 則認(rèn)為正在擴(kuò)容,會(huì)做一次遷移工作,下面會(huì)詳細(xì)說下遷移過程
根據(jù)上面查找過程,查找key所在位置,如果找到則更新,沒找到則找空位插入即可
經(jīng)過前面迭代尋找動(dòng)作,若沒有找到可插入的位置,意味著需要擴(kuò)容進(jìn)行插入,下面會(huì)詳細(xì)說下擴(kuò)容過程
通過匯編語言可以看到,向 map 中刪除 key,最終調(diào)用的是 mapdelete 函數(shù)
刪除的邏輯相對(duì)比較簡單,大多函數(shù)在賦值操作中已經(jīng)用到過,核心還是找到 key 的具體位置。尋找過程都是類似的,在 bucket 中挨個(gè) cell 尋找。找到對(duì)應(yīng)位置后,對(duì) key 或者 value 進(jìn)行“清零”操作,將 count 值減 1,將對(duì)應(yīng)位置的 tophash 值置成 Empty
再來說觸發(fā) map 擴(kuò)容的時(shí)機(jī):在向 map 插入新 key 的時(shí)候,會(huì)進(jìn)行條件檢測,符合下面這 2 個(gè)條件,就會(huì)觸發(fā)擴(kuò)容:
1、裝載因子超過閾值
源碼里定義的閾值是 6.5 (loadFactorNum/loadFactorDen),是經(jīng)過測試后取出的一個(gè)比較合理的因子
我們知道,每個(gè) bucket 有 8 個(gè)空位,在沒有溢出,且所有的桶都裝滿了的情況下,裝載因子算出來的結(jié)果是 8。因此當(dāng)裝載因子超過 6.5 時(shí),表明很多 bucket 都快要裝滿了,查找效率和插入效率都變低了。在這個(gè)時(shí)候進(jìn)行擴(kuò)容是有必要的。
對(duì)于條件 1,元素太多,而 bucket 數(shù)量太少,很簡單:將 B 加 1,bucket 最大數(shù)量( 2^B )直接變成原來 bucket 數(shù)量的 2 倍。于是,就有新老 bucket 了。注意,這時(shí)候元素都在老 bucket 里,還沒遷移到新的 bucket 來。新 bucket 只是最大數(shù)量變?yōu)樵瓉碜畲髷?shù)量的 2 倍( 2^B * 2 ) 。
2、overflow 的 bucket 數(shù)量過多
在裝載因子比較小的情況下,這時(shí)候 map 的查找和插入效率也很低,而第 1 點(diǎn)識(shí)別不出來這種情況。表面現(xiàn)象就是計(jì)算裝載因子的分子比較小,即 map 里元素總數(shù)少,但是 bucket 數(shù)量多(真實(shí)分配的 bucket 數(shù)量多,包括大量的 overflow bucket)
不難想像造成這種情況的原因:不停地插入、刪除元素。先插入很多元素,導(dǎo)致創(chuàng)建了很多 bucket,但是裝載因子達(dá)不到第 1 點(diǎn)的臨界值,未觸發(fā)擴(kuò)容來緩解這種情況。之后,刪除元素降低元素總數(shù)量,再插入很多元素,導(dǎo)致創(chuàng)建很多的 overflow bucket,但就是不會(huì)觸發(fā)第 1 點(diǎn)的規(guī)定,你能拿我怎么辦?overflow bucket 數(shù)量太多,導(dǎo)致 key 會(huì)很分散,查找插入效率低得嚇人,因此出臺(tái)第 2 點(diǎn)規(guī)定。這就像是一座空城,房子很多,但是住戶很少,都分散了,找起人來很困難
對(duì)于條件 2,其實(shí)元素沒那么多,但是 overflow bucket 數(shù)特別多,說明很多 bucket 都沒裝滿。解決辦法就是開辟一個(gè)新 bucket 空間,將老 bucket 中的元素移動(dòng)到新 bucket,使得同一個(gè) bucket 中的 key 排列地更緊密。這樣,原來,在 overflow bucket 中的 key 可以移動(dòng)到 bucket 中來。結(jié)果是節(jié)省空間,提高 bucket 利用率,map 的查找和插入效率自然就會(huì)提升。
由于 map 擴(kuò)容需要將原有的 key/value 重新搬遷到新的內(nèi)存地址,如果有大量的 key/value 需要搬遷,會(huì)非常影響性能。因此 Go map 的擴(kuò)容采取了一種稱為“漸進(jìn)式”的方式,原有的 key 并不會(huì)一次性搬遷完畢,每次最多只會(huì)搬遷 2 個(gè) bucket。
上面說的 hashGrow() 函數(shù)實(shí)際上并沒有真正地“搬遷”,它只是分配好了新的 buckets,并將老的 buckets 掛到了 oldbuckets 字段上。真正搬遷 buckets 的動(dòng)作在 growWork() 函數(shù)中,而調(diào)用 growWork() 函數(shù)的動(dòng)作是在 mapassign 和 mapdelete 函數(shù)中。也就是插入或修改、刪除 key 的時(shí)候,都會(huì)嘗試進(jìn)行搬遷 buckets 的工作。先檢查 oldbuckets 是否搬遷完畢,具體來說就是檢查 oldbuckets 是否為 nil。
如果未遷移完畢,賦值/刪除的時(shí)候,擴(kuò)容完畢后(預(yù)分配內(nèi)存),不會(huì)馬上就進(jìn)行遷移。而是采取 增量擴(kuò)容 的方式,當(dāng)有訪問到具體 bukcet 時(shí),才會(huì)逐漸的進(jìn)行遷移(將 oldbucket 遷移到 bucket)
nevacuate 標(biāo)識(shí)的是當(dāng)前的進(jìn)度,如果都搬遷完,應(yīng)該和2^B的長度是一樣的
在evacuate 方法實(shí)現(xiàn)是把這個(gè)位置對(duì)應(yīng)的bucket,以及其沖突鏈上的數(shù)據(jù)都轉(zhuǎn)移到新的buckets上。
轉(zhuǎn)移的判斷直接通過tophash 就可以,判斷tophash中第一個(gè)hash值即可
遍歷的過程,就是按順序遍歷 bucket,同時(shí)按順序遍歷 bucket 中的 key。
map遍歷是無序的,如果想實(shí)現(xiàn)有序遍歷,可以先對(duì)key進(jìn)行排序
為什么遍歷 map 是無序的?
如果發(fā)生過遷移,key 的位置發(fā)生了重大的變化,有些 key 飛上高枝,有些 key 則原地不動(dòng)。這樣,遍歷 map 的結(jié)果就不可能按原來的順序了。
如果就一個(gè)寫死的 map,不會(huì)向 map 進(jìn)行插入刪除的操作,按理說每次遍歷這樣的 map 都會(huì)返回一個(gè)固定順序的 key/value 序列吧。但是 Go 杜絕了這種做法,因?yàn)檫@樣會(huì)給新手程序員帶來誤解,以為這是一定會(huì)發(fā)生的事情,在某些情況下,可能會(huì)釀成大錯(cuò)。
Go 做得更絕,當(dāng)我們?cè)诒闅v map 時(shí),并不是固定地從 0 號(hào) bucket 開始遍歷,每次都是從一個(gè)**隨機(jī)值序號(hào)的 bucket 開始遍歷,并且是從這個(gè) bucket 的一個(gè) 隨機(jī)序號(hào)的 cell **開始遍歷。這樣,即使你是一個(gè)寫死的 map,僅僅只是遍歷它,也不太可能會(huì)返回一個(gè)固定序列的 key/value 對(duì)了。