主頁 > 後端開發 > go map資料結構和原始碼詳解

go map資料結構和原始碼詳解

2020-09-17 17:43:15 後端開發

目錄

  • 1. 前言
  • 2. go map的資料結構
    • 2.1 核心結體體
    • 2.2 資料結構圖
  • 3. go map的常用操作
    • 3.1 創建
    • 3.2 插入或更新
    • 3.3 洗掉
    • 3.4 查找
    • 3.5 range迭代
      • 3.5.1 初始化迭代器mapiterinit()
      • 3.5.2 迭代程序mapiternext()
  • 4. go map的擴容縮容
    • 4.1 擴容縮容的基本原理
    • 4.2 為什么叫“偽縮容”？如何實作“真縮容”？
  • 5 Q&A關鍵知識點
    • 5.1 基本原理
    • 5.2 時間復雜度和空間復雜度分析

1. 前言

本文以go1.12.5版本分析，map相關的原始碼在runtime包的map開頭的幾個檔案中，主要為map.go，
go的map底層實作方式是hash表（C++的map是紅黑樹實作，而C++ 11新增的unordered_map則與go的map類似，都是hash實作），go map的資料被置入一個由桶組成的有序陣列中，每個桶最多可以存放8個key/value對，key的hash值(32位)的低階位用于在該陣列中定位到桶，而高8位則用于在桶中區分key/value對，
go map的hash表中的基本單位是桶，每個桶最多存8個鍵值對，超了，則會鏈接到額外的溢位桶，所以go map是基本資料結構是hash陣列+桶內的key-value陣列+溢位的桶鏈表
當hash表超過閾值需要擴容增長時，會分配一個新的陣列，新陣列的大小一般是舊陣列的2倍，這里從舊陣列將資料遷移到新陣列，不會一次全量拷貝，go會在每次讀寫Map時以桶為單位做動態搬遷疏散，

2. go map的資料結構

我們先了解基本的資料結構，后面再看原始碼就簡單多了，

2.1 核心結體體

map主要由兩個核心的結構，即基礎結構和桶實作：

  • hmap：map的基礎結構
  • bmap：嚴格來說hmap.buckets指向桶組成的陣列，每個桶的頭部是bmap，之后是8個key，再是8個value，最后是1個溢位指標，溢位指標指向額外的桶鏈表，用于存盤溢位的資料
const ( // 關鍵的變數
    bucketCntBits = 3
	bucketCnt     = 1 << bucketCntBits  // 一個桶最多存盤8個key-value對
	loadFactorNum = 13 // 擴散因子：loadFactorNum / loadFactorDen = 6.5，
	loadFactorDen = 2  // 即元素數量 >= (hash桶數量(2^hmp.B) * 6.5 / 8) 時，觸發擴容
)
// map的基礎資料結構
type hmap struct {
	count     int	 // map存盤的元素對計數，len()函式回傳此值，所以map的len()時間復雜度是O(1)
	flags     uint8  // 記錄幾個特殊的位標記，如當前是否有別的執行緒正在寫map、當前是否為相同大小的增長（擴容/縮容？）
	B         uint8  // hash桶buckets的數量為2^B個
	noverflow uint16 // 溢位的桶的數量的近似值
	hash0     uint32 // hash種子

	buckets    unsafe.Pointer // 指向2^B個桶組成的陣列的指標，資料存在這里
	oldbuckets unsafe.Pointer // 指向擴容前的舊buckets陣列，只在map增長時有效
	nevacuate  uintptr        // 計數器，標示擴容后搬遷的進度

	extra *mapextra // 保存溢位桶的鏈表和未使用的溢位桶陣列的首地址
}

// 桶的實作結構
type bmap struct {
	// tophash存盤桶內每個key的hash值的高位元組
	// tophash[0] < minTopHash表示桶的疏散狀態
	// 當前版本bucketCnt的值是8，一個桶最多存盤8個key-value對
	tophash [bucketCnt]uint8
	// 特別注意：
	// 實際分配記憶體時會申請一個更大的記憶體空間A，A的前8位元組為bmap
	// 后面依次跟8個key、8個value、1個溢位指標
	// map的桶結構實際指的是記憶體空間A
}

// map.go里很多函式的第1個入參是這個結構，從成員來看很明顯，此結構標示了鍵值對和桶的大小等必要資訊
// 有了這個結構的資訊，map.go的代碼就可以與鍵值對的具體資料型別解耦
// 所以map.go用記憶體偏移量和unsafe.Pointer指標來直接對記憶體進行存取，而無需關心key或value的具體型別
type maptype struct {
	typ        _type
	key        *_type
	elem       *_type
	bucket     *_type // internal type representing a hash bucket
	keysize    uint8  // size of key slot
	valuesize  uint8  // size of value slot
	bucketsize uint16 // size of bucket
	flags      uint32
}

