Go中Map底層原理剖析_go map底層實現-CSDN博客

目錄

Map 鍵值對key,value

? ? ? ? ? ? ? ? ? 注意：?map唯一確定的key值通過哈希運算得出哈希值

? ? ?一、 map的聲明及初始化：

? ? ?二、 map的增刪改查操作：

? ? ?三、? ?map的賦值操作與切片對比：

? ? ?四、? ?通用所有語言的map哈希底層原理：

? ? ?五、? ? go語言實現和擴展后的map底層原理：? runtime包下map.go文件

? ? ? ? ? ? map對象創建底層原理：

? ? ? ? ? ? ? ? ?一）、初始化hmap對象，bmap對象。?編輯

? ? ? ? ? ? ? ? ?二）、將鍵值對信息寫入bmap中。

? ? ? ?map對象的擴容底層原理：等量擴容，翻倍擴容：

? ? ? ? ? ? ? ? 等量擴容：

? ? ? ? ? ? ? ? 翻倍擴容：

指針

結構體

函數

---

---

Map 鍵值對key,value

?? ? ? 注意：?map唯一確定的key值通過哈希運算得出哈希值

?????????????????????????1）key值必須唯一，所以map不可重復

? ? ? ? ????????? ? 2）key值不能是動態變化的值類型，不能是切片類型，map類型。也不能是嵌套的切片，map類型。

? ? ? ?一、 map的聲明及初始化：

? ? ? ? ? ? ? 1)? ?mapObject := map[ string ]? string{}?

? ? ? ? ? ? ? 2)? mapObject?:= make(map[ string ] string , 10)?

???????????????????????? 通過make關鍵字設定了容量的參考值，并且map沒有cap()查看容量方法

? ? ? ? ? ????3）var mapObject? map[ string] int? //對象地址為空??

? ? ? ? ? ? ? ? ? ? ? ? 僅聲明了類型，并沒有初始化的操作，所以沒有在內存中開辟空間。

? ? ? ? ? ? ? 注意) ：?mapObject_zhiZhen?:=?? new(map[ string ] string)? ?//對象地址為空

?????????????????????????雖然new關鍵字會初始化對象，但是map類型對象初始化的默認值為nil，類比于java，就像引用類型對象默認的初始化值為null。

---

? ? ? ?二、 map的增刪改查操作：

? ? ? ? ? ? mapObject := map[string ] string { }?

? ? ? ? ? ? ? ? 添加 ：

? ? ? ? ? ? ? ? 修改：

? ? ? ? ? ? ? ? ? ? ? ? mapObject[ "key1" ]? =? "value1"

? ? ? ? ? ? ? ? 刪除：

? ? ? ? ? ? ? ? ? ? ? ? delete(mapObject,"key1")

? ? ? ? ? ? ? ? 查看:

? ? ? ? ? ? ? ? ? ? ? ? for key,value :=? range mapObject{

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? fmt.Println(key,value)

????????????????????????}

---

? ? ?三、? ?map的賦值操作與切片對比：

? ? ? ? ? ? ? ? v1 := map[ string ] string{ }

? ? ? ? ? ? ? ? v2 := v1

? ? ? ? ? ? ? ????????? ?v1,v2 指向的是同一個內存地址，無論是否發生擴容機制。

? ? ? ? ? ? ? ? v3 := [ ] int{11,22,33 }

? ? ? ? ? ? ? ? v4 := append(v3,44)

? ? ? ? ? ? ? ? ? ? ? ? v3,v4內存地址發生改變，究其原因是v3切片容量已經滿了(容量默認為v3的元素個數3)，v4就會開劈新的內存空間創建新的切片對象并復制原有的所有元素。

---

? ? ?四、? ?通用所有語言的map哈希底層原理：

? ? ? ? ? ? ? ? 通過唯一確定的key值通過哈希運算計算出哈希值。每一個key,value鍵值對都通過哈希值進行存放，具體的存放方法是：

? ? ? ? ? ? ? ? 假定一個最優的存放隊列是4，每一個map元素都放在這4個隊列其中之一，而放在哪個隊列中就根據哈希值和隊列數的模：

????????????????模值是0就放在第一個；

????????????????模值是1就放在第二個；

????????????????模值是2就放在第三個；

????????????????模值是3就放在第四個。

? ? ? ? ? ? ? ? 這樣就把所有散列的map元素按哈希值與隊列數的模值這樣的規律放好，將來想找到某一個map元素，就根據模值找到這個元素所在的隊列，在根據這個元素的哈希值具體查找到這個元素，這樣的話效率對比查找某個map值需要遍歷整個map集合來說效率就高了3/4。

---

? ? 五、? ? go語言實現和擴展后的map底層原理：? runtime包下map.go文件

? ? ? ? ? ? ? ? go語言的map底層會有兩個對象hmap，bmap

? ? ? ? ? ? ? ? ? ? ? ? hmap實現了根據map元素個數count創建最優桶個數B，存放所有桶的桶數組buckets。哈希因子是為了將所有的key按此哈希因子的統一規律進行哈希運算得到哈希值。

? ? ? ? ? ? ? ? ? ? ? ? bmap代表的是桶數組中的桶對象，bmap負責存儲key，value值。并且還會存儲

key的哈希值的高8位，目的是為了根據map元素哈希值實現快速查找。

? ? ?

---

? ? ? ? map對象創建底層原理：

? ? ? ? ? ? ? ? 一）、初始化hmap對象，bmap對象。

---

? ? ? ? ? ? ? ? ?二）、將鍵值對信息寫入bmap中。

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?所有元素的存放到對應bmap的計算方法：

?????????????????????????????????????????哈希值與B的&運算，但是B值與哈希值相比較高位全部為0，高位&運算的二進制結果都為0，沒有意義，通常取哈希值低B位進行運算得到對應標準桶的索引下標。

? ?

---

? ? ? ?map對象的擴容底層原理：等量擴容，翻倍擴容：

? ? ? ? ? ? ? ? 等量擴容：

? ? ? ? ? ? ? ? ? ? ? ? ?溢出桶太多，存放隊列的元素從有規律到雜亂無章，重新將標準桶和溢出桶所有元素按哈希值排列一遍。觸發等量擴容并沒有改變map的標準桶個數B，只是將所有元素重新排列一遍。

? ? ? ? ? ? ? ? 翻倍擴容：

? ? ? ? ? ?簡單來說就是B = B + 1，所有元素的存放位置根據B需要重新計算。

??????????但計算過程也不需要從頭開始計算。同一個map哈希因子不變，哈希值并沒有改變，

只需要關注元素存放的下標位置。

? ? ? ? ? 而元素從舊桶到新桶也只能有兩個選擇，一個選擇是原來的位置index，另一個選擇

是?index+B 。因為?哈希值 的低B位與B值進行&運算得到索引下標。B變為B+1時，不確定

的就是哈希值的低B位增加的那一位是0還是1。如果是0直接還是原位置index，如果是1就是

index+B

? ? ? ?

?

---

?

指針

結構體

函數