Map大合集

• • • 1. 原理
    • 2.1 哈希沖突
    • 2.2 Map底層原理剖析
    • • 2.2.1 初始化
      • 2.2.2 寫(xiě)入數(shù)據(jù)
      • 2.2.3 查找數(shù)據(jù)
      • 2.2.4 擴(kuò)容
      • 2.2.5 遷移
      • • 翻倍擴(kuò)容
        • 等量擴(kuò)容
    • 2.3 map不安全問(wèn)題

1. 原理

Go中的map原理是 :
將多個(gè)鍵 / 值 (key / value)對(duì)分散的存儲(chǔ)在hashBuckets(哈希桶)中
給定一個(gè)鍵, 通過(guò)特定的哈希算法會(huì)計(jì)算出鍵值對(duì)的哈希值, 然后再用哈希值 % array_size, 就得了對(duì)應(yīng)的存儲(chǔ)下標(biāo) index

hash表：哈希值會(huì)確定其鍵應(yīng)該映射到哪一個(gè)桶。而一個(gè)好的哈希函數(shù)，應(yīng)當(dāng)盡量少的出現(xiàn)哈希沖突，以此保證操作哈希表的時(shí)間復(fù)雜度

2.1 哈希沖突

哈希函數(shù)在實(shí)際中遇到的最常見(jiàn)的問(wèn)題就是哈希碰撞, 即不同的鍵通過(guò)哈希函數(shù)可能產(chǎn)生相同的哈希值, 則他們會(huì)被分配到同一個(gè)桶中
主要有兩種策略

拉鏈法
拉鏈法是將同一個(gè)桶中的元素通過(guò)鏈表的形式連接起來(lái).
好處就是 : 不用預(yù)先申請(qǐng)空間, 可以不斷的鏈接新的元素
缺點(diǎn)就是 : 需要額外的指針來(lái)連接元素, 增加了哈希表的大小, 同時(shí)如果同一個(gè)桶中的連接元素太多了, 那么對(duì)于查找來(lái)說(shuō)就不嚴(yán)格符合O(1), 當(dāng)一條鏈表過(guò)長(zhǎng)時(shí), 我們需要改變這種情況, 讓這個(gè)鏈表減少元素 , 更改哈希函數(shù), 或者擴(kuò)容.

開(kāi)放尋址法
所有元素存儲(chǔ)在桶的數(shù)組中, 當(dāng)插入新元素時(shí), 將按照某種探測(cè)策略操作, 直到找到未使用的數(shù)組插槽為止
go中采用的是開(kāi)放尋址法中的線性探測(cè)策略, 每次順序加1

2.2 Map底層原理剖析

Golang中的Map有自己的一套實(shí)現(xiàn)原理，其核心是由hmap和bmap兩個(gè)結(jié)構(gòu)體實(shí)現(xiàn)。

2.2.1 初始化

// 初始化一個(gè)可容納10個(gè)元素的map info = make(map[string]string,10)

• 第一步：創(chuàng)建一個(gè)hmap結(jié)構(gòu)體對(duì)象。

• 第二步：生成一個(gè)哈希因子hash0 并賦值到hmap對(duì)象中（用于后續(xù)為key創(chuàng)建哈希值）。

• 第三步：根據(jù)hint=10，并根據(jù)算法規(guī)則來(lái)創(chuàng)建 B，當(dāng)前B應(yīng)該為1。

  hint B 0~8 0 9~13 1 14~26 2 ...

• 第四步：根據(jù)B去創(chuàng)建去創(chuàng)建桶（bmap對(duì)象）并存放在buckets數(shù)組中，當(dāng)前bmap的數(shù)量應(yīng)為2.

  • 當(dāng)B<4時(shí)，根據(jù)B創(chuàng)建桶的個(gè)數(shù)的規(guī)則為：$2^B$（標(biāo)準(zhǔn)桶）
  • 當(dāng)B>=4時(shí)，根據(jù)B創(chuàng)建桶的個(gè)數(shù)的規(guī)則為：$2^B$ + $2^{B?4}$（標(biāo)準(zhǔn)桶+溢出桶）

  注意：每個(gè)bmap中可以存儲(chǔ)8個(gè)鍵值對(duì)，當(dāng)不夠存儲(chǔ)時(shí)需要使用溢出桶，并將當(dāng)前bmap中的overflow字段指向溢出桶的位置。

2.2.2 寫(xiě)入數(shù)據(jù)

info["name"] = "王嘉豪"

在map中寫(xiě)入數(shù)據(jù)時(shí)，內(nèi)部的執(zhí)行流程為：

• 第一步：結(jié)合哈希因子和鍵 name生成哈希值 011011100011111110111011011。