C++使用模板可以根據不同的型別生成map的代碼，
golang則通過上述maptype結構體傳遞鍵值對的型別大小等資訊，從而map.go直接用指標操作對應大小的記憶體來實作全域一份map代碼同時適用于不同型別的鍵值對，這點上可以認為相比C++用模板實作map的方式，go map的目標檔案的代碼量會更小，

2.2 資料結構圖

map底層創建時，會初始化一個hmap結構體，同時分配一個足夠大的記憶體空間A，其中A的前段用于hash陣列，A的后段預留給溢位的桶，于是hmap.buckets指向hash陣列，即A的首地址；hmap.extra.nextOverflow初始時指向記憶體A中的后段，即hash陣列結尾的下一個桶，也即第1個預留的溢位桶，所以當hash沖突需要使用到新的溢位桶時，會優先使用上述預留的溢位桶，hmap.extra.nextOverflow依次往后偏移直到用完所有的溢位桶，才有可能會申請新的溢位桶空間，

上圖中，當需要分配一個溢位桶時，會優先從預留的溢位桶陣列里取一個出來鏈接到鏈表后面，這時不需要再次申請記憶體，但當預留的桶被用完了，則需要申請新的記憶體給溢位桶，

3. go map的常用操作

3.1 創建

使用make(map[k]v, hint)創建map時會呼叫makemap()函式，代碼邏輯比較簡單，
值得注意的是，makemap()創建的hash陣列，陣列的前面是hash表的空間，當hint >= 4時后面會追加2^(hint-4)個桶，之后再記憶體頁幀對齊又追加了若干個桶（參見2.2章節結構圖的hash陣列部分）
所以創建map時一次記憶體分配既分配了用戶預期大小的hash陣列，又追加了一定量的預留的溢位桶，還做了記憶體對齊，一舉多得，

// make(map[k]v, hint), hint即預分配大小
// 不傳hint時，如用new創建個預設容量為0的map時，makemap只初始化hmap結構，不分配hash陣列
func makemap(t *maptype, hint int, h *hmap) *hmap {
	// 省略部分代碼
	// 隨機hash種子
	h.hash0 = fastrand()

	// 2^h.B 為大于hint*6.5(擴容因子)的最小的2的冪
	B := uint8(0)
	// overLoadFactor(hint, B)只有一行代碼：return hint > bucketCnt && uintptr(hint) > loadFactorNum*(bucketShift(B)/loadFactorDen)
	// 即B的大小應滿足 hint <= (2^B) * 6.5
	// 一個桶能存8對key-value，所以這就表示B的初始值是保證這個map不需要擴容即可存下hint個元素對的最小的B值
	for overLoadFactor(hint, B) {
		B++
	}
	h.B = B

	// 這里分配hash陣列
	if h.B != 0 {
		var nextOverflow *bmap
		h.buckets, nextOverflow = makeBucketArray(t, h.B, nil)
		// makeBucketArray()會在hash陣列后面預分配一些溢位桶，
		// h.extra.nextOverflow用來保存上述溢位桶的首地址
		if nextOverflow != nil {
			h.extra = new(mapextra)
			h.extra.nextOverflow = nextOverflow
		}
	}

	return h
}

// 分配hash陣列
func makeBucketArray(t *maptype, b uint8, dirtyalloc unsafe.Pointer) (buckets unsafe.Pointer, nextOverflow *bmap) {
	base := bucketShift(b) // base代表用戶預期的桶的數量，即hash陣列的真實大小
	nbuckets := base // nbuckets表示實際分配的桶的數量，>= base，這就可能會追加一些溢位桶作為溢位的預留
	if b >= 4 {
		// 這里追加一定數量的桶，并做記憶體對齊
		nbuckets += bucketShift(b - 4)
		sz := t.bucket.size * nbuckets
		up := roundupsize(sz)
		if up != sz {
			nbuckets = up / t.bucket.size
		}
	}

	// 后面的代碼就是申請記憶體空間了，此處省略
	// 這里大家可以思考下這個陣列空間要怎么分配，其實就是n*sizeof(桶)，所以：
		// 每個桶前面是8位元組的tophash陣列，然后是8個key，再是8個value，最后放一個溢位指標
		// sizeof(桶) = 8 + 8*sizeof(key) + 8*sizeof(value) + 8
	
	return buckets, nextOverflow
}

3.2 插入或更新

go map的插入操作，呼叫mapassign()函式，
同學們或許在某些資料上了解過：

  • go map需要初始化才能使用，對空map插入會panic，hmap指標傳遞的方式，決定了map在使用前必須初始化
  • go map不支持并發讀寫，會panic，如果一定要并發，請用sync.Map或自己解決沖突

上述兩個限制，在mapassign()函式開頭能找到答案：

  1. 引數合法性檢測，計算hash值
