腳本之家服務器常用軟件

快捷導航

go語言常用的map是怎么實現的(原理)詳解

更新時間：2026年01月07日 09:11:34 作者：沒天賦不蕉綠

Go的map是一種高效的鍵值對存儲數據結構,其底層實現是一個哈希表,包括哈希函數、散列沖突處理、動態(tài)擴容等機制,以提供快速的鍵查找操作,這篇文章主要介紹了go語言常用的map是怎么實現(原理)的相關資料,需要的朋友可以參考下

前言

作為從java轉來的go學長，我們當初常用的hashmap八股背的再熟悉不過了，那go的map是怎么實現的呢？

為此我前往不可視境界線，探索了B站世界，結合了幾篇大佬們的博客文章以及源碼，最后肝出本文，希望大家多多支持，邪王真眼是最強的！

一、哈希沖突

首先，提到map就不得不提到哈希，也就不得不提到哈希沖突了，個人理解map本質上就是一種優(yōu)化后的哈希表，為了方便檢索，go和java皆是如此，并且兩者還有一個共同特點，二者解決哈希沖突的方式都是使用拉鏈法，而非開放尋址法

but，why？

我認為，使用拉鏈法的好處

容量更大，不管是java還是go，使用拉鏈法都允許一個下標上容納更多的節(jié)點
拉鏈法允許動態(tài)地調整桶中元素的數量，例如通過在達到一定條件時轉換為紅黑樹或擴容，添加溢出桶等
在實現上，拉鏈法相對于開放尋址法來說更為簡單直接。它不需要復雜的探測過程，只需在鏈表中順序查找即可

二、map的結構

go語言中的map其實就是一個指向hmap的指針，占用8個字節(jié)。所以map底層結構就是hmap ,hmap包含多個結構為bmap（桶）的bucket數組，當發(fā)生沖突的時候，會到正常桶里面的overflow指針所指向的溢出桶里面去找，Go語言中溢出桶也是一個動態(tài)數組形式，它是根據需要動態(tài)創(chuàng)建的。Go語言中處理沖突其實是采用了優(yōu)化的拉鏈法，鏈表中每個節(jié)點存儲的不是一個鍵值對，而是8個鍵值對

來看下map底層的代碼

// A header for a Go map.
type hmap struct {
   // Note: the format of the hmap is also encoded in cmd/compile/internal/reflectdata/reflect.go.
   // Make sure this stays in sync with the compiler's definition.
   count     int // ## live cells == size of map.  Must be first (used by len() builtin)
   flags     uint8
   B         uint8  // log_2 of ## of buckets (can hold up to loadFactor * 2^B items)
   noverflow uint16 // approximate number of overflow buckets; see incrnoverflow for details
   hash0     uint32 // hash seed

   buckets    unsafe.Pointer // array of 2^B Buckets. may be nil if count==0.
   oldbuckets unsafe.Pointer // previous bucket array of half the size, non-nil only when growing
   nevacuate  uintptr        // progress counter for evacuation (buckets less than this have been evacuated)

   extra *mapextra // optional fields
}

我們不需要關注所有的字段，只需要記住這幾個：

count：map中元素的個數，就是len（map）的值
flags：記錄map的一些狀態(tài)
B：計算map的桶數，就是2^B，比如B=3，那么桶數就是8
buckets：指向桶數組bmap的指針
oldbuckets：擴容時指向舊的桶數組，非擴容時為nil
nevacuate：等于舊桶數組大小時遷移完成
extra：指向溢出桶相關

下面再詳細關注一下bmap：

type bmap struct {
    topbits  [8]uint8 // 記錄了哈希值的高八位，在桶內檢索時需要
    keys     [8]keytype 
    values   [8]valuetype
    overflow uintptr // 存儲溢出桶，當8個kv都用完之后會把新寫入的寫到溢出桶，初始化時創(chuàng)建的溢出桶就存這里
}

再來關注一下這個tophash，我一開始沒搞明白它是干嘛用的，怎么來的

這張圖就很直觀了，通過hash函數得到hash值，這個tophash就是藍色的高8位，那紅色的低8位是干嘛的呢，在定位是桶數組的哪個桶時，我們就通過低8位快速定位到了我們的數組下標

三、map的訪問原理

這里我認為go中map的訪問邏輯要比java麻煩一些

1.判斷map是否為空或者無數據，若為空或者無數據返回對應的空值

2. map寫檢測，如果正處于寫狀態(tài)，表示此時不能進行操作，報fatal error

3.計算出hash值和掩碼

4.判斷當前map是否處于擴容狀態(tài)，如果在擴容執(zhí)行下面步驟:

4.1根據狀態(tài)位算判斷當前桶是否被遷移

4.2如果遷移，在新桶中查找

4.3未被遷移，在舊桶中查找

4.4根據掩碼找到的位置

ps：你是不是讀到這里好奇掩碼是什么？以下來自百度

5.依次遍歷桶以及溢出桶來查找key

5.1遍歷桶內的8個槽位

5.2比較該槽位的tophash和當前key的tophash是否相等

5.3相同，繼續(xù)比較key是否相同，相同則直接返回對應value

5.4不相同，查看這個槽位的狀態(tài)位是否為"后繼空狀態(tài)"（顧名思義，它是桶里最后一個槽位了后面都是空的，另外后面還會出現一種狀態(tài)就是本槽位是空）

5.5是，key在以后的槽中也沒有，這個key不存在，直接返回零值

5.6否，遍歷下一個槽位

6. 當前桶沒有找到，則遍歷溢出桶，用同樣的方式查找