• 第二步：獲取哈希值的后B位，并根據(jù)后B位的值來(lái)決定將此鍵值對(duì)存放到那個(gè)桶中（bmap）。

  將哈希值和桶掩碼（B個(gè)為1的二進(jìn)制）進(jìn)行 & 運(yùn)算，最終得到哈希值的后B位的值。假設(shè)當(dāng)B為1時(shí)，其結(jié)果為 0 ： 哈希值：011011100011111110111011010 桶掩碼：000000000000000000000000001 結(jié)果： 000000000000000000000000000 = 0通過(guò)示例你會(huì)發(fā)現(xiàn)，找桶的原則實(shí)際上是根據(jù)后B為的位運(yùn)算計(jì)算出 索引位置，然后再去buckets數(shù)組中根據(jù)索引找到目標(biāo)桶（bmap)。

• 第三步：在上一步確定桶之后，接下來(lái)就在桶中寫(xiě)入數(shù)據(jù)。

  獲取哈希值的tophash（即：哈希值的`高8位`），將tophash、key、value分別寫(xiě)入到桶中的三個(gè)數(shù)組中。 如果桶已滿，則通過(guò)overflow找到溢出桶，并在溢出桶中繼續(xù)寫(xiě)入。注意：以后在桶中查找數(shù)據(jù)時(shí)，會(huì)基于tophash來(lái)找（tophash相同則再去比較key）。

• 第四步：hmap的個(gè)數(shù)count++（map中的元素個(gè)數(shù)+1）

[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來(lái)直接上傳(img-Cp491mQI-1639726855036)(assets/image-20200919191800912.png)]

2.2.3 查找數(shù)據(jù)

value := info["name"]

在map中讀取數(shù)據(jù)時(shí)，內(nèi)部的執(zhí)行流程為：

• 第一步：結(jié)合哈希引子和鍵 name生成哈希值。

• 第二步：獲取哈希值的后B位，并根據(jù)后B為的值來(lái)決定將此鍵值對(duì)存放到那個(gè)桶中（bmap）。

• 第三步：確定桶之后，再根據(jù)key的哈希值計(jì)算出tophash（高8位），根據(jù)tophash和key去桶中查找數(shù)據(jù)。

  當(dāng)前桶如果沒(méi)找到，則根據(jù)overflow再去溢出桶中找，均未找到則表示key不存在, 返回value類(lèi)型的零值

2.2.4 擴(kuò)容

在向map中添加數(shù)據(jù)時(shí)，當(dāng)達(dá)到某個(gè)條件，則會(huì)引發(fā)字典擴(kuò)容。

擴(kuò)容條件：

• map中數(shù)據(jù)總個(gè)數(shù) / 桶個(gè)數(shù) > 6.5 ，引發(fā)翻倍擴(kuò)容。
• 使用了太多的溢出桶時(shí)（溢出桶使用的太多會(huì)導(dǎo)致map處理速度降低）。
  • B <=15，已使用的溢出桶個(gè)數(shù) >= $2^B$ 時(shí)，引發(fā)等量擴(kuò)容。
  • B > 15，已使用的溢出桶個(gè)數(shù) >= $2^{15}$ 時(shí)，引發(fā)等量擴(kuò)容。

func hashGrow(t *maptype, h *hmap) {// If we've hit the load factor, get bigger.// Otherwise, there are too many overflow buckets,// so keep the same number of buckets and "grow" laterally.bigger := uint8(1)if !overLoadFactor(h.count+1, h.B) {bigger = 0h.flags |= sameSizeGrow}oldbuckets := h.bucketsnewbuckets, nextOverflow := makeBucketArray(t, h.B+bigger, nil)... } 擴(kuò)容之后, 數(shù)據(jù)還保存在舊桶中, 需要遷移后數(shù)據(jù)才在新桶中

當(dāng)擴(kuò)容之后：

• 第一步：B會(huì)根據(jù)擴(kuò)容后新桶的個(gè)數(shù)進(jìn)行增加（翻倍擴(kuò)容新B=舊B+1，等量擴(kuò)容 新B=舊B）。
• 第二步：oldbuckets指向原來(lái)的桶（舊桶）。
• 第三步：buckets指向新創(chuàng)建的桶（新桶中暫時(shí)還沒(méi)有數(shù)據(jù)）。
• 第四步：nevacuate設(shè)置為0，表示如果數(shù)據(jù)遷移的話，應(yīng)該從原桶（舊桶）中的第0個(gè)位置開(kāi)始遷移。
• 第五步：noverflow設(shè)置為0，擴(kuò)容后新桶中已使用的溢出桶為0。
• 第六步：extra.oldoverflow設(shè)置為原桶（舊桶）已使用的所有溢出桶。即：h.extra.oldoverflow = h.extra.overflow
• 第七步：extra.overflow設(shè)置為nil，因?yàn)樾峦爸羞€未使用溢出桶。
• 第八步：extra.nextOverflow設(shè)置為新創(chuàng)建的桶中的第一個(gè)溢出桶的位置。
  

