徹底理解Golang Map

本文目錄如下，閱讀本文后，將一網打盡下面Golang Map相關面試題

興賓網站制作公司哪家好，找創新互聯！從網頁設計、網站建設、微信開發、APP開發、成都響應式網站建設公司等網站項目制作，到程序開發，運營維護。創新互聯于2013年開始到現在10年的時間，我們擁有了豐富的建站經驗和運維經驗，來保證我們的工作的順利進行。專注于網站建設就選創新互聯。

Go中的map是一個指針，占用8個字節，指向hmap結構體; 源碼 src/runtime/map.go 中可以看到map的底層結構

每個map的底層結構是hmap，hmap包含若干個結構為bmap的bucket數組。每個bucket底層都采用鏈表結構。接下來，我們來詳細看下map的結構

bmap 就是我們常說的“桶”，一個桶里面會最多裝 8 個 key，這些 key 之所以會落入同一個桶，是因為它們經過哈希計算后，哈希結果是“一類”的，關于key的定位我們在map的查詢和插入中詳細說明。在桶內，又會根據 key 計算出來的 hash 值的高 8 位來決定 key 到底落入桶內的哪個位置（一個桶內最多有8個位置)。

bucket內存數據結構可視化如下：

注意到 key 和 value 是各自放在一起的，并不是 key/value/key/value/... 這樣的形式。源碼里說明這樣的好處是在某些情況下可以省略掉 padding字段，節省內存空間。

當 map 的 key 和 value 都不是指針，并且 size 都小于 128 字節的情況下，會把 bmap 標記為不含指針，這樣可以避免 gc 時掃描整個 hmap。但是，我們看 bmap 其實有一個 overflow 的字段，是指針類型的，破壞了 bmap 不含指針的設想，這時會把 overflow 移動到 extra 字段來。

map是個指針，底層指向hmap，所以是個引用類型

golang 有三個常用的高級類型 slice 、map、channel, 它們都是 引用類型 ，當引用類型作為函數參數時，可能會修改原內容數據。

golang 中沒有引用傳遞，只有值和指針傳遞。所以 map 作為函數實參傳遞時本質上也是值傳遞，只不過因為 map 底層數據結構是通過指針指向實際的元素存儲空間，在被調函數中修改 map，對調用者同樣可見，所以 map 作為函數實參傳遞時表現出了引用傳遞的效果。

因此，傳遞 map 時，如果想修改map的內容而不是map本身，函數形參無需使用指針

map 底層數據結構是通過指針指向實際的元素 存儲空間 ，這種情況下，對其中一個map的更改，會影響到其他map

map 在沒有被修改的情況下，使用 range 多次遍歷 map 時輸出的 key 和 value 的順序可能不同。這是 Go 語言的設計者們有意為之，在每次 range 時的順序被隨機化，旨在提示開發者們，Go 底層實現并不保證 map 遍歷順序穩定，請大家不要依賴 range 遍歷結果順序。

map 本身是無序的，且遍歷時順序還會被隨機化，如果想順序遍歷 map，需要對 map key 先排序，再按照 key 的順序遍歷 map。

map默認是并發不安全的，原因如下：

Go 官方在經過了長時間的討論后，認為 Go map 更應適配典型使用場景（不需要從多個 goroutine 中進行安全訪問），而不是為了小部分情況（并發訪問），導致大部分程序付出加鎖代價（性能），決定了不支持。

場景: 2個協程同時讀和寫，以下程序會出現致命錯誤：fatal error: concurrent map writes

如果想實現map線程安全，有兩種方式：

方式一：使用讀寫鎖 map + sync.RWMutex

方式二：使用golang提供的 sync.Map

sync.map是用讀寫分離實現的，其思想是空間換時間。和map+RWLock的實現方式相比，它做了一些優化：可以無鎖訪問read map，而且會優先操作read map，倘若只操作read map就可以滿足要求(增刪改查遍歷)，那就不用去操作write map(它的讀寫都要加鎖)，所以在某些特定場景中它發生鎖競爭的頻率會遠遠小于map+RWLock的實現方式。

golang中map是一個kv對集合。底層使用hash table，用鏈表來解決沖突 ，出現沖突時，不是每一個key都申請一個結構通過鏈表串起來，而是以bmap為最小粒度掛載，一個bmap可以放8個kv。在哈希函數的選擇上，會在程序啟動時，檢測 cpu 是否支持 aes，如果支持，則使用 aes hash，否則使用 memhash。