四、map的賦值原理

我們平常使用map賦值時，有兩點需要注意：

1.map做賦值操作前一定要初始化，否則就panic

2.map不支持并發(fā)讀寫，注意不是并發(fā)讀，前面讀的過程我們也發(fā)現了它沒有修改狀態(tài)，不是寫狀態(tài)就不會有問題

過程：

1. map寫檢測，如果正處于寫狀態(tài)，表示此時不;能進行讀取，報fatal error

2.計算出hash值，將map置為寫狀態(tài)

3.判斷桶數組是否為空，若為空，初始化桶數組

4.目標桶查找

1.根據hash值找到桶的位置

2.判斷該當前是否處于擴容:

1.若正在擴容:遷移這個桶，并且還另外幫忙多遷移一個桶以及它的溢出桶

3.獲取目標桶的指針，計算出tophash,開始后面的key查找過程

5. key查找

1.遍歷桶和它的溢出桶的每個槽位，按下述方式查找

2.判斷槽位的tophash和目標tophash

1.不相等

1.槽位tophash為空，標記這個位置為侯選位置

2.槽位tophash的標志位為'后繼空狀態(tài)"，說明這個key之前沒有被插入過，插入 key/value

3. tophash標志位不為空，說明存儲著其他key,說明當前槽的tophash不符合，繼續(xù) 遍歷下一個槽

2.相等

1.判斷當前槽位的key與目標key是否相等

1.不相等，繼續(xù)遍歷下一-個槽位

2.相等，找到了目標key的位置，原來已存在鍵值對，則修改key對應的value, 然后執(zhí)行收尾程

6. key插入

1.若map中既沒有找到key,且根據這個key找到的桶及其這個桶的溢出桶中沒有空的槽位了，要申請一個新的溢出桶，在新申請的桶里插入

2.否則在找到的位置插入

7.收尾程序

1.再次判斷map的寫狀態(tài)

2.清除map的寫狀態(tài)

這里需要注意一點:申請一-個新的溢出桶的時候并不會一開始就創(chuàng)建一個溢出桶，因為map在初始化的時候會提前創(chuàng)建好一些溢出桶存儲在extra* mapextra字段,樣當出現溢出現象時候,這些下溢出桶會優(yōu)先被使用，只有預分配的溢出桶使用完了，才會新建溢出桶。

五、map的刪除

for {
   b.tophash[i] = emptyRest
   if i == 0 {
      if b == bOrig {
         break // beginning of initial bucket, we're done.
      }
      // Find previous bucket, continue at its last entry.
      c := b
      for b = bOrig; b.overflow(t) != c; b = b.overflow(t) {
      }
      i = bucketCnt - 1
   } else {
      i--
   }
   if b.tophash[i] != emptyOne {
      break
   }
}

map刪除的過程總體和訪問賦值差不多，主要不同點是，如果在找到了目標key,則把當前桶該槽位對應的key和value刪除,將該槽位的tophash置為emptyOne，如果發(fā)現當前槽位后面沒有元素,則將tophash設置為emptyRest,并循環(huán)向前檢查前一個元素，若前一個元素也為空,槽位狀態(tài)為emptyOne,則將前一個元素的tophash也設置為emptyRest。這樣做的目的是將emptyRest狀態(tài)盡可能地向前面的槽推進，這樣做是為了增加效率，因為在查找的時候發(fā)現了emptyRest狀態(tài)就不用繼續(xù)往后找了，因為后面沒有元素了。

六、map的擴容

先不去討論go是如何設計，如果你是go語言的設計師，在如此設計的數據結構和賦值刪除等邏輯的前提下，你認為什么時候應該擴容呢？

無非就兩種情況：

元素數量太多，已經出現或者將要出現哈希沖突太頻繁
元素的密度不夠緊湊，被刪除后剩余的空間太多需要重新整理空間

是的，能想到這兩點，你也可以當go語言的設計師了，并且根據這兩種情況，應該采取不同的擴容方式，即雙倍擴容，等量擴容

go語言觸發(fā)擴容的條件：

負載因子＞6.5
溢出桶數量過多

你是不是又想問什么是負載因子？

負載因子 = 哈希表中的元素數量 / 桶的數量

擴容函數：

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 = 0
      h.flags |= sameSizeGrow
   }
   oldbuckets := h.buckets
   newbuckets, nextOverflow := makeBucketArray(t, h.B+bigger, nil)

   flags := h.flags &^ (iterator | oldIterator)
   if h.flags&iterator != 0 {
      flags |= oldIterator
   }
   // commit the grow (atomic wrt gc)
   h.B += bigger
   h.flags = flags
   h.oldbuckets = oldbuckets
   h.buckets = newbuckets
   h.nevacuate = 0
   h.noverflow = 0

   if h.extra != nil && h.extra.overflow != nil {
      // Promote current overflow buckets to the old generation.
      if h.extra.oldoverflow != nil {
         throw("oldoverflow is not nil")
      }
      h.extra.oldoverflow = h.extra.overflow
      h.extra.overflow = nil
   }
   if nextOverflow != nil {
      if h.extra == nil {
         h.extra = new(mapextra)
      }
      h.extra.nextOverflow = nextOverflow
   }

   // the actual copying of the hash table data is done incrementally
   // by growWork() and evacuate().
}

其實只需要記住，和java不同，go采用漸進式擴容，不會一次性遷移所有的桶，而是一次遷移一點，每次寫入時都遷移兩個桶

等量擴容的桶數組下標是對應的