goland map底層原理

map 是Go語言中基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)，在日常的使用中經(jīng)常被用到。但是它底層是如何實現(xiàn)的呢？

站在用戶的角度思考問題，與客戶深入溝通，找到濟源網(wǎng)站設(shè)計與濟源網(wǎng)站推廣的解決方案，憑借多年的經(jīng)驗，讓設(shè)計與互聯(lián)網(wǎng)技術(shù)結(jié)合，創(chuàng)造個性化、用戶體驗好的作品，建站類型包括：成都網(wǎng)站制作、做網(wǎng)站、企業(yè)官網(wǎng)、英文網(wǎng)站、手機端網(wǎng)站、網(wǎng)站推廣、空間域名、虛擬主機、企業(yè)郵箱。業(yè)務(wù)覆蓋濟源地區(qū)。

總體來說golang的map是hashmap，是使用數(shù)組+鏈表的形式實現(xiàn)的，使用拉鏈法消除hash沖突。

golang的map由兩種重要的結(jié)構(gòu)，hmap和bmap(下文中都有解釋)，主要就是hmap中包含一個指向bmap數(shù)組的指針，key經(jīng)過hash函數(shù)之后得到一個數(shù)，這個數(shù)低位用于選擇bmap(當作bmap數(shù)組指針的下表)，高位用于放在bmap的[8]uint8數(shù)組中，用于快速試錯。然后一個bmap可以指向下一個bmap(拉鏈)。

Golang中map的底層實現(xiàn)是一個散列表，因此實現(xiàn)map的過程實際上就是實現(xiàn)散表的過程。在這個散列表中，主要出現(xiàn)的結(jié)構(gòu)體有兩個，一個叫 hmap (a header for a go map)，一個叫 bmap (a bucket for a Go map，通常叫其bucket)。這兩種結(jié)構(gòu)的樣子分別如下所示：

hmap :

圖中有很多字段，但是便于理解map的架構(gòu)，你只需要關(guān)心的只有一個，就是標紅的字段： buckets數(shù)組 。Golang的map中用于存儲的結(jié)構(gòu)是bucket數(shù)組。而bucket(即bmap)的結(jié)構(gòu)是怎樣的呢？

bucket ：

相比于hmap，bucket的結(jié)構(gòu)顯得簡單一些，標紅的字段依然是“核心”，我們使用的map中的key和value就存儲在這里。“高位哈希值”數(shù)組記錄的是當前bucket中key相關(guān)的“索引”，稍后會詳細敘述。還有一個字段是一個指向擴容后的bucket的指針，使得bucket會形成一個鏈表結(jié)構(gòu)。例如下圖：

由此看出hmap和bucket的關(guān)系是這樣的：

而bucket又是一個鏈表，所以，整體的結(jié)構(gòu)應(yīng)該是這樣的：

哈希表的特點是會有一個哈希函數(shù)，對你傳來的key進行哈希運算，得到唯一的值，一般情況下都是一個數(shù)值。Golang的map中也有這么一個哈希函數(shù)，也會算出唯一的值，對于這個值的使用，Golang也是很有意思。

Golang把求得的值按照用途一分為二：高位和低位。

如圖所示，藍色為高位，紅色為低位。 然后低位用于尋找當前key屬于hmap中的哪個bucket，而高位用于尋找bucket中的哪個key。上文中提到：bucket中有個屬性字段是“高位哈希值”數(shù)組，這里存的就是藍色的高位值，用來聲明當前bucket中有哪些“key”，便于搜索查找。 需要特別指出的一點是：我們map中的key/value值都是存到同一個數(shù)組中的。數(shù)組中的順序是這樣的:

并不是key0/value0/key1/value1的形式，這樣做的好處是：在key和value的長度不同的時候，可 以消除padding(內(nèi)存對齊)帶來的空間浪費 。

現(xiàn)在，我們可以得到Go語言map的整個的結(jié)構(gòu)圖了：(hash結(jié)果的低位用于選擇把KV放在bmap數(shù)組中的哪一個bmap中，高位用于key的快速預覽，用于快速試錯)

map的擴容

當以上的哈希表增長的時候，Go語言會將bucket數(shù)組的數(shù)量擴充一倍，產(chǎn)生一個新的bucket數(shù)組，并將舊數(shù)組的數(shù)據(jù)遷移至新數(shù)組。

加載因子