func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
    // 不熟悉指標操作的同學，用指標傳參往往會踩空指標的坑
    // 這里大家可以思考下，為什么h要非空判斷？
    // 如果一定要在這里支持空map并檢測到map為空時自動初始化，應該怎么寫？
    // 提示：指標的指標
	if h == nil {
		panic(plainError("assignment to entry in nil map"))
	}
	// 在這里做并發判斷，檢測到并發寫時，拋例外
	// 注意：go map的并發檢測是偽檢測，并不保證所有的并發都會被檢測出來，而且這玩意是在運行期檢測，
	// 所以對map有并發要求時，應使用sync.map來代替普通map，通過加鎖來阻斷并發沖突
	if h.flags&hashWriting != 0 {
		throw("concurrent map writes")
	}
	hash := alg.hash(key, uintptr(h.hash0)) // 這里得到uint32的hash值
	h.flags ^= hashWriting // 置Writing標志，key寫入buckets后才會清除標志
	if h.buckets == nil { // map不能為空，但hash陣列可以初始是空的，這里會初始化
		h.buckets = newobject(t.bucket) // newarray(t.bucket, 1)
	}
	
	...
}
  1. 定位key在hash表中的位置
func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
    ...
    
again:
	bucket := hash & bucketMask(h.B) // 這里用hash值的低階位定位hash陣列的下標偏移量
	if h.growing() {
		growWork(t, h, bucket) // 這里是map的擴容縮容操作，我們在第4章單獨講
	}
	// 通過下標bucket，偏移定位到具體的桶
	b := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + bucket*uintptr(t.bucketsize)))
	top := tophash(hash) // 這里取高8位用于在桶內定位鍵值對
	
	...
}
  1. 進一步定位key可以插入的桶及桶中的位置
  • 兩輪回圈，外層回圈遍歷hash桶及其指向的溢位鏈表，內層回圈則在桶內遍歷（一個桶最多8個key-value對）
  • 有可能正好鏈表上的桶都滿了，這時inserti為nil，第4步會鏈接一個新的溢位桶進來
func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
    ...

    var inserti *uint8          // tophash插入位置
	var insertk unsafe.Pointer  // key插入位置
	var val unsafe.Pointer      // value插入位置
bucketloop:
	for {
		for i := uintptr(0); i < bucketCnt; i++ {
			if b.tophash[i] != top {
				if isEmpty(b.tophash[i]) && inserti == nil {
				    // 找到個空位，先記錄下tophash、key、value的插入位置
				    // 但要遍歷完才能確定要不要插入到這個位置，因為后面有可能有重復的元素
					inserti = &b.tophash[i]
					insertk = add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
					val = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))
				}
				if b.tophash[i] == emptyRest {
					break bucketloop // 遍歷完整個溢位鏈表，退出回圈
				}
				continue
			}
			k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
			if t.indirectkey() {
				k = *((*unsafe.Pointer)(k))
			}
			if !alg.equal(key, k) {
				continue
			}
			// 走到這里說明map里找到一個重復的key，更新key-value，跳到第5步
			if t.needkeyupdate() {
				typedmemmove(t.key, k, key)
			}
			val = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))
			goto done // 更新Key后跳到第5步
		}
		ovf := b.overflow(t)
		if ovf == nil {
			break // 遍歷完整個溢位鏈表，沒找到能插入的空位，結束回圈，下一步再追加一個溢位桶進來
		}
		b = ovf // 繼續遍歷下一個溢位桶
	}

	...
}
  1. 插入key
func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
    ...
    // 這里判斷要不要擴容，我們第4章再講
    if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
		hashGrow(t, h)
		goto again // Growing the table invalidates everything, so try again
	}

	if inserti == nil { // inserti == nil說明上1步沒找到空位，整個鏈表是滿的，這里添加一個新的溢位桶上去
		newb := h.newoverflow(t, b) // 分配新溢位桶，優先用3.1章節預留的溢位桶，用完了則分配一個新桶記憶體
		inserti = &newb.tophash[0]
		insertk = add(unsafe.Pointer(newb), dataOffset)
		val = add(insertk, bucketCnt*uintptr(t.keysize))
	}

	// 當key或value的型別大小超過一定值時，桶只存盤key或value的指標，這里分配空間并取指標
	if t.indirectkey() {
		kmem := newobject(t.key)
		*(*unsafe.Pointer)(insertk) = kmem
		insertk = kmem
	}
	if t.indirectvalue() {
		vmem := newobject(t.elem)
		*(*unsafe.Pointer)(val) = vmem
	}
	typedmemmove(t.key, insertk, key) // 在桶中對應位置插入key
	*inserti = top // 插入tophash，hash值高8位
	h.count++ // 插入了新的鍵值對，h.count數量+1

	...
}
  1. 結束插入
 func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
    ...
    
 done:
	if h.flags&hashWriting == 0 {
		throw("concurrent map writes")
	}
	h.flags &^= hashWriting // 釋放hashWriting標志位
	if t.indirectvalue() {
		val = *((*unsafe.Pointer)(val))
	}
	return val // 回傳value可插入位置的指標，注意，value還沒插入
}
  • 只插入了tophash和key，就結束了嗎？value還沒插入呢
  • 是的，mapassign()只插入tophash和key，并回傳val指標，編譯器會在呼叫mapassign()后用匯編往val插入value
  • google大佬這么騷氣的操作，是為了減少value值傳遞的次數嗎？