map有3鐘初始化方式，一般通過make方式創建

map的創建通過生成匯編碼可以知道，make創建map時調用的底層函數是 runtime.makemap 。如果你的map初始容量小于等于8會發現走的是 runtime.fastrand 是因為容量小于8時不需要生成多個桶，一個桶的容量就可以滿足

makemap函數會通過 fastrand 創建一個隨機的哈希種子，然后根據傳入的 hint 計算出需要的最小需要的桶的數量，最后再使用 makeBucketArray 創建用于保存桶的數組，這個方法其實就是根據傳入的 B 計算出的需要創建的桶數量在內存中分配一片連續的空間用于存儲數據，在創建桶的過程中還會額外創建一些用于保存溢出數據的桶，數量是 2^(B-4) 個。初始化完成返回hmap指針。

找到一個 B，使得 map 的裝載因子在正常范圍內

Go 語言中讀取 map 有兩種語法：帶 comma 和 不帶 comma。當要查詢的 key 不在 map 里，帶 comma 的用法會返回一個 bool 型變量提示 key 是否在 map 中；而不帶 comma 的語句則會返回一個 value 類型的零值。如果 value 是 int 型就會返回 0，如果 value 是 string 類型，就會返回空字符串。

map的查找通過生成匯編碼可以知道，根據 key 的不同類型，編譯器會將查找函數用更具體的函數替換，以優化效率：

函數首先會檢查 map 的標志位 flags。如果 flags 的寫標志位此時被置 1 了，說明有其他協程在執行“寫”操作，進而導致程序 panic。這也說明了 map 對協程是不安全的。

key經過哈希函數計算后，得到的哈希值如下（主流64位機下共 64 個 bit 位）：

m: 桶的個數

從buckets 通過 hash m 得到對應的bucket，如果bucket正在擴容，并且沒有擴容完成，則從oldbuckets得到對應的bucket

計算hash所在桶編號：

用上一步哈希值最后的 5 個 bit 位，也就是 01010 ，值為 10，也就是 10 號桶（范圍是0~31號桶）

計算hash所在的槽位:

用上一步哈希值哈希值的高8個bit 位，也就是 10010111 ，轉化為十進制，也就是151，在 10 號 bucket 中尋找** tophash 值（HOB hash）為 151* 的 槽位**，即為key所在位置，找到了 2 號槽位，這樣整個查找過程就結束了。

如果在 bucket 中沒找到，并且 overflow 不為空，還要繼續去 overflow bucket 中尋找，直到找到或是所有的 key 槽位都找遍了，包括所有的 overflow bucket。

通過上面找到了對應的槽位，這里我們再詳細分析下key/value值是如何獲取的：

bucket 里 key 的起始地址就是 unsafe.Pointer(b)+dataOffset。第 i 個 key 的地址就要在此基礎上跨過 i 個 key 的大小；而我們又知道，value 的地址是在所有 key 之后，因此第 i 個 value 的地址還需要加上所有 key 的偏移。

通過匯編語言可以看到，向 map 中插入或者修改 key，最終調用的是 mapassign 函數。

實際上插入或修改 key 的語法是一樣的，只不過前者操作的 key 在 map 中不存在，而后者操作的 key 存在 map 中。

mapassign 有一個系列的函數，根據 key 類型的不同，編譯器會將其優化為相應的“快速函數”。

我們只用研究最一般的賦值函數 mapassign 。

map的賦值會附帶著map的擴容和遷移，map的擴容只是將底層數組擴大了一倍，并沒有進行數據的轉移，數據的轉移是在擴容后逐步進行的，在遷移的過程中每進行一次賦值（access或者delete）會至少做一次遷移工作。

1.判斷map是否為nil

每一次進行賦值/刪除操作時，只要oldbuckets != nil 則認為正在擴容，會做一次遷移工作，下面會詳細說下遷移過程

根據上面查找過程，查找key所在位置，如果找到則更新，沒找到則找空位插入即可

經過前面迭代尋找動作，若沒有找到可插入的位置，意味著需要擴容進行插入，下面會詳細說下擴容過程

通過匯編語言可以看到，向 map 中刪除 key，最終調用的是 mapdelete 函數

刪除的邏輯相對比較簡單，大多函數在賦值操作中已經用到過，核心還是找到 key 的具體位置。尋找過程都是類似的，在 bucket 中挨個 cell 尋找。找到對應位置后，對 key 或者 value 進行“清零”操作，將 count 值減 1，將對應位置的 tophash 值置成 Empty