判斷擴充的條件，就是哈希表中的加載因子(即loadFactor)。

加載因子是一個閾值，一般表示為：散列包含的元素數(shù) 除以 位置總數(shù)。是一種“產(chǎn)生沖突機會”和“空間使用”的平衡與折中：加載因子越小，說明空間空置率高，空間使用率小，但是加載因子越大，說明空間利用率上去了，但是“產(chǎn)生沖突機會”高了。

每種哈希表的都會有一個加載因子，數(shù)值超過加載因子就會為哈希表擴容。

Golang的map的加載因子的公式是：map長度 / 2^B(這是代表bmap數(shù)組的長度，B是取的低位的位數(shù))閾值是6.5。其中B可以理解為已擴容的次數(shù)。

當Go的map長度增長到大于加載因子所需的map長度時，Go語言就會將產(chǎn)生一個新的bucket數(shù)組，然后把舊的bucket數(shù)組移到一個屬性字段oldbucket中。注意：并不是立刻把舊的數(shù)組中的元素轉(zhuǎn)義到新的bucket當中，而是，只有當訪問到具體的某個bucket的時候，會把bucket中的數(shù)據(jù)轉(zhuǎn)移到新的bucket中。

如下圖所示：當擴容的時候，Go的map結(jié)構(gòu)體中，會保存舊的數(shù)據(jù)，和新生成的數(shù)組

上面部分代表舊的有數(shù)據(jù)的bucket，下面部分代表新生成的新的bucket。藍色代表存有數(shù)據(jù)的bucket，橘黃色代表空的bucket。

擴容時map并不會立即把新數(shù)據(jù)做遷移，而是當訪問原來舊bucket的數(shù)據(jù)的時候，才把舊數(shù)據(jù)做遷移，如下圖：

注意：這里并不會直接刪除舊的bucket，而是把原來的引用去掉，利用GC清除內(nèi)存。

map中數(shù)據(jù)的刪除

如果理解了map的整體結(jié)構(gòu)，那么查找、更新、刪除的基本步驟應(yīng)該都很清楚了。這里不再贅述。

值得注意的是，找到了map中的數(shù)據(jù)之后，針對key和value分別做如下操作：

1

2

3

4

1、如果``key``是一個指針類型的，則直接將其置為空，等待GC清除；

2、如果是值類型的，則清除相關(guān)內(nèi)存。

3、同理，對``value``做相同的操作。

4、最后把key對應(yīng)的高位值對應(yīng)的數(shù)組index置為空。

Go語言和其他語言的不同之基本語法

Go語言作為出現(xiàn)比較晚的一門編程語言，在其原生支持高并發(fā)、云原生等領(lǐng)域的優(yōu)秀表現(xiàn)，像目前比較流行的容器編排技術(shù)Kubernetes、容器技術(shù)Docker都是用Go語言寫的，像Java等其他面向?qū)ο蟮恼Z言，雖然也能做云原生相關(guān)的開發(fā)，但是支持的程度遠沒有Go語言高，憑借其語言特性和簡單的編程方式，彌補了其他編程語言一定程度上的不足，一度成為一個熱門的編程語言。

最近在學習Go語言，我之前使用過C#、Java等面向?qū)ο缶幊痰恼Z言，發(fā)現(xiàn)其中有很多的編程方式和其他語言有區(qū)別的地方，好記性不如爛筆頭，總結(jié)一下，和其他語言做個對比。這里只總結(jié)差異的地方，具體的語法不做詳細的介紹。

種一棵樹最好的時間是十年前，其次是現(xiàn)在。

3)變量初始化時候可以和其他語言一樣直接在變量后面加等號，等號后面為要初始化的值，也可以使用變量名：=變量值的簡單方式

3）變量賦值 Go語言的變量賦值和多數(shù)語言一致，但是Go語言提供了多重賦值的功能，比如下面這個交換i、j變量的語句：

在不支持多重賦值的語言中，交換兩個變量的值需要引入一個中間變量：

4)匿名變量

在使用其他語言時，有時候要獲取一個值，卻因為該函數(shù)返回多個值而不得不定義很多沒有的變量，Go語言可以借助多重返回值和匿名變量來避免這種寫法，使代碼看起來更優(yōu)雅。

假如GetName()函數(shù)返回3個值，分別是firstName,lastName和nickName

若指向獲得nickName，則函數(shù)調(diào)用可以這樣寫