2.2.5 遷移

擴(kuò)容之后，必然要伴隨著數(shù)據(jù)的遷移，即：將舊桶中的數(shù)據(jù)要遷移到新桶中。

翻倍擴(kuò)容

如果是翻倍擴(kuò)容，那么遷移規(guī)就是將舊桶中的數(shù)據(jù)分流至新的兩個(gè)桶中（比例不定），并且桶編號(hào)的位置為：同編號(hào)位置 和 翻倍后對(duì)應(yīng)編號(hào)位置。

那么問(wèn)題來(lái)了，如何實(shí)現(xiàn)的這種遷移呢？

首先，我們要知道如果翻倍擴(kuò)容（數(shù)據(jù)總個(gè)數(shù) / 桶個(gè)數(shù) > 6.5），則新桶個(gè)數(shù)是舊桶的2倍，即：map中的B的值要+1（因?yàn)橥暗膫€(gè)數(shù)等于$2^B$，而翻倍之后新桶的個(gè)數(shù)就是$2^B$ * 2 ，也就是$2^{B+1}$，所以 新桶的B的值=原桶B + 1 ）。

遷移時(shí)會(huì)遍歷某個(gè)舊桶中所有的key（包括溢出桶），并根據(jù)key重新生成哈希值，根據(jù)哈希值的 底B位 來(lái)決定將此鍵值對(duì)分流道那個(gè)新桶中。

擴(kuò)容后，B的值在原來(lái)的基礎(chǔ)上已加1，也就意味著通過(guò)多1位來(lái)計(jì)算此鍵值對(duì)要分流到新桶位置，如上圖：

• 當(dāng)新增的位（紅色）的值為 0，則數(shù)據(jù)會(huì)遷移到與舊桶編號(hào)一致的位置。
• 當(dāng)新增的位（紅色）的值為 1，則數(shù)據(jù)會(huì)遷移到翻倍后對(duì)應(yīng)編號(hào)位置。

例如：

舊桶個(gè)數(shù)為32個(gè)，翻倍后新桶的個(gè)數(shù)為64。 在重新計(jì)算舊桶中的所有key哈希值時(shí)，紅色位只能是0或1，所以桶中的所有數(shù)據(jù)的后B位只能是以下兩種情況：- 000111【7】，意味著要遷移到與舊桶編號(hào)一致的位置。- 100111【39】，意味著會(huì)遷移到翻倍后對(duì)應(yīng)編號(hào)位置。特別提醒：同一個(gè)桶中key的哈希值的低B位一定是相同的，不然不會(huì)放在同一個(gè)桶中，所以同一個(gè)桶中黃色標(biāo)記的位都是相同的。

等量擴(kuò)容

如果是等量擴(kuò)容（溢出桶太多引發(fā)的擴(kuò)容），那么數(shù)據(jù)遷移機(jī)制就會(huì)比較簡(jiǎn)單，就是將舊桶（含溢出桶）中的值遷移到新桶中。

這種擴(kuò)容和遷移的意義在于：當(dāng)溢出桶比較多而每個(gè)桶中的數(shù)據(jù)又不多時(shí)，可以通過(guò)等量擴(kuò)容和遷移讓數(shù)據(jù)更緊湊，從而減少溢出桶。

2.3 map不安全問(wèn)題

map 不是線程安全的。

在查找、賦值、遍歷、刪除的過(guò)程中都會(huì)檢測(cè)寫(xiě)標(biāo)志，一旦發(fā)現(xiàn)寫(xiě)標(biāo)志置位（等于1），則直接 panic。賦值和刪除函數(shù)在檢測(cè)完寫(xiě)標(biāo)志是復(fù)位之后，先將寫(xiě)標(biāo)志位置位，才會(huì)進(jìn)行之后的操作。

if h.flags&hashWriting ==0{throw("concurrent map writes") }

如果要使用線程安全的map, 就可以去了解一下sync.Map
這個(gè)就是加了讀寫(xiě)鎖的map, 但是一但加鎖, 對(duì)于性能必定有影響. 各種協(xié)程, 對(duì)于鎖的競(jìng)爭(zhēng)是很激烈的.

總結(jié)

以上是生活随笔為你收集整理的Go中的Map实现机制的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。