golang map源碼淺析

golang 中 map的實現(xiàn)結(jié)構(gòu)為： 哈希表 + 鏈表。 其中鏈表，作用是當(dāng)發(fā)生hash沖突時，拉鏈法生成的結(jié)點(diǎn)。

成都創(chuàng)新互聯(lián)公司是一家集網(wǎng)站建設(shè),賓陽企業(yè)網(wǎng)站建設(shè),賓陽品牌網(wǎng)站建設(shè),網(wǎng)站定制,賓陽網(wǎng)站建設(shè)報價,網(wǎng)絡(luò)營銷,網(wǎng)絡(luò)優(yōu)化,賓陽網(wǎng)站推廣為一體的創(chuàng)新建站企業(yè)，幫助傳統(tǒng)企業(yè)提升企業(yè)形象加強(qiáng)企業(yè)競爭力?？沙浞譂M足這一群體相比中小企業(yè)更為豐富、高端、多元的互聯(lián)網(wǎng)需求。同時我們時刻保持專業(yè)、時尚、前沿，時刻以成就客戶成長自我，堅持不斷學(xué)習(xí)、思考、沉淀、凈化自己，讓我們?yōu)楦嗟钠髽I(yè)打造出實用型網(wǎng)站。

可以看到， []bmap 是一個hash table， 每一個 bmap是我們常說的“桶”。 經(jīng)過hash 函數(shù)計算出來相同的hash值， 放到相同的桶中。 一個 bmap中可以存放 8個 元素， 如果多出8個，則生成新的結(jié)點(diǎn)，尾接到隊尾。

以上是只是靜態(tài)文件 src/runtime/map.go 中的定義。 實際上編譯期間會給它加料 ，動態(tài)地創(chuàng)建一個新的結(jié)構(gòu)：

上圖就是 bmap的內(nèi)存模型， HOB Hash 指的就是 top hash。 注意到 key 和 value 是各自放在一起的，并不是 key/value/key/value/... 這樣的形式。源碼里說明這樣的好處是在某些情況下可以省略掉 padding 字段，節(jié)省內(nèi)存空間。

每個 bmap設(shè)計成 最多只能放 8 個 key-value 對 ，如果有第 9 個 key-value 落入當(dāng)前的 bmap，那就需要再構(gòu)建一個 bmap，通過 overflow 指針連接起來。

map創(chuàng)建方法:

我們實際上是通過調(diào)用的 makemap ，來創(chuàng)建map的。實際工作只是初始化了hmap中的各種字段，如：設(shè)置B的大小， 設(shè)置hash 種子 hash 0.

注意 :

makemap 返回是*hmap 指針， 即 map 是引用對象， 對map的操作會影響到結(jié)構(gòu)體內(nèi)部 。

使用方式

對應(yīng)的是下面兩種方法

map的key的類型，實現(xiàn)了自己的hash 方式。每種類型實現(xiàn)hash函數(shù)方式不一樣。

key 經(jīng)過哈希計算后得到hash值，共 64 個 bit 位。 其中后B 個bit位置， 用來定位當(dāng)前元素落在哪一個桶里， 高8個bit 為當(dāng)前 hash 值的top hash。 實際上定位key的過程是一個雙重循環(huán)的過程， 外層循環(huán)遍歷 所有的overflow， 內(nèi)層循環(huán)遍歷 當(dāng)前bmap 中的 8個元素 。

舉例說明： 如果當(dāng)前 B 的值為 5， 那么buckets 的長度 為 2^5 = 32。假設(shè)有個key 經(jīng)過hash函數(shù)計算后，得到的hash結(jié)果為：

外層遍歷bucket 中的鏈表

內(nèi)層循環(huán)遍歷 bmap中的8個 cell

建議先不看此部分內(nèi)容，看完后續(xù) 修改 map中元素 - 擴(kuò)容 操作后 再回頭看此部分內(nèi)容。

擴(kuò)容前的數(shù)據(jù)：

等量擴(kuò)容后的數(shù)據(jù)：

等量擴(kuò)容后，查找方式和原本相同， 不多做贅述。

兩倍擴(kuò)容后的數(shù)據(jù)

兩倍擴(kuò)容后，oldbuckets 的元素，可能被分配成了兩部分。查找順序如下：