3.3 洗掉

  1. 洗掉與插入類似，前面的步驟都是引數和狀態判斷、定位key-value位置，然后clear對應的記憶體，不展開說，以下是幾個關鍵點：
  • 洗掉程序中也會置hashWriting標志
  • 當key/value過大時，hash表里存盤的是指標，這時候用軟洗掉，置指標為nil，資料交給gc去刪，當然，這是map的內部處理，外層是無感知的，拿到的都是值拷貝
  • 無論Key/value是值型別還是指標型別，洗掉操作都只影響hash表，外層已經拿到的資料不受影響，尤其是指標型別，外層的指標還能繼續使用
  1. 由于定位key位置的方式是查找tophash，所以洗掉操作對tophash的處理是關鍵：
  • map首先將對應位置的tophash[i]置為emptyOne，表示該位置已被洗掉
  • 如果tophash[i]不是整個鏈表的最后一個，則只置emptyOne標志，該位置被洗掉但未釋放，后續插入操作不能使用此位置
  • 如果tophash[i]是鏈表最后一個有效節點了，則把鏈表最后面的所有標志為emptyOne的位置，都置為emptyRest，置為emptyRest的位置可以在后續的插入操作中被使用，
  • 這種洗掉方式，以少量空間來避免桶鏈表和桶內的資料移動，事實上，go 資料一旦被插入到桶的確切位置，map是不會再移動該資料在桶中的位置了，
func mapdelete(t *maptype, h *hmap, key unsafe.Pointer) {
    ...

            b.tophash[i] = emptyOne // 先標記洗掉
			// 如果b.tophash[i]不是最后一個元素，則暫時先占著坑，emptyOne標記的位置暫時不能被插入新元素(見3.2章節插入函式)
			if i == bucketCnt-1 {
				if b.overflow(t) != nil && b.overflow(t).tophash[0] != emptyRest {
					goto notLast
				}
			} else {
				if b.tophash[i+1] != emptyRest {
					goto notLast
				}
			}
			for { // 如果b.tophash[i]是最后一個元素，則把末尾的emptyOne全部清除置為emptyRest
				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
				}
			}

    ...
}

3.4 查找

查找操作由mapaccess開頭的一組函式實作，前面的章節在插入和洗掉之前都得先定位查找到元素，邏輯是類似的，也比較簡單，就不細說了：

  • mapaccess1()：通過Key查找，回傳value指標，用于val := map[key]，未找到時回傳value型別的0值，
  • mapaccess2()：通過key查找，回傳value指標，以及bool型別的是否查找成功的標志，用于val, ok := map[key]，未找到時回傳value型別的0值，
  • mapaccessK()：通過key查找，回傳key和value指標，用于迭代器(range)，未找到時回傳空指標
  • mapaccess1_fat()，對mapaccess1()的封裝，區別是mapaccess1_fat()多了個zero引數，未找到時回傳zero
  • mapaccess2_fat()，也是對mapaccess1()的封裝，相比mapaccess1_fat()，本函式增加一個是否查找成功的標志

3.5 range迭代

map的迭代是通過hiter結構和對應的兩個輔助函式實作的，hiter結構由編譯器在呼叫輔助函式之前創建并傳入，每次迭代結果也由hiter結構傳回，下方的it即是hiter結構體的指標變數，

3.5.1 初始化迭代器mapiterinit()

mapiterinit()函式主要是決定我們從哪個位置開始迭代，為什么是從哪個位置，而不是直接從hash陣列頭部開始呢？《go程式設計語言》好像提到過，hash表中資料每次插入的位置是變化的（其實是因為實作的原因，一方面hash種子是隨機的，這導致相同的資料在不同的map變數內的hash值不同；另一方面即使同一個map變數內，資料洗掉再添加的位置也有可能變化，因為在同一個桶及溢位鏈表中資料的位置不分先后），所以為了防止用戶錯誤的依賴于每次迭代的順序，map作者干脆讓相同的map每次迭代的順序也是隨機的，
迭代順序隨機的實作方式也簡單，直接從隨機的一個位置開始就行了：

  • it.startBucket：這個是hash陣列的偏移量，表示遍歷從這個桶開始
  • it.offset：這個是桶內的偏移量，表示每個桶的遍歷都從這個偏移量開始