再來說觸發 map 擴容的時機：在向 map 插入新 key 的時候，會進行條件檢測，符合下面這 2 個條件，就會觸發擴容：

1、裝載因子超過閾值

源碼里定義的閾值是 6.5 (loadFactorNum/loadFactorDen)，是經過測試后取出的一個比較合理的因子

我們知道，每個 bucket 有 8 個空位，在沒有溢出，且所有的桶都裝滿了的情況下，裝載因子算出來的結果是 8。因此當裝載因子超過 6.5 時，表明很多 bucket 都快要裝滿了，查找效率和插入效率都變低了。在這個時候進行擴容是有必要的。

對于條件 1，元素太多，而 bucket 數量太少，很簡單：將 B 加 1，bucket 最大數量( 2^B )直接變成原來 bucket 數量的 2 倍。于是，就有新老 bucket 了。注意，這時候元素都在老 bucket 里，還沒遷移到新的 bucket 來。新 bucket 只是最大數量變為原來最大數量的 2 倍( 2^B * 2 ) 。

2、overflow 的 bucket 數量過多

在裝載因子比較小的情況下，這時候 map 的查找和插入效率也很低，而第 1 點識別不出來這種情況。表面現象就是計算裝載因子的分子比較小，即 map 里元素總數少，但是 bucket 數量多（真實分配的 bucket 數量多，包括大量的 overflow bucket）

不難想像造成這種情況的原因：不停地插入、刪除元素。先插入很多元素，導致創建了很多 bucket，但是裝載因子達不到第 1 點的臨界值，未觸發擴容來緩解這種情況。之后，刪除元素降低元素總數量，再插入很多元素，導致創建很多的 overflow bucket，但就是不會觸發第 1 點的規定，你能拿我怎么辦？overflow bucket 數量太多，導致 key 會很分散，查找插入效率低得嚇人，因此出臺第 2 點規定。這就像是一座空城，房子很多，但是住戶很少，都分散了，找起人來很困難

對于條件 2，其實元素沒那么多，但是 overflow bucket 數特別多，說明很多 bucket 都沒裝滿。解決辦法就是開辟一個新 bucket 空間，將老 bucket 中的元素移動到新 bucket，使得同一個 bucket 中的 key 排列地更緊密。這樣，原來，在 overflow bucket 中的 key 可以移動到 bucket 中來。結果是節省空間，提高 bucket 利用率，map 的查找和插入效率自然就會提升。

由于 map 擴容需要將原有的 key/value 重新搬遷到新的內存地址，如果有大量的 key/value 需要搬遷，會非常影響性能。因此 Go map 的擴容采取了一種稱為“漸進式”的方式，原有的 key 并不會一次性搬遷完畢，每次最多只會搬遷 2 個 bucket。

上面說的 hashGrow() 函數實際上并沒有真正地“搬遷”，它只是分配好了新的 buckets，并將老的 buckets 掛到了 oldbuckets 字段上。真正搬遷 buckets 的動作在 growWork() 函數中，而調用 growWork() 函數的動作是在 mapassign 和 mapdelete 函數中。也就是插入或修改、刪除 key 的時候，都會嘗試進行搬遷 buckets 的工作。先檢查 oldbuckets 是否搬遷完畢，具體來說就是檢查 oldbuckets 是否為 nil。

如果未遷移完畢，賦值/刪除的時候，擴容完畢后（預分配內存），不會馬上就進行遷移。而是采取 增量擴容 的方式，當有訪問到具體 bukcet 時，才會逐漸的進行遷移（將 oldbucket 遷移到 bucket）

nevacuate 標識的是當前的進度，如果都搬遷完，應該和2^B的長度是一樣的

在evacuate 方法實現是把這個位置對應的bucket，以及其沖突鏈上的數據都轉移到新的buckets上。

轉移的判斷直接通過tophash 就可以，判斷tophash中第一個hash值即可

遍歷的過程，就是按順序遍歷 bucket，同時按順序遍歷 bucket 中的 key。

map遍歷是無序的，如果想實現有序遍歷，可以先對key進行排序

為什么遍歷 map 是無序的？

如果發生過遷移，key 的位置發生了重大的變化，有些 key 飛上高枝，有些 key 則原地不動。這樣，遍歷 map 的結果就不可能按原來的順序了。

如果就一個寫死的 map，不會向 map 進行插入刪除的操作，按理說每次遍歷這樣的 map 都會返回一個固定順序的 key/value 序列吧。但是 Go 杜絕了這種做法，因為這樣會給新手程序員帶來誤解，以為這是一定會發生的事情，在某些情況下，可能會釀成大錯。