此處只分析 mapaccess1 ,。 mapaccess2 相比 mapaccess1 多添加了是否找到的bool值， 有興趣可自行看一下。

使用方式：

步驟如下：

擴(kuò)容條件 ：

擴(kuò)容的標(biāo)識 ： h.oldbuckets ！= nil

假設(shè)當(dāng)前定位到了新的buckets的3號桶中，首先會判斷oldbuckets中的對應(yīng)的桶有沒有被搬遷過。 如果搬遷過了，不需要看原來的桶了，直接遍歷新的buckets的3號桶。

擴(kuò)容前：

等量擴(kuò)容結(jié)果

雙倍擴(kuò)容會將old buckets上的元素分配到x， y兩個部key 1 B == 0 分配到x部分，key 1 B == 1 分配到y(tǒng)部分

注意： 當(dāng)前只對雙倍擴(kuò)容描述， 等量擴(kuò)容只是重新填充了一下元素， 相對位置沒有改變。

假設(shè)當(dāng)前map 的B == 5，原本元素經(jīng)過hash函數(shù)計算的 hash 值為：

因為雙倍擴(kuò)容之后 B = B + 1，此時B == 6。key 1 B == 1, 即 當(dāng)前元素rehash到高位，新buckets中 y 部分. 否則 key 1 B == 0 則rehash到低位，即x 部分。

使用方式：

可以看到，每一遍歷生成迭代器的時候，會隨機(jī)選取一個bucket 以及 一個cell開始。 從前往后遍歷，再次遍歷到起始位置時，遍歷完成。

golang變量(二)——map和slice詳解

衍生類型，interface{} , map, [] ，struct等

map類似于java的hashmap，python的dict，php的hash array。

常規(guī)的for循環(huán)，可以用for k,v :=range m {}. 但在下面清空有一個坑注意：

著名的map[string]*struct 副本問題

結(jié)果：

Go 中不存在引用傳遞，所有的參數(shù)傳遞都是值傳遞，而map是等同于指針類型的，所以在把map變量傳遞給函數(shù)時，函數(shù)對map的修改，也會實質(zhì)改變map的值。

slice類似于其他語言的數(shù)組（list，array），slice初始化和map一樣，這里不在重復(fù)

除了Pointer數(shù)組外，len表示使用長度，cap是總?cè)萘浚琺ake([]int, len, cap)可以預(yù)申請 比較大的容量，這樣可以減少容量拓展的消耗，前提是要用到。

cap是計算切片容量，len是計算變量長度的，兩者不一樣。具體例子如下：

結(jié)果：

分析：cap是計算當(dāng)前slice已分配的容量大小，采用的是預(yù)分配的伙伴算法（當(dāng)容量滿時，拓展分配一倍的容量）。

append是slice非常常用的函數(shù)，用于添加數(shù)據(jù)到slice中，但如果使用不好，會有下面的問題：

預(yù)期是[1 2 3 4 5 6 7 8 9 10]， [1 2 3 4 5 6 7 8 9 10 11 12]，但實際結(jié)果是：

注意slice是值傳遞，修改一下：

輸出如下：

== 只能用于判斷常規(guī)數(shù)據(jù)類型，無法使用用于slice和map判斷，用于判斷map和slice可以使用reflect.DeepEqual，這個函數(shù)用了遞歸來判斷每層的k，v是否一致。

當(dāng)然還有其他方式，比如轉(zhuǎn)換成json，但小心有一些異常的bug，比如html編碼，具體這個json問題，待后面在分析。

go語言怎樣處理 map 的值

// 先聲明map

var m1 map[string]string

// 再使用make函數(shù)創(chuàng)建一個非nil的map，nil map不能賦值

m1 = make(map[string]string)

// 最后給已聲明的map賦值

m1["a"] = "aa"

m1["b"] = "bb"

// 直接創(chuàng)建

m2 := make(map[string]string)

// 然后賦值

m2["a"] = "aa"

m2["b"] = "bb"

// 初始化 + 賦值一體化

m3 := map[string]string{

"a": "aa",

"b": "bb",

}

望采納。。

// ==========================================

// 查找鍵值是否存在

if v, ok := m1["a"]; ok {

fmt.Println(v)

} else {

fmt.Println("Key Not Found")

}

// 遍歷map

for k, v := range m1 {

fmt.Println(k, v)

}