于是，map的遍歷程序如下：

  • 從hash陣列中第it.startBucket個桶開始，先遍歷hash桶，然后是這個桶的溢位鏈表，
  • 之后hash陣列偏移量+1，繼續前一步動作，
  • 遍歷每一個桶，無論是hash桶還是溢位桶，都從it.offset偏移量開始，（如果只是隨機一個開始的桶，range結果還是有序的；但每個桶都加it.offset偏移，這個輸出結果就有點撲朔迷離，大家可以親手試下，對同一個map多次range）
  • 當迭代器經過一輪回圈回到it.startBucket的位置，結束遍歷，
func mapiterinit(t *maptype, h *hmap, it *hiter) {
    ...
    
    // 隨機一個偏移量來開始
    r := uintptr(fastrand())
    if h.B > 31-bucketCntBits {
		r += uintptr(fastrand()) << 31
    }
	it.startBucket = r & bucketMask(h.B)
	it.offset = uint8(r >> h.B & (bucketCnt - 1))
	
	...
	
	mapiternext(it) // 初始化迭代器的同時也回傳第1對key/value
}

3.5.2 迭代程序mapiternext()

上一節迭代回圈的程序很清晰了，這里我們說明幾個重要的引數：

  • it.startBucket：開始的桶
  • it.offset：每個桶開始的偏移量
  • it.bptr：當前遍歷的桶
  • it.i：it.bptr已經遍歷的鍵值對數量，i初始為0，當i=8時表示這個桶遍歷完了，將it.bptr移向下一個桶
  • it.key：每次迭代的結果
  • it.value：每次迭代的結果

此外，迭代還需要關注擴容縮容的情況：

  • 如果是在迭代開始后才growing，這種情況當前的邏輯沒處理，迭代有可能例外，呃，go map不支持并發，
  • 如果是先growing，再開始迭代，這是有可能的，這種情況下，會先到舊hash表中檢查key對應的桶有沒有被疏散，未疏散則遍歷舊桶，已疏散則遍歷新hash表里對應的桶，

4. go map的擴容縮容

4.1 擴容縮容的基本原理

go map的擴容縮容都是grow相關的函式，這里擴容是真的，縮容是偽縮容，后面我會解釋，我們先看下觸發條件：

func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
    ...
    
    if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
		hashGrow(t, h)
		goto again // Growing the table invalidates everything, so try again
	}
	
	...
}

// overLoadFactor()回傳true則觸發擴容，即map的count大于hash桶數量(2^B)*6.5
func overLoadFactor(count int, B uint8) bool {
	return count > bucketCnt && uintptr(count) > loadFactorNum*(bucketShift(B)/loadFactorDen)
}

// tooManyOverflowBuckets()，顧名思義，溢位桶太多了觸發縮容
func tooManyOverflowBuckets(noverflow uint16, B uint8) bool {
	if B > 15 {
		B = 15
	}
	return noverflow >= uint16(1)<<(B&15)
}

map只在插入元素即mapassign()函式中對是否擴容縮容進行觸發，條件即是上面這段代碼：

  • 條件1：當前不處在growing狀態
  • 條件2-1：觸發擴容：map的資料量count大于hash桶數量(2B)*6.5，注意這里的(2B)只是hash陣列大小，不包括溢位的桶
  • 條件2-2：觸發縮容：溢位的桶數量noverflow>=32768(1<<15)或者>=hash陣列大小，

仔細觀察觸發的代碼，擴容和縮容是同一個函式，這是怎么做到的呢？在hashGrow()開始，會先判斷是否滿足擴容條件，如果滿足就表明這次是擴容，不滿足就一定是縮容條件觸發了，擴容和縮容剩下的邏輯，主要區別就在于容量變化，就是hmap.B引數，擴容時B+1則hash表容量擴大1倍，縮容時hash表容量不變，

  • h.oldbuckets：指向舊的hash陣列，即當前的h.buckets
  • h.buckets：指向新創建的hash陣列

到這里觸發的主要作業已經完成，接下來就是怎么把元素搬遷到新hash表里了，如果現在就一次全量搬遷過去，顯然接下來會有比較長的一段時間map被占用（不支持并發），所以搬遷的作業是異步增量搬遷的，
在插入和洗掉的函式內都有下面一段代碼用于在每次插入和洗掉操作時，執行一次搬遷作業：

    if h.growing() { // 當前處于搬遷狀態
		growWork(t, h, bucket) // 呼叫搬遷函式
	}
	
func growWork(t *maptype, h *hmap, bucket uintptr) {
	// 將當前需要處理的桶搬遷
	evacuate(t, h, bucket&h.oldbucketmask())

	if h.growing() { // 再多搬遷一個桶
		evacuate(t, h, h.nevacuate)
	}
}
  • 每執行一次插入或洗掉，都會呼叫growWork搬遷0~2個hash桶（有可能這次需要搬遷的2個桶在此之前都被搬過了）
  • 搬遷是以hash桶為單位的，包含對應的hash桶和這個桶的溢位鏈表
  • 被delete掉的元素(emptyone標志)會被舍棄（這是縮容的關鍵）