Go 做得更絕，當我們在遍歷 map 時，并不是固定地從 0 號 bucket 開始遍歷，每次都是從一個**隨機值序號的 bucket 開始遍歷，并且是從這個 bucket 的一個 隨機序號的 cell **開始遍歷。這樣，即使你是一個寫死的 map，僅僅只是遍歷它，也不太可能會返回一個固定序列的 key/value 對了。

Go語言又伸魔爪，匯編語言架的住嗎

匯編比較特殊，他主要應用的環境別人都替代不了，別的語言能干的事情沒誰會傻到用匯編。這玩意一般用來做一些高級語言運行環境還沒初始化的時候運行的程序比如BIOS，還有內核里需要操作一些特殊的寄存器的時候，比如x86下讀寫CR0，CR3之類的控制寄存器的情況，這些高級語言都沒法辦到。

如何配置go語言開發環境

1.1 Go 安裝

Go的三種安裝方式

Go有多種安裝方式，你可以選擇自己喜歡的。這里我們介紹三種最常見的安裝方式：

Go源碼安裝：這是一種標準的軟件安裝方式。對于經常使用Unix類系統的用戶，尤其對于開發者來說，從源碼安裝可以自己定制。

Go標準包安裝：Go提供了方便的安裝包，支持Windows、Linux、Mac等系統。這種方式適合快速安裝，可根據自己的系統位數下載好相應的安裝包，一路next就可以輕松安裝了。**推薦這種方式**

第三方工具安裝：目前有很多方便的第三方軟件包工具，例如Ubuntu的apt-get、Mac的homebrew等。這種安裝方式適合那些熟悉相應系統的用戶。

最后，如果你想在同一個系統中安裝多個版本的Go，你可以參考第三方工具GVM，這是目前在這方面做得最好的工具，除非你知道怎么處理。

Go源碼安裝

在Go的源代碼中，有些部分是用Plan 9 C和ATT匯編寫的，因此假如你要想從源碼安裝，就必須安裝C的編譯工具。

在Mac系統中，只要你安裝了Xcode，就已經包含了相應的編譯工具。

在類Unix系統中，需要安裝gcc等工具。例如Ubuntu系統可通過在終端中執行sudo apt-get install gcc

libc6-dev來安裝編譯工具。

在Windows系統中，你需要安裝MinGW，然后通過MinGW安裝gcc，并設置相應的環境變量。

你可以直接去官網下載源碼，找相應的goVERSION.src.tar.gz的文件下載，下載之后解壓縮到$HOME目錄，執行如下代碼：

cd go/src

./all.bash

運行all.bash后出現"ALL TESTS PASSED"字樣時才算安裝成功。

上面是Unix風格的命令，Windows下的安裝方式類似，只不過是運行all.bat，調用的編譯器是MinGW的gcc。

如果是Mac或者Unix用戶需要設置幾個環境變量，如果想重啟之后也能生效的話把下面的命令寫到.bashrc或者.zshrc里面，

export GOPATH=$HOME/gopath

export PATH=$PATH:$HOME/go/bin:$GOPATH/bin

如果你是寫入文件的，記得執行bash .bashrc或者bash

.zshrc使得設置立馬生效。

如果是window系統，就需要設置環境變量，在path里面增加相應的go所在的目錄，設置gopath變量。

當你設置完畢之后在命令行里面輸入go，看到如下圖片即說明你已經安裝成功

圖1.1 源碼安裝之后執行Go命令的圖

如果出現Go的Usage信息，那么說明Go已經安裝成功了；如果出現該命令不存在，那么可以檢查一下自己的PATH環境變中是否包含了Go的安裝目錄。

關于上面的GOPATH將在下面小節詳細講解

Go標準包安裝

Go提供了每個平臺打好包的一鍵安裝，這些包默認會安裝到如下目錄：/usr/local/go

(Windows系統：c:\Go)，當然你可以改變他們的安裝位置，但是改變之后你必須在你的環境變量中設置如下信息：

export GOROOT=$HOME/go

export GOPATH=$HOME/gopath

export PATH=$PATH:$GOROOT/bin:$GOPATH/bin

上面這些命令對于Mac和Unix用戶來說最好是寫入.bashrc或者.zshrc文件，對于windows用戶來說當然是寫入環境變量。

如何判斷自己的操作系統是32位還是64位？

