在開發(fā)過程中，map是必不可少的數(shù)據(jù)結(jié)構(gòu)，在Golang中，使用map或多或少會(huì)遇到與其他語言不一樣的體驗(yàn)，比如訪問不存在的元素會(huì)返回其類型的空值、map的大小究竟是多少，為什么會(huì)報(bào)"cannot take the address of"錯(cuò)誤，遍歷map的隨機(jī)性等等。
本文希望通過研究map的底層實(shí)現(xiàn)，以解答這些疑惑。
基于Golang 1.8.3

1. 數(shù)據(jù)結(jié)構(gòu)及內(nèi)存管理

hashmap的定義位于 src/runtime/hashmap.go 中，首先我們看下hashmap和bucket的定義：

type hmap struct {
 count  int // 元素的個(gè)數(shù)
 flags  uint8 // 狀態(tài)標(biāo)志
 B   uint8 // 可以最多容納 6.5 * 2 ^ B 個(gè)元素，6.5為裝載因子
 noverflow uint16 // 溢出的個(gè)數(shù)
 hash0  uint32 // 哈希種子
 
 buckets unsafe.Pointer // 桶的地址
 oldbuckets unsafe.Pointer // 舊桶的地址，用于擴(kuò)容
 nevacuate uintptr  // 搬遷進(jìn)度，小于nevacuate的已經(jīng)搬遷
 overflow *[2]*[]*bmap 
}

其中，overflow是一個(gè)指針，指向一個(gè)元素個(gè)數(shù)為2的數(shù)組，數(shù)組的類型是一個(gè)指針，指向一個(gè)slice，slice的元素是桶(bmap)的地址，這些桶都是溢出桶；為什么有兩個(gè)？因?yàn)镚o map在hash沖突過多時(shí)，會(huì)發(fā)生擴(kuò)容操作，為了不全量搬遷數(shù)據(jù)，使用了增量搬遷，[0]表示當(dāng)前使用的溢出桶集合，[1]是在發(fā)生擴(kuò)容時(shí)，保存了舊的溢出桶集合；overflow存在的意義在于防止溢出桶被gc。

// A bucket for a Go map.
type bmap struct {
 // 每個(gè)元素hash值的高8位，如果tophash[0] < minTopHash，表示這個(gè)桶的搬遷狀態(tài)
 tophash [bucketCnt]uint8
 // 接下來是8個(gè)key、8個(gè)value，但是我們不能直接看到；為了優(yōu)化對(duì)齊，go采用了key放在一起，value放在一起的存儲(chǔ)方式，
 // 再接下來是hash沖突發(fā)生時(shí)，下一個(gè)溢出桶的地址
}

tophash的存在是為了快速試錯(cuò)，畢竟只有8位，比較起來會(huì)快一點(diǎn)。

從定義可以看出，不同于STL中map以紅黑樹實(shí)現(xiàn)的方式，Golang采用了HashTable的實(shí)現(xiàn)，解決沖突采用的是鏈地址法。也就是說，使用數(shù)組+鏈表來實(shí)現(xiàn)map。特別的，對(duì)于一個(gè)key，幾個(gè)比較重要的計(jì)算公式為:

例如，對(duì)于B = 3，當(dāng)hash(key) = 4時(shí)， hashtop = 0， bucket = 4，當(dāng)hash(key) = 20時(shí)，hashtop = 0， bucket = 4；這個(gè)例子我們?cè)诎徇w過程還會(huì)用到。

內(nèi)存布局類似于這樣：

hashmap-buckets

2. 創(chuàng)建 - makemap

map的創(chuàng)建比較簡(jiǎn)單，在參數(shù)校驗(yàn)之后，需要找到合適的B來申請(qǐng)桶的內(nèi)存空間，接著便是穿件hmap這個(gè)結(jié)構(gòu)，以及對(duì)它的初始化。

makemap

3. 訪問 - mapaccess

對(duì)于給定的一個(gè)key，可以通過下面的操作找到它是否存在

image.png

方法定義為

// returns key, if not find, returns nil
func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer 
 
// returns key and exist. if not find, returns nil, false
func mapaccess2(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, bool)
 
// returns both key and value. if not find, returns nil, nil
func mapaccessK(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, unsafe.Pointer)

可見在找不到對(duì)應(yīng)key的情況下，會(huì)返回nil

4. 分配 - mapassign

為一個(gè)key分配空間的邏輯，大致與查找類似；但增加了寫保護(hù)和擴(kuò)容的操作；注意，分配過程和刪除過程都沒有在oldbuckets中查找，這是因?yàn)槭紫纫M(jìn)行擴(kuò)容判斷和操作；如下：

assign

擴(kuò)容是整個(gè)hashmap的核心算法，我們放在第6部分重點(diǎn)研究。

新建一個(gè)溢出桶，并將其拼接在當(dāng)前桶的尾部，實(shí)現(xiàn)了類似鏈表的操作：