4.2 為什么叫“偽縮容”？如何實作“真縮容”？

現在可以解釋為什么我把map的縮容叫做偽縮容了：因為縮容僅僅針對溢位桶太多的情況，觸發縮容時hash陣列的大小不變，即hash陣列所占用的空間只增不減，也就是說，如果我們把一個已經增長到很大的map的元素挨個全部洗掉掉，hash表所占用的記憶體空間也不會被釋放，

所以如果要實作“真縮容”，需自己實作縮容搬遷，即創建一個較小的map，將需要縮容的map的元素挨個搬遷過來：

// go map縮容代碼示例
myMap := make(map[int]int, 1000000)

// 假設這里我們對bigMap做了很多次插入，之后又做了很多次洗掉，此時bigMap的元素數量遠小于hash表大小
// 接下來我們開始縮容
smallMap := make(map[int]int, len(myMap))
for k, v := range myMap {
    smallMap[k] = v
}
myMap = smallMap // 縮容完成，原來的map被我們丟棄，交給gc去清理

5 Q&A關鍵知識點

5.1 基本原理

  • 底層是hash實作，資料結構為hash陣列 + 桶 + 溢位的桶鏈表，每個桶存盤最多8個key-value對
  • 查找和插入的原理：key的hash值（低階位）與桶數量相與，得到key所在的hash桶，再用key的高8位與桶中的tophash[i]對比，相同則進一步對比key值，key值相等則找到
  • go map不支持并發，插入、洗掉、搬遷等操作會置writing標志，檢測到并發直接panic
  • 每次擴容hash表增大1倍，hash表只增不減
  • 支持有限縮容，delete操作只置洗掉標志位，釋放溢位桶的空間依靠觸發縮容來實作，
  • map在使用前必須初始化，否則panic：已初始化的map是make(map[key]value)或make(map[key]value, hint)這兩種形式，而new或var xxx map[key]value這兩種形式是未初始化的，直接使用會panic，

5.2 時間復雜度和空間復雜度分析

時間復雜度，go map是hash實作，我們先不管具體原理，江湖套路hash實作的就叫它O(1)的時間復雜度：

  • 正常情況，且不考慮擴容狀態，復雜度O(1)：通過hash值定位桶是O(1)，一個桶最多8個元素，合理的hash演算法應該能把元素相對均勻散列，所以溢位鏈表（如果有）也不會太長，所以雖然在桶和溢位鏈表上定位key是遍歷，考慮到數量小也可以認為是O(1)
  • 正常情況，處于擴容狀態時，復雜度也是O(1)：相比于上一種狀態，擴容會增加搬遷最多2個桶和溢位鏈表的時間消耗，當溢位鏈表不太長時，復雜度也可以認為是O(1)
  • 極端情況，散列極不均勻，大部分資料被集中在一條散列鏈表上，復雜度退化為O(n)，

go采用的hash演算法應是很成熟的演算法，極端情況暫不考慮，所以綜合情況下go map的時間復雜度應為O(1)

空間復雜度分析：
首先我們不考慮因洗掉大量元素導致的空間浪費情況（這種情況現在go是留給程式員自己解決），只考慮一個持續增長狀態的map的一個空間使用率：
由于溢位桶數量超過hash桶數量時會觸發縮容，所以最壞的情況是資料被集中在一條鏈上，hash表基本是空的，這時空間浪費O(n)，
最好的情況下，資料均勻散列在hash表上，沒有元素溢位，這時最好的空間復雜度就是擴散因子決定了，當前go的擴散因子由全域變數決定，即loadFactorNum/loadFactorDen = 6.5，即平均每個hash桶被分配到6.5個元素以上時，開始擴容，所以最小的空間浪費是(8-6.5)/8 = 0.1875，即O(0.1875n)

結論：go map的空間復雜度（指除去正常存盤元素所需空間之外的空間浪費）是O(0.1875n) ~ O(n)之間，

轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/67378.html

標籤：Go

上一篇：GO基礎之切片

下一篇：GO基礎之Map

標籤雲
其他(157675) Python(38076) JavaScript(25376) Java(17977) C(15215) 區塊鏈(8255) C＃(7972) AI(7469) 爪哇(7425) MySQL(7132) html(6777) 基礎類(6313) sql(6102) 熊猫(6058) PHP(5869) 数组(5741) R(5409) Linux(5327) 反应(5209) 腳本語言(PerlPython)(5129) 非技術區(4971) Android(4554) 数据框(4311) css(4259) 节点.js(4032) C語言(3288) json(3245) 列表(3129) 扑(3119) C++語言(3117) 安卓(2998) 打字稿(2995) VBA(2789) Java相關(2746) 疑難問題(2699) 细绳(2522) 單片機工控(2479) iOS(2429) ASP.NET(2402) MongoDB(2323) 麻木的(2285) 正则表达式(2254) 字典(2211) 循环(2198) 迅速(2185) 擅长(2169) 镖(2155) 功能(1967) .NET技术(1958) Web開發(1951) python-3.x(1918) HtmlCss(1915) 弹簧靴(1913) C++(1909) xml(1889) PostgreSQL(1872) .NETCore(1853) 谷歌表格(1846) Unity3D(1843) for循环(1842)