我們接下來的Go安裝需要判斷操作系統的位數，所以這小節我們先確定自己的系統類型。

Windows系統用戶請按Win+R運行cmd，輸入systeminfo后回車，稍等片刻，會出現一些系統信息。在“系統類型”一行中，若顯示“x64-based

PC”，即為64位系統；若顯示“X86-based PC”，則為32位系統。

Mac系統用戶建議直接使用64位的，因為Go所支持的Mac OS X版本已經不支持純32位處理器了。

Linux系統用戶可通過在Terminal中執行命令arch(即uname

-m)來查看系統信息：

64位系統顯示

x86_64

32位系統顯示

i386

Mac 安裝

訪問下載地址，32位系統下載go1.4.2.darwin-386-osx10.8.pkg，64位系統下載go1.4.2.darwin-amd64-osx10.8.pkg，雙擊下載文件，一路默認安裝點擊下一步，這個時候go已經安裝到你的系統中，默認已經在PATH中增加了相應的~/go/bin,這個時候打開終端，輸入go

看到類似上面源碼安裝成功的圖片說明已經安裝成功

如果出現go的Usage信息，那么說明go已經安裝成功了；如果出現該命令不存在，那么可以檢查一下自己的PATH環境變中是否包含了go的安裝目錄。

Linux 安裝

訪問下載地址，32位系統下載go1.4.2.linux-386.tar.gz，64位系統下載go1.4.2.linux-amd64.tar.gz，

假定你想要安裝Go的目錄為 $GO_INSTALL_DIR，后面替換為相應的目錄路徑。

解壓縮tar.gz包到安裝目錄下：tar zxvf go1.4.2.linux-amd64.tar.gz -C

$GO_INSTALL_DIR。

設置PATH，export PATH=$PATH:$GO_INSTALL_DIR/go/bin

然后執行go

圖1.2 Linux系統下安裝成功之后執行go顯示的信息

如果出現go的Usage信息，那么說明go已經安裝成功了；如果出現該命令不存在，那么可以檢查一下自己的PATH環境變中是否包含了go的安裝目錄。

Windows 安裝

訪問Google Code 下載頁，32

位請選擇名稱中包含 windows-386 的 msi 安裝包，64 位請選擇名稱中包含 windows-amd64 的。下載好后運行，不要修改默認安裝目錄

C:\Go\，若安裝到其他位置會導致不能執行自己所編寫的 Go 代碼。安裝完成后默認會在環境變量 Path 后添加 Go 安裝目錄下的 bin 目錄

C:\Go\bin\，并添加環境變量 GOROOT，值為 Go 安裝根目錄 C:\Go\ 。

驗證是否安裝成功

在運行中輸入 cmd 打開命令行工具，在提示符下輸入 go，檢查是否能看到 Usage 信息。輸入

cd %GOROOT%，看是否能進入 Go 安裝目錄。若都成功，說明安裝成功。

不能的話請檢查上述環境變量 Path 和 GOROOT 的值。若不存在請卸載后重新安裝，存在請重啟計算機后重試以上步驟。

第三方工具安裝

GVM

gvm是第三方開發的Go多版本管理工具，類似ruby里面的rvm工具。使用起來相當的方便，安裝gvm使用如下命令：

bash (curl -s -S -L )

安裝完成后我們就可以安裝go了：

gvm install go1.4.2

gvm use go1.4.2

也可以使用下面的命令，省去每次調用gvm use的麻煩： gvm use go1.4.2 --default

執行完上面的命令之后GOPATH、GOROOT等環境變量會自動設置好，這樣就可以直接使用了。

apt-get

Ubuntu是目前使用最多的Linux桌面系統，使用apt-get命令來管理軟件包，我們可以通過下面的命令來安裝Go，為了以后方便，應該把

git mercurial 也安裝上：

sudo apt-get install python-software-properties

sudo add-apt-repository ppa:gophers/go

sudo apt-get update

sudo apt-get install golang-stable git-core mercurial

homebrew

homebrew是Mac系統下面目前使用最多的管理軟件的工具，目前已支持Go，可以通過命令直接安裝Go，為了以后方便，應該把

git mercurial 也安裝上：

brew update brew upgrade

brew install go

brew install git

brew install mercurial

本文標題：go語言學習調用匯編,go語言編譯過程
分享路徑：http://www.yijiale78.com/article8/dsihhip.html

成都網站建設公司_創新互聯，為您提供品牌網站設計、自適應網站、微信小程序、品牌網站制作、Google、做網站

廣告

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