這種寫法可以讓代碼更清晰，從而大幅降低溝通的復雜度和維護的難度。

1）基本常量

常量使用關(guān)鍵字const 定義，可以限定常量類型，但不是必須的，如果沒有定義常量的類型，是無類型常量

2）預定義常量

Go語言預定義了這些常量 true、false和iota

iota比較特殊，可以被任務(wù)是一個可被編譯器修改的常量，在每個const關(guān)鍵字出現(xiàn)時被重置為0，然后在下一個const出現(xiàn)之前每出現(xiàn)一個iota，其所代表的數(shù)字會自動加1.

3)枚舉

1）int 和int32在Go語言中被認為是兩種不同類型的類型

2）Go語言定義了兩個浮點型float32和float64，其中前者等價于C語言的float類型，后者等價于C語言的double類型

3）go語言支持復數(shù)類型

復數(shù)實際上是由兩個實數(shù)（在計算機中使用浮點數(shù)表示）構(gòu)成，一個表示實部（real）、一個表示虛部（imag）。也就是數(shù)學上的那個復數(shù)

復數(shù)的表示

實部與虛部

對于一個復數(shù)z=complex(x,y),就可以通過Go語言內(nèi)置函數(shù)real(z)獲得該復數(shù)的實部，也就是x，通過imag(z)獲得該復數(shù)的虛部，也就是y

4）數(shù)組(值類型，長度在定義后無法再次修改，每次傳遞都將產(chǎn)生一個副本。)

5）數(shù)組切片（slice）

數(shù)組切片（slice）彌補了數(shù)組的不足，其數(shù)據(jù)結(jié)構(gòu)可以抽象為以下三個變量：

6）Map 在go語言中Map不需要引入任何庫，使用很方便

Go循環(huán)語句只支持for關(guān)鍵字，不支持while和do-while

goto語句的語義非常簡單，就是跳轉(zhuǎn)到本函數(shù)內(nèi)的某個標簽

今天就介紹到這里，以后我會在總結(jié)Go語言在其他方面比如并發(fā)編程、面向?qū)ο蟆⒕W(wǎng)絡(luò)編程等方面的不同及使用方法。希望對大家有所幫助。

Go語言——sync.Map詳解

sync.Map是1.9才推薦的并發(fā)安全的map，除了互斥量以外，還運用了原子操作，所以在這之前，有必要了解下 Go語言——原子操作

go1.10\src\sync\map.go

entry分為三種情況：

從read中讀取key，如果key存在就tryStore。

注意這里開始需要加鎖，因為需要操作dirty。

條目在read中，首先取消標記，然后將條目保存到dirty里。（因為標記的數(shù)據(jù)不在dirty里）

最后原子保存value到條目里面，這里注意read和dirty都有條目。

總結(jié)一下Store：

這里可以看到dirty保存了數(shù)據(jù)的修改，除非可以直接原子更新read，繼續(xù)保持read clean。

有了之前的經(jīng)驗，可以猜測下load流程：

與猜測的 區(qū)別 ：

由于數(shù)據(jù)保存兩份，所以刪除考慮：

先看第二種情況。加鎖直接刪除dirty數(shù)據(jù)。思考下貌似沒什么問題，本身就是臟數(shù)據(jù)。

第一種和第三種情況唯一的區(qū)別就是條目是否被標記。標記代表刪除，所以直接返回。否則CAS操作置為nil。這里總感覺少點什么，因為條目其實還是存在的，雖然指針nil。

看了一圈貌似沒找到標記的邏輯，因為刪除只是將他變成nil。

之前以為這個邏輯就是簡單的將為標記的條目拷貝給dirty，現(xiàn)在看來大有文章。

p == nil，說明條目已經(jīng)被delete了，CAS將他置為標記刪除。然后這個條目就不會保存在dirty里面。

這里其實就跟miss邏輯串起來了，因為miss達到閾值之后，dirty會全量變成read，也就是說標記刪除在這一步最終刪除。這個還是很巧妙的。

真正的刪除邏輯：

很繞。。。。

當前文章：go語言map的定義 go的map實現(xiàn)
鏈接URL：http://jinyejixie.com/article44/dosgche.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供外貿(mào)建站、面包屑導航、外貿(mào)網(wǎng)站建設(shè)、定制網(wǎng)站、網(wǎng)頁設(shè)計公司、自適應(yīng)網(wǎng)站

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)