熱門瀏覽
  • 【C++】Microsoft C++、C 和匯編程式檔案

    ......

    uj5u.com 2020-09-10 00:57:23 more
  • 例外宣告

    相比于斷言適用于排除邏輯上不可能存在的狀態，例外通常是用于邏輯上可能發生的錯誤。 例外宣告 Item 1：當函式不可能拋出例外或不能接受拋出例外時，使用noexcept 理由 如果不打算拋出例外的話，程式就會認為無法處理這種錯誤，并且應當盡早終止，如此可以有效地阻止例外的傳播與擴散。 示例 //不可 ......

    uj5u.com 2020-09-10 00:57:27 more
  • Codeforces 1400E Clear the Multiset(貪心 + 分治)

    鏈接：https://codeforces.com/problemset/problem/1400/E 來源：Codeforces 思路：給你一個陣列，現在你可以進行兩種操作，操作1：將一段沒有 0 的區間進行減一的操作，操作2：將 i 位置上的元素歸零。最終問：將這個陣列的全部元素歸零后操作的最少 ......

    uj5u.com 2020-09-10 00:57:30 more
  • UVA11610 【Reverse Prime】

    本人看到此題沒有翻譯，就附帶了一個自己的翻譯版本 思考 這一題，它的第一個要求是找出所有 $7$ 位反向質數及其質因數的個數。 我們應該需要質數篩篩選1~$10^{7}$的所有數，這里就不慢慢介紹了。但是，重讀題，我們突然發現反向質數都是 $7$ 位，而將它反過來后的數字卻是 $6$ 位數，這就說明 ......

    uj5u.com 2020-09-10 00:57:36 more
  • 統計區間素數數量

    1 #pragma GCC optimize(2) 2 #include <bits/stdc++.h> 3 using namespace std; 4 bool isprime[1000000010]; 5 vector<int> prime; 6 inline int getlist(int ......

    uj5u.com 2020-09-10 00:57:47 more
  • C/C++編程筆記：C++中的 const 變數詳解，教你正確認識const用法

    1、C中的const 1、區域const變數存放在堆疊區中，會分配記憶體（也就是說可以通過地址間接修改變數的值）。測驗代碼如下： 運行結果： 2、全域const變數存放在只讀資料段（不能通過地址修改，會發生寫入錯誤）， 默認為外部聯編，可以給其他源檔案使用（需要用extern關鍵字修飾） 運行結果： ......

    uj5u.com 2020-09-10 00:58:04 more
  • 【C++犯錯記錄】VS2019 MFC添加資源不懂如何修改資源宏ID

    1. 首先在資源視圖中，添加資源 2. 點擊新添加的資源，復制自動生成的ID 3. 在解決方案資源管理器中找到Resource.h檔案，編輯，使用整個專案搜索和替換的方式快速替換 宏宣告 4. Ctrl+Shift+F 全域搜索，點擊查找全部，然后逐個替換 5. 為什么使用搜索替換而不使用屬性視窗直 ......

    uj5u.com 2020-09-10 00:59:11 more
  • 【C++犯錯記錄】VS2019 MFC不懂的批量添加資源

    1. 打開資源頭檔案Resource.h，在其中預先定義好宏 ID（不清楚其實ID值應該設定多少，可以先新建一個相同的資源項，再在這個資源的ID值的基礎上遞增即可） 2. 在資源視圖中選中專案資源，按F7編輯資源檔案，按 ID 型別 相對路徑的形式添加 資源。（別忘了先把檔案拷貝到專案中的res檔案 ......

    uj5u.com 2020-09-10 01:00:19 more
  • C/C++編程筆記：關于C++的參考型別，專供新手入門使用

    今天要講的是C++中我最喜歡的一個用法——參考，也叫別名。 參考就是給一個變數名取一個變數名，方便我們間接地使用這個變數。我們可以給一個變數創建N個參考，這N + 1個變數共享了同一塊記憶體區域。(參考型別的變數會占用記憶體空間，占用的記憶體空間的大小和指標型別的大小是相同的。雖然參考是一個物件的別名，但 ......

    uj5u.com 2020-09-10 01:00:22 more
  • 【C/C++編程筆記】從頭開始學習C ++：初學者完整指南

    眾所周知，C ++的學習曲線陡峭，但是花時間學習這種語言將為您的職業帶來奇跡，并使您與其他開發人員區分開。您會更輕松地學習新語言，形成真正的解決問題的技能，并在編程的基礎上打下堅實的基礎。 C ++將幫助您養成良好的編程習慣（即清晰一致的編碼風格，在撰寫代碼時注釋代碼，并限制類內部的可見性），并且由 ......

    uj5u.com 2020-09-10 01:00:41 more
最新发布
  • Rust中的智能指標:Box<T> Rc<T> Arc<T> Cell<T> RefCell<T> Weak

    Rust中的智能指標是什么 智能指標（smart pointers）是一類資料結構，是擁有資料所有權和額外功能的指標。是指標的進一步發展 指標（pointer）是一個包含記憶體地址的變數的通用概念。這個地址參考，或 ” 指向”（points at）一些其 他資料 。參考以 & 符號為標志并借用了他們所 ......

    uj5u.com 2023-04-20 07:24:10 more
  • Java的值傳遞和參考傳遞

    值傳遞不會改變本身，參考傳遞（如果傳遞的值需要實體化到堆里）如果發生修改了會改變本身。 1.基本資料型別都是值傳遞 package com.example.basic; public class Test { public static void main(String[] args) { int ......

    uj5u.com 2023-04-20 07:24:04 more
  • [2]SpinalHDL教程——Scala簡單入門

    第一個 Scala 程式 shell里面輸入 $ scala scala> 1 + 1 res0: Int = 2 scala> println("Hello World!") Hello World! 檔案形式 object HelloWorld { /* 這是我的第一個 Scala 程式 * 以 ......

    uj5u.com 2023-04-20 07:23:58 more
  • 理解函式指標和回呼函式

    理解 函式指標 指向函式的指標。比如： 理解函式指標的偽代碼 void (*p)(int type, char *data); // 定義一個函式指標p void func(int type, char *data); // 宣告一個函式func p = func; // 將指標p指向函式func ......

    uj5u.com 2023-04-20 07:23:52 more
  • Django筆記二十五之資料庫函式之日期函式

    本文首發于公眾號：Hunter后端 原文鏈接：Django筆記二十五之資料庫函式之日期函式 日期函式主要介紹兩個大類，Extract() 和 Trunc() Extract() 函式作用是提取日期，比如我們可以提取一個日期欄位的年份，月份，日等資料 Trunc() 的作用則是截取，比如 2022-0 ......

    uj5u.com 2023-04-20 07:23:45 more
  • 一天吃透JVM面試八股文

    什么是JVM？ JVM，全稱Java Virtual Machine（Java虛擬機），是通過在實際的計算機上仿真模擬各種計算機功能來實作的。由一套位元組碼指令集、一組暫存器、一個堆疊、一個垃圾回收堆和一個存盤方法域等組成。JVM屏蔽了與作業系統平臺相關的資訊，使得Java程式只需要生成在Java虛擬機 ......

    uj5u.com 2023-04-20 07:23:31 more
  • 使用Java接入小程式訂閱訊息！

    更新完微信服務號的模板訊息之后，我又趕緊把微信小程式的訂閱訊息給實作了！之前我一直以為微信小程式也是要企業才能申請，沒想到小程式個人就能申請。 訊息推送平臺🔥推送下發【郵件】【短信】【微信服務號】【微信小程式】【企業微信】【釘釘】等訊息型別。 https://gitee.com/zhongfuch ......

    uj5u.com 2023-04-20 07:22:59 more
  • java -- 緩沖流、轉換流、序列化流

    緩沖流 緩沖流, 也叫高效流, 按照資料型別分類： 位元組緩沖流：BufferedInputStream，BufferedOutputStream 字符緩沖流：BufferedReader，BufferedWriter 緩沖流的基本原理，是在創建流物件時，會創建一個內置的默認大小的緩沖區陣列，通過緩沖 ......

    uj5u.com 2023-04-20 07:22:49 more
  • Java-SpringBoot-Range請求頭設定實作視頻分段傳輸

    老實說，人太懶了，現在基本都不喜歡寫筆記了，但是網上有關Range請求頭的文章都太水了 下面是抄的一段StackOverflow的代碼...自己大修改過的，寫的注釋挺全的，應該直接看得懂，就不解釋了 寫的不好...只是希望能給視頻網站開發的新手一點點幫助吧. 業務場景：視頻分段傳輸、視頻多段傳輸（理 ......

    uj5u.com 2023-04-20 07:22:42 more
  • Windows 10開發教程_編程入門自學教程_菜鳥教程-免費教程分享

    教程簡介 Windows 10開發入門教程 - 從簡單的步驟了解Windows 10開發，從基本到高級概念，包括簡介，UWP，第一個應用程式，商店，XAML控制元件，資料系結，XAML性能，自適應設計，自適應UI，自適應代碼，檔案管理，SQLite資料庫，應用程式到應用程式通信，應用程式本地化，應用程式 ......

    uj5u.com 2023-04-20 07:22:35 more

Copyright © 2010-2020 有解無憂