// 獲取當(dāng)前桶的溢出桶
func (b *bmap) overflow(t *maptype) *bmap {
 return *(**bmap)(add(unsafe.Pointer(b), uintptr(t.bucketsize)-sys.PtrSize))
}
 
// 設(shè)置當(dāng)前桶的溢出桶
func (h *hmap) setoverflow(t *maptype, b, ovf *bmap) {
 h.incrnoverflow()
 if t.bucket.kind&kindNoPointers != 0 {
  h.createOverflow()
  //重點(diǎn)，這里講溢出桶append到overflow[0]的后面
  *h.overflow[0] = append(*h.overflow[0], ovf)
 }
 *(**bmap)(add(unsafe.Pointer(b), uintptr(t.bucketsize)-sys.PtrSize)) = ovf
}

5. 刪除 - mapdelete

刪除某個(gè)key的操作與分配類似，由于hashmap的存儲(chǔ)結(jié)構(gòu)是數(shù)組+鏈表，所以真正刪除key僅僅是將對(duì)應(yīng)的slot設(shè)置為empty，并沒有減少內(nèi)存；如下：

mapdelete

6. 擴(kuò)容 - growWork

首先，判斷是否需要擴(kuò)容的邏輯是

func (h *hmap) growing() bool {
 return h.oldbuckets != nil
}

何時(shí)h.oldbuckets不為nil呢？在分配assign邏輯中，當(dāng)沒有位置給key使用，而且滿足測(cè)試條件(裝載因子>6.5或有太多溢出通)時(shí)，會(huì)觸發(fā)hashGrow邏輯：

func hashGrow(t *maptype, h *hmap) {
 //判斷是否需要sameSizeGrow，否則"真"擴(kuò)
 bigger := uint8(1)
 if !overLoadFactor(int64(h.count), h.B) {
  bigger = 0
  h.flags |= sameSizeGrow
 }
  // 下面將buckets復(fù)制給oldbuckets
 oldbuckets := h.buckets
 newbuckets := newarray(t.bucket, 1<<(h.B+bigger))
 flags := h.flags &^ (iterator | oldIterator)
 if h.flags&iterator != 0 {
  flags |= oldIterator
 }
 // 更新hmap的變量
 h.B += bigger
 h.flags = flags
 h.oldbuckets = oldbuckets
 h.buckets = newbuckets
 h.nevacuate = 0
 h.noverflow = 0
  // 設(shè)置溢出桶
 if h.overflow != nil {
  if h.overflow[1] != nil {
   throw("overflow is not nil")
  }
// 交換溢出桶
  h.overflow[1] = h.overflow[0]
  h.overflow[0] = nil
 }
}

OK，下面正式進(jìn)入重點(diǎn)，擴(kuò)容階段；在assign和delete操作中，都會(huì)觸發(fā)擴(kuò)容growWork：

func growWork(t *maptype, h *hmap, bucket uintptr) {
 // 搬遷舊桶，這樣assign和delete都直接在新桶集合中進(jìn)行
 evacuate(t, h, bucket&h.oldbucketmask())
  //再搬遷一次搬遷過程中的桶
 if h.growing() {
  evacuate(t, h, h.nevacuate)
 }
}

6.1 搬遷過程

一般來說，新桶數(shù)組大小是原來的2倍(在!sameSizeGrow()條件下)，新桶數(shù)組前半段可以"類比"為舊桶，對(duì)于一個(gè)key，搬遷后落入哪一個(gè)索引中呢？

 假設(shè)舊桶數(shù)組大小為2^B， 新桶數(shù)組大小為2*2^B，對(duì)于某個(gè)hash值X
若 X & (2^B) == 0，說明 X < 2^B，那么它將落入與舊桶集合相同的索引xi中；
否則，它將落入xi + 2^B中。

例如，對(duì)于舊B = 3時(shí)，hash1 = 4，hash2 = 20，其搬遷結(jié)果類似這樣。

example.png

源碼中有些變量的命名比較簡(jiǎn)單，容易擾亂思路，我們注明一下便于理解。

搬遷過程如下：

evacuate

總結(jié)

到目前為止，Golang的map實(shí)現(xiàn)細(xì)節(jié)已經(jīng)分析完畢，但不包含迭代器相關(guān)操作。通過分析，我們了解了map是由數(shù)組+鏈表實(shí)現(xiàn)的HashTable，其大小和B息息相關(guān)，同時(shí)也了解了map的創(chuàng)建、查詢、分配、刪除以及擴(kuò)容搬遷原理?？偟膩碚f，Golang通過hashtop快速試錯(cuò)加快了查找過程，利用空間換時(shí)間的思想解決了擴(kuò)容的問題，利用將8個(gè)key(8個(gè)value)依次放置減少了padding空間等等。

到此這篇關(guān)于Golang 語言map底層實(shí)現(xiàn)原理解析的文章就介紹到這了,更多相關(guān)Golang map底層實(shí)現(xiàn)原理內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論