別的不說,直接上代碼
創新互聯建站成立與2013年,是專業互聯網技術服務公司,擁有項目網站建設、成都網站制作網站策劃,項目實施與項目整合能力。我們以讓每一個夢想脫穎而出為使命,1280元霍邱做網站,已為上家服務,為霍邱各地企業和個人服務,聯系電話:13518219792
user:=make(map[string]string)
user["wang"]="王"
if?user["wang"]!=""{
print("存在")
}
if?_,ok:=user["wang"];ok{
print("存在")
}
不知道你有沒有聽過這么一句:在使用 map 時盡量不要在 big map 中保存指針。好吧,你現在已經聽過了:)為什么呢?原因在于 Go 語言的垃圾回收器會掃描標記 map 中的所有元素,GC 開銷相當大,直接GG。
這兩天在《Mastering Go》中看到 GC 這一章節里面對比 map 和 slice 在垃圾回收中的效率對比,書中只給出結論沒有說明理由,這我是不能忍的,于是有了這篇學習筆記。扯那么多,Show Your Code
這是一個簡單的測試程序,保存字符串的 map 和 保存整形的 map GC 的效率相差幾十倍,是不是有同學會說明明保存的是 string 哪有指針?這個要說到 Go 語言中 string 的底層實現了,源碼在 src/runtime/string.go里,可以看到 string 其實包含一個指向數據的指針和一個長度字段。注意這里的是否包含指針,包括底層的實現。
Go 語言的 GC 會遞歸遍歷并標記所有可觸達的對象,標記完成之后將所有沒有引用的對象進行清理。掃描到指針就會往下接著尋找,一直到結束。
Go 語言中 map 是基于 數組和鏈表 的數據結構實現的,通過 優化的拉鏈法 解決哈希沖突,每個 bucket 可以保存 8 對鍵值,在 8 個鍵值對數據后面有一個 overflow 指針,因為桶中最多只能裝 8 個鍵值對,如果有多余的鍵值對落到了當前桶,那么就需要再構建一個桶(稱為溢出桶),通過 overflow 指針鏈接起來。
因為 overflow 指針的緣故,所以無論 map 保存的是什么,GC 的時候就會把所有的 bmap 掃描一遍,帶來巨大的 GC 開銷。官方 issues 就有關于這個問題的討論, runtime: Large maps cause significant GC pauses #9477
無腦機翻如下:
如果我們有一個map [k] v,其中k和v都不包含指針,并且我們想提高掃描性能,則可以執行以下操作。
將“ allOverflow [] unsafe.Pointer”添加到 hmap 并將所有溢出存儲桶存儲在其中。 然后將 bmap 標記為noScan。 這將使掃描非??欤驗槲覀儾粫呙枞魏斡脩魯祿?/p>
實際上,它將有些復雜,因為我們需要從allOverflow中刪除舊的溢出桶。 而且它還會增加 hmap 的大小,因此也可能需要重新整理數據。
最終官方在 hmap 中增加了 overflow 相關字段完成了上面的優化,這是具體的 commit 地址。
下面看下具體是如何實現的,源碼基于 go1.15,src/cmd/compile/internal/gc/reflect.go 中
通過注釋可以看出,如果 map 中保存的鍵值都不包含指針(通過 Haspointers 判斷),就使用一個 uintptr 類型代替 bucket 的指針用于溢出桶 overflow 字段,uintptr 類型在 GO 語言中就是個大小可以保存得下指針的整數,不是指針,就相當于實現了 將 bmap 標記為 noScan, GC 的時候就不會遍歷完整個 map 了。隨著不斷的學習,愈發感慨 GO 語言中很多模塊設計得太精妙了。
差不多說清楚了,能力有限,有不對的地方歡迎留言討論,源碼位置還是問的群里大佬 _
map 是Go語言中基礎的數據結構,在日常的使用中經常被用到。但是它底層是如何實現的呢?
總體來說golang的map是hashmap,是使用數組+鏈表的形式實現的,使用拉鏈法消除hash沖突。
golang的map由兩種重要的結構,hmap和bmap(下文中都有解釋),主要就是hmap中包含一個指向bmap數組的指針,key經過hash函數之后得到一個數,這個數低位用于選擇bmap(當作bmap數組指針的下表),高位用于放在bmap的[8]uint8數組中,用于快速試錯。然后一個bmap可以指向下一個bmap(拉鏈)。
Golang中map的底層實現是一個散列表,因此實現map的過程實際上就是實現散表的過程。在這個散列表中,主要出現的結構體有兩個,一個叫 hmap (a header for a go map),一個叫 bmap (a bucket for a Go map,通常叫其bucket)。這兩種結構的樣子分別如下所示:
hmap :
圖中有很多字段,但是便于理解map的架構,你只需要關心的只有一個,就是標紅的字段: buckets數組 。Golang的map中用于存儲的結構是bucket數組。而bucket(即bmap)的結構是怎樣的呢?
bucket :
相比于hmap,bucket的結構顯得簡單一些,標紅的字段依然是“核心”,我們使用的map中的key和value就存儲在這里?!案呶还V怠睌到M記錄的是當前bucket中key相關的“索引”,稍后會詳細敘述。還有一個字段是一個指向擴容后的bucket的指針,使得bucket會形成一個鏈表結構。例如下圖:
由此看出hmap和bucket的關系是這樣的:
而bucket又是一個鏈表,所以,整體的結構應該是這樣的:
哈希表的特點是會有一個哈希函數,對你傳來的key進行哈希運算,得到唯一的值,一般情況下都是一個數值。Golang的map中也有這么一個哈希函數,也會算出唯一的值,對于這個值的使用,Golang也是很有意思。
Golang把求得的值按照用途一分為二:高位和低位。
如圖所示,藍色為高位,紅色為低位。 然后低位用于尋找當前key屬于hmap中的哪個bucket,而高位用于尋找bucket中的哪個key。上文中提到:bucket中有個屬性字段是“高位哈希值”數組,這里存的就是藍色的高位值,用來聲明當前bucket中有哪些“key”,便于搜索查找。 需要特別指出的一點是:我們map中的key/value值都是存到同一個數組中的。數組中的順序是這樣的:
并不是key0/value0/key1/value1的形式,這樣做的好處是:在key和value的長度不同的時候,可 以消除padding(內存對齊)帶來的空間浪費 。
現在,我們可以得到Go語言map的整個的結構圖了:(hash結果的低位用于選擇把KV放在bmap數組中的哪一個bmap中,高位用于key的快速預覽,用于快速試錯)
map的擴容
當以上的哈希表增長的時候,Go語言會將bucket數組的數量擴充一倍,產生一個新的bucket數組,并將舊數組的數據遷移至新數組。
加載因子
判斷擴充的條件,就是哈希表中的加載因子(即loadFactor)。
加載因子是一個閾值,一般表示為:散列包含的元素數 除以 位置總數。是一種“產生沖突機會”和“空間使用”的平衡與折中:加載因子越小,說明空間空置率高,空間使用率小,但是加載因子越大,說明空間利用率上去了,但是“產生沖突機會”高了。
每種哈希表的都會有一個加載因子,數值超過加載因子就會為哈希表擴容。
Golang的map的加載因子的公式是:map長度 / 2^B(這是代表bmap數組的長度,B是取的低位的位數)閾值是6.5。其中B可以理解為已擴容的次數。
當Go的map長度增長到大于加載因子所需的map長度時,Go語言就會將產生一個新的bucket數組,然后把舊的bucket數組移到一個屬性字段oldbucket中。注意:并不是立刻把舊的數組中的元素轉義到新的bucket當中,而是,只有當訪問到具體的某個bucket的時候,會把bucket中的數據轉移到新的bucket中。
如下圖所示:當擴容的時候,Go的map結構體中,會保存舊的數據,和新生成的數組
上面部分代表舊的有數據的bucket,下面部分代表新生成的新的bucket。藍色代表存有數據的bucket,橘黃色代表空的bucket。
擴容時map并不會立即把新數據做遷移,而是當訪問原來舊bucket的數據的時候,才把舊數據做遷移,如下圖:
注意:這里并不會直接刪除舊的bucket,而是把原來的引用去掉,利用GC清除內存。
map中數據的刪除
如果理解了map的整體結構,那么查找、更新、刪除的基本步驟應該都很清楚了。這里不再贅述。
值得注意的是,找到了map中的數據之后,針對key和value分別做如下操作:
1
2
3
4
1、如果``key``是一個指針類型的,則直接將其置為空,等待GC清除;
2、如果是值類型的,則清除相關內存。
3、同理,對``value``做相同的操作。
4、最后把key對應的高位值對應的數組index置為空。
前面,我們講了map的用法以及原理 Golang中map的實現原理 ,但我們知道,map在并發讀寫的情況下是不安全。需要并發讀寫時,一般的做法是加鎖,但這樣性能并不高,Go語言在 1.9 版本中提供了一種效率較高的并發安全的 sync.Map,今天,我們就來講講 sync.Map的用法以及原理
sync.Map與map不同,不是以語言原生形態提供,而是在 sync 包下的特殊結構:
我們下來看下sync.Map結構體
結構體之間的關系如下圖所示:
總結一下:
Load方法比較簡單,總結一下:
總結如下:
sync.Map是1.9才推薦的并發安全的map,除了互斥量以外,還運用了原子操作,所以在這之前,有必要了解下 Go語言——原子操作
go1.10\src\sync\map.go
entry分為三種情況:
從read中讀取key,如果key存在就tryStore。
注意這里開始需要加鎖,因為需要操作dirty。
條目在read中,首先取消標記,然后將條目保存到dirty里。(因為標記的數據不在dirty里)
最后原子保存value到條目里面,這里注意read和dirty都有條目。
總結一下Store:
這里可以看到dirty保存了數據的修改,除非可以直接原子更新read,繼續保持read clean。
有了之前的經驗,可以猜測下load流程:
與猜測的 區別 :
由于數據保存兩份,所以刪除考慮:
先看第二種情況。加鎖直接刪除dirty數據。思考下貌似沒什么問題,本身就是臟數據。
第一種和第三種情況唯一的區別就是條目是否被標記。標記代表刪除,所以直接返回。否則CAS操作置為nil。這里總感覺少點什么,因為條目其實還是存在的,雖然指針nil。
看了一圈貌似沒找到標記的邏輯,因為刪除只是將他變成nil。
之前以為這個邏輯就是簡單的將為標記的條目拷貝給dirty,現在看來大有文章。
p == nil,說明條目已經被delete了,CAS將他置為標記刪除。然后這個條目就不會保存在dirty里面。
這里其實就跟miss邏輯串起來了,因為miss達到閾值之后,dirty會全量變成read,也就是說標記刪除在這一步最終刪除。這個還是很巧妙的。
真正的刪除邏輯:
很繞。。。。
網站題目:go語言map源碼 go map原理
網頁地址:http://m.newbst.com/article22/docpocc.html
成都網站建設公司_創新互聯,為您提供網站改版、微信小程序、搜索引擎優化、外貿建站、App開發、網站收錄
聲明:本網站發布的內容(圖片、視頻和文字)以用戶投稿、用戶轉載內容為主,如果涉及侵權請盡快告知,我們將會在第一時間刪除。文章觀點不代表本網站立場,如需處理請聯系客服。電話:028-86922220;郵箱:631063699@qq.com。內容未經允許不得轉載,或轉載時需注明來源: 創新互聯