国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

深度解密Go語言之 map

番茄西紅柿 / 1350人閱讀

摘要:當(dāng)然,哈希查找表的平均查找效率是,如果哈希函數(shù)設(shè)計的很好,最壞的情況基本不會出現(xiàn)。選擇函數(shù)主要考察的是兩點性能碰撞概率。再用哈希值的高位,找到此在中的位置,這是在尋找已有的。

這篇文章主要講 map 的賦值、刪除、查詢、擴(kuò)容的具體執(zhí)行過程,仍然是從底層的角度展開。結(jié)合源碼,看完本文一定會徹底明白 map 底層原理。

我要說明的是,這里對 map 的基本用法涉及比較少,我相信可以通過閱讀其他入門書籍了解。本文的內(nèi)容比較深入,但是由于我畫了各種圖,我相信很容易看懂。

什么是 map

維基百科里這樣定義 map:

In computer science, an associative array, map, symbol table, or dictionary is an abstract data type composed of a collection of (key, value) pairs, such that each possible key appears at most once in the collection.

簡單說明一下:在計算機(jī)科學(xué)里,被稱為相關(guān)數(shù)組、map、符號表或者字典,是由一組 對組成的抽象數(shù)據(jù)結(jié)構(gòu),并且同一個 key 只會出現(xiàn)一次。

有兩個關(guān)鍵點:map 是由 key-value 對組成的;key 只會出現(xiàn)一次。

和 map 相關(guān)的操作主要是:

    增加一個 k-v 對 —— Add or insert;

    刪除一個 k-v 對 —— Remove or delete;

    修改某個 k 對應(yīng)的 v —— Reassign;

    查詢某個 k 對應(yīng)的 v —— Lookup;

簡單說就是最基本的 增刪查改。

map 的設(shè)計也被稱為 “The dictionary problem”,它的任務(wù)是設(shè)計一種數(shù)據(jù)結(jié)構(gòu)用來維護(hù)一個集合的數(shù)據(jù),并且可以同時對集合進(jìn)行增刪查改的操作。最主要的數(shù)據(jù)結(jié)構(gòu)有兩種:哈希查找表(Hash table)、搜索樹(Search tree)。

哈希查找表用一個哈希函數(shù)將 key 分配到不同的桶(bucket,也就是數(shù)組的不同 index)。這樣,開銷主要在哈希函數(shù)的計算以及數(shù)組的常數(shù)訪問時間。在很多場景下,哈希查找表的性能很高。

哈希查找表一般會存在“碰撞”的問題,就是說不同的 key 被哈希到了同一個 bucket。一般有兩種應(yīng)對方法:鏈表法開放地址法鏈表法將一個 bucket 實現(xiàn)成一個鏈表,落在同一個 bucket 中的 key 都會插入這個鏈表。開放地址法則是碰撞發(fā)生后,通過一定的規(guī)律,在數(shù)組的后面挑選“空位”,用來放置新的 key。

搜索樹法一般采用自平衡搜索樹,包括:AVL 樹,紅黑樹。面試時經(jīng)常會被問到,甚至被要求手寫紅黑樹代碼,很多時候,面試官自己都寫不上來,非常過分。

自平衡搜索樹法的最差搜索效率是 O(logN),而哈希查找表最差是 O(N)。當(dāng)然,哈希查找表的平均查找效率是 O(1),如果哈希函數(shù)設(shè)計的很好,最壞的情況基本不會出現(xiàn)。還有一點,遍歷自平衡搜索樹,返回的 key 序列,一般會按照從小到大的順序;而哈希查找表則是亂序的。

為什么要用 map

從 Go 語言官方博客摘錄一段話:

One of the most useful data structures in computer science is the hash table. Many hash table implementations exist with varying properties, but in general they offer fast lookups, adds, and deletes. Go provides a built-in map type that implements a hash table.

hash table 是計算機(jī)數(shù)據(jù)結(jié)構(gòu)中一個最重要的設(shè)計。大部分 hash table 都實現(xiàn)了快速查找、添加、刪除的功能。Go 語言內(nèi)置的 map 實現(xiàn)了上述所有功能。

很難想象寫一個程序不使用 map,以至于在回答為什么要用 map 這個問題上犯了難。

所以,到底為什么要用 map 呢?因為它太強(qiáng)大了,各種增刪查改的操作效率非常高。

map 的底層如何實現(xiàn)

首先聲明我用的 Go 版本:

go version go1.9.2 darwin/amd64

前面說了 map 實現(xiàn)的幾種方案,Go 語言采用的是哈希查找表,并且使用鏈表解決哈希沖突。

接下來我們要探索 map 的核心原理,一窺它的內(nèi)部結(jié)構(gòu)。

map 內(nèi)存模型

在源碼中,表示 map 的結(jié)構(gòu)體是 hmap,它是 hashmap 的“縮寫”:

// A header for a Go map.
type hmap struct {
    // 元素個數(shù),調(diào)用 len(map) 時,直接返回此值
	count     int
	flags     uint8
	// buckets 的對數(shù) log_2
	B         uint8
	// overflow 的 bucket 近似數(shù)
	noverflow uint16
	// 計算 key 的哈希的時候會傳入哈希函數(shù)
	hash0     uint32
    // 指向 buckets 數(shù)組,大小為 2^B
    // 如果元素個數(shù)為0,就為 nil
	buckets    unsafe.Pointer
	// 擴(kuò)容的時候,buckets 長度會是 oldbuckets 的兩倍
	oldbuckets unsafe.Pointer
	// 指示擴(kuò)容進(jìn)度,小于此地址的 buckets 遷移完成
	nevacuate  uintptr
	extra *mapextra // optional fields
}

說明一下,B 是 buckets 數(shù)組的長度的對數(shù),也就是說 buckets 數(shù)組的長度就是 2^B。bucket 里面存儲了 key 和 value,后面會再講。

buckets 是一個指針,最終它指向的是一個結(jié)構(gòu)體:

type bmap struct {
	tophash [bucketCnt]uint8
}

但這只是表面(src/runtime/hashmap.go)的結(jié)構(gòu),編譯期間會給它加料,動態(tài)地創(chuàng)建一個新的結(jié)構(gòu):

type bmap struct {
    topbits  [8]uint8
    keys     [8]keytype
    values   [8]valuetype
    pad      uintptr
    overflow uintptr
}

bmap 就是我們常說的“桶”,桶里面會最多裝 8 個 key,這些 key 之所以會落入同一個桶,是因為它們經(jīng)過哈希計算后,哈希結(jié)果是“一類”的。在桶內(nèi),又會根據(jù) key 計算出來的 hash 值的高 8 位來決定 key 到底落入桶內(nèi)的哪個位置(一個桶內(nèi)最多有8個位置)。

來一個整體的圖:

當(dāng) map 的 key 和 value 都不是指針,并且 size 都小于 128 字節(jié)的情況下,會把 bmap 標(biāo)記為不含指針,這樣可以避免 gc 時掃描整個 hmap。但是,我們看 bmap 其實有一個 overflow 的字段,是指針類型的,破壞了 bmap 不含指針的設(shè)想,這時會把 overflow 移動到 extra 字段來。

type mapextra struct {
	// overflow[0] contains overflow buckets for hmap.buckets.
	// overflow[1] contains overflow buckets for hmap.oldbuckets.
	overflow [2]*[]*bmap

	// nextOverflow 包含空閑的 overflow bucket,這是預(yù)分配的 bucket
	nextOverflow *bmap
}

bmap 是存放 k-v 的地方,我們把視角拉近,仔細(xì)看 bmap 的內(nèi)部組成。

上圖就是 bucket 的內(nèi)存模型,HOB Hash 指的就是 top hash。 注意到 key 和 value 是各自放在一起的,并不是 key/value/key/value/... 這樣的形式。源碼里說明這樣的好處是在某些情況下可以省略掉 padding 字段,節(jié)省內(nèi)存空間。

例如,有這樣一個類型的 map:

map[int64]int8

如果按照 key/value/key/value/... 這樣的模式存儲,那在每一個 key/value 對之后都要額外 padding 7 個字節(jié);而將所有的 key,value 分別綁定到一起,這種形式 key/key/.../value/value/...,則只需要在最后添加 padding。

每個 bucket 設(shè)計成最多只能放 8 個 key-value 對,如果有第 9 個 key-value 落入當(dāng)前的 bucket,那就需要再構(gòu)建一個 bucket ,通過 overflow 指針連接起來。

創(chuàng)建 map

從語法層面上來說,創(chuàng)建 map 很簡單:

ageMp := make(map[string]int)
// 指定 map 長度
ageMp := make(map[string]int, 8)

// ageMp 為 nil,不能向其添加元素,會直接panic
var ageMp map[string]int

通過匯編語言可以看到,實際上底層調(diào)用的是 makemap 函數(shù),主要做的工作就是初始化 hmap 結(jié)構(gòu)體的各種字段,例如計算 B 的大小,設(shè)置哈希種子 hash0 等等。

func makemap(t *maptype, hint int64, h *hmap, bucket unsafe.Pointer) *hmap {
	// 省略各種條件檢查...

	// 找到一個 B,使得 map 的裝載因子在正常范圍內(nèi)
	B := uint8(0)
	for ; overLoadFactor(hint, B); B++ {
	}

	// 初始化 hash table
	// 如果 B 等于 0,那么 buckets 就會在賦值的時候再分配
	// 如果長度比較大,分配內(nèi)存會花費長一點
	buckets := bucket
	var extra *mapextra
	if B != 0 {
		var nextOverflow *bmap
		buckets, nextOverflow = makeBucketArray(t, B)
		if nextOverflow != nil {
			extra = new(mapextra)
			extra.nextOverflow = nextOverflow
		}
	}

	// 初始化 hamp
	if h == nil {
		h = (*hmap)(newobject(t.hmap))
	}
	h.count = 0
	h.B = B
	h.extra = extra
	h.flags = 0
	h.hash0 = fastrand()
	h.buckets = buckets
	h.oldbuckets = nil
	h.nevacuate = 0
	h.noverflow = 0

	return h
}

注意,這個函數(shù)返回的結(jié)果:*hmap,它是一個指針,而我們之前講過的 makeslice 函數(shù)返回的是 Slice 結(jié)構(gòu)體:

func makeslice(et *_type, len, cap int) slice

回顧一下 slice 的結(jié)構(gòu)體定義:

// runtime/slice.go
type slice struct {
    array unsafe.Pointer // 元素指針
    len   int // 長度 
    cap   int // 容量
}

結(jié)構(gòu)體內(nèi)部包含底層的數(shù)據(jù)指針。

makemap 和 makeslice 的區(qū)別,帶來一個不同點:當(dāng) map 和 slice 作為函數(shù)參數(shù)時,在函數(shù)參數(shù)內(nèi)部對 map 的操作會影響 map 自身;而對 slice 卻不會(之前講 slice 的文章里有講過)。

主要原因:一個是指針(*hmap),一個是結(jié)構(gòu)體(slice)。Go 語言中的函數(shù)傳參都是值傳遞,在函數(shù)內(nèi)部,參數(shù)會被 copy 到本地。*hmap指針 copy 完之后,仍然指向同一個 map,因此函數(shù)內(nèi)部對 map 的操作會影響實參。而 slice 被 copy 后,會成為一個新的 slice,對它進(jìn)行的操作不會影響到實參。

哈希函數(shù)

map 的一個關(guān)鍵點在于,哈希函數(shù)的選擇。在程序啟動時,會檢測 cpu 是否支持 aes,如果支持,則使用 aes hash,否則使用 memhash。這是在函數(shù) alginit() 中完成,位于路徑:src/runtime/alg.go 下。

hash 函數(shù),有加密型和非加密型。 加密型的一般用于加密數(shù)據(jù)、數(shù)字摘要等,典型代表就是 md5、sha1、sha256、aes256 這種; 非加密型的一般就是查找。在 map 的應(yīng)用場景中,用的是查找。 選擇 hash 函數(shù)主要考察的是兩點:性能、碰撞概率。

之前我們講過,表示類型的結(jié)構(gòu)體:

type _type struct {
	size       uintptr
	ptrdata    uintptr // size of memory prefix holding all pointers
	hash       uint32
	tflag      tflag
	align      uint8
	fieldalign uint8
	kind       uint8
	alg        *typeAlg
	gcdata    *byte
	str       nameOff
	ptrToThis typeOff
}

其中 alg 字段就和哈希相關(guān),它是指向如下結(jié)構(gòu)體的指針:

// src/runtime/alg.go
type typeAlg struct {
	// (ptr to object, seed) -> hash
	hash func(unsafe.Pointer, uintptr) uintptr
	// (ptr to object A, ptr to object B) -> ==);equal func(unsafe.Pointer, unsafe.Pointer) bool
}

typeAlg 包含兩個函數(shù),hash 函數(shù)計算類型的哈希值,而 equal 函數(shù)則計算兩個類型是否“哈希相等”。

對于 string 類型,它的 hash、equal 函數(shù)如下:

func strhash(a unsafe.Pointer, h uintptr) uintptr {
	x := (*stringStruct)(a)
	return memhash(x.str, h, uintptr(x.len))
}

func strequal(p, q unsafe.Pointer) bool {
	return *(*string)(p) == *(*string)(q)
}

根據(jù) key 的類型,_type 結(jié)構(gòu)體的 alg 字段會被設(shè)置對應(yīng)類型的 hash 和 equal 函數(shù)。

key 定位過程

key 經(jīng)過哈希計算后得到哈希值,共 64 個 bit 位(64位機(jī),32位機(jī)就不討論了,現(xiàn)在主流都是64位機(jī)),計算它到底要落在哪個桶時,只會用到最后 B 個 bit 位。還記得前面提到過的 B 嗎?如果 B = 5,那么桶的數(shù)量,也就是 buckets 數(shù)組的長度是 2^5 = 32。

例如,現(xiàn)在有一個 key 經(jīng)過哈希函數(shù)計算后,得到的哈希結(jié)果是:

 10010111 | 000011110110110010001111001010100010010110010101010 │ 01010

用最后的 5 個 bit 位,也就是 01010,值為 10,也就是 10 號桶。這個操作實際上就是取余操作,但是取余開銷太大,所以代碼實現(xiàn)上用的位操作代替。

再用哈希值的高 8 位,找到此 key 在 bucket 中的位置,這是在尋找已有的 key。最開始桶內(nèi)還沒有 key,新加入的 key 會找到第一個空位,放入。

buckets 編號就是桶編號,當(dāng)兩個不同的 key 落在同一個桶中,也就是發(fā)生了哈希沖突。沖突的解決手段是用鏈表法:在 bucket 中,從前往后找到第一個空位。這樣,在查找某個 key 時,先找到對應(yīng)的桶,再去遍歷 bucket 中的 key。

這里參考曹大 github 博客里的一張圖,原圖是 ascii 圖,geek 味十足,可以從參考資料找到曹大的博客,推薦大家去看看。

上圖中,假定 B = 5,所以 bucket 總數(shù)就是 2^5 = 32。首先計算出待查找 key 的哈希,使用低 5 位 00110,找到對應(yīng)的 6 號 bucket,使用高 8 位 10010111,對應(yīng)十進(jìn)制 151,在 6 號 bucket 中尋找 tophash 值(HOB hash)為 151 的 key,找到了 2 號槽位,這樣整個查找過程就結(jié)束了。

如果在 bucket 中沒找到,并且 overflow 不為空,還要繼續(xù)去 overflow bucket 中尋找,直到找到或是所有的 key 槽位都找遍了,包括所有的 overflow bucket。

我們來看下源碼吧,哈哈!通過匯編語言可以看到,查找某個 key 的底層函數(shù)是 mapacess 系列函數(shù),函數(shù)的作用類似,區(qū)別在下一節(jié)會講到。這里我們直接看 mapacess1 函數(shù):

func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
	// ……
	
	// 如果 h 什么都沒有,返回零值
	if h == nil || h.count == 0 {
		return unsafe.Pointer(&zeroVal[0])
	}
	
	// 寫和讀沖突
	if h.flags&hashWriting != 0 {
		throw("concurrent map read and map write")
	}
	
	// 不同類型 key 使用的 hash 算法在編譯期確定
	alg := t.key.alg
	
	// 計算哈希值,并且加入 hash0 引入隨機(jī)性
	hash := alg.hash(key, uintptr(h.hash0))
	
	// 比如 B=5,那 m 就是31,二進(jìn)制是全 1
	// 求 bucket num 時,將 hash 與 m 相與,
	// 達(dá)到 bucket num 由 hash 的低 8 位決定的效果
	m := uintptr(1)<1
	
	// b 就是 bucket 的地址
	b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))
	
	// oldbuckets 不為 nil,說明發(fā)生了擴(kuò)容
	if c := h.oldbuckets; c != nil {
	    // 如果不是同 size 擴(kuò)容(看后面擴(kuò)容的內(nèi)容)
	    // 對應(yīng)條件 1 的解決方案
		if !h.sameSizeGrow() {
			// 新 bucket 數(shù)量是老的 2 倍
			m >>= 1
		}
		
		// 求出 key 在老的 map 中的 bucket 位置
		oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize)))
		
		// 如果 oldb 沒有搬遷到新的 bucket
		// 那就在老的 bucket 中尋找
		if !evacuated(oldb) {
			b = oldb
		}
	}
	
	// 計算出高 8 位的 hash
	// 相當(dāng)于右移 56 位,只取高8位
	top := uint8(hash >> (sys.PtrSize*8 - 8))
	
	// 增加一個 minTopHash
	if top < minTopHash {
		top += minTopHash
	}
	for {
	    // 遍歷 8 個 bucket
		for i := uintptr(0); i < bucketCnt; i++ {
		    // tophash 不匹配,繼續(xù)
			if b.tophash[i] != top {
				continue
			}
			// tophash 匹配,定位到 key 的位置
			k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
			// key 是指針
			if t.indirectkey {
			    // 解引用
				k = *((*unsafe.Pointer)(k))
			}
			// 如果 key 相等
			if alg.equal(key, k) {
			    // 定位到 value 的位置
				v := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))
				// value 解引用
				if t.indirectvalue {
					v = *((*unsafe.Pointer)(v))
				}
				return v
			}
		}
		
		// bucket 找完(還沒找到),繼續(xù)到 overflow bucket 里找
		b = b.overflow(t)
		// overflow bucket 也找完了,說明沒有目標(biāo) key
		// 返回零值
		if b == nil {
			return unsafe.Pointer(&zeroVal[0])
		}
	}
}

函數(shù)返回 h[key] 的指針,如果 h 中沒有此 key,那就會返回一個 key 相應(yīng)類型的零值,不會返回 nil。

代碼整體比較直接,沒什么難懂的地方。跟著上面的注釋一步步理解就好了。

這里,說一下定位 key 和 value 的方法以及整個循環(huán)的寫法。

// key 定位公式
k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))

// value 定位公式
v := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))

b 是 bmap 的地址,這里 bmap 還是源碼里定義的結(jié)構(gòu)體,只包含一個 tophash 數(shù)組,經(jīng)編譯器擴(kuò)充之后的結(jié)構(gòu)體才包含 key,value,overflow 這些字段。dataOffset 是 key 相對于 bmap 起始地址的偏移:

dataOffset = unsafe.Offsetof(struct {
		b bmap
		v int64
	}{}.v)

因此 bucket 里 key 的起始地址就是 unsafe.Pointer(b)+dataOffset。第 i 個 key 的地址就要在此基礎(chǔ)上跨過 i 個 key 的大小;而我們又知道,value 的地址是在所有 key 之后,因此第 i 個 value 的地址還需要加上所有 key 的偏移。理解了這些,上面 key 和 value 的定位公式就很好理解了。

再說整個大循環(huán)的寫法,最外層是一個無限循環(huán),通過

b = b.overflow(t)

遍歷所有的 bucket,這相當(dāng)于是一個 bucket 鏈表。

當(dāng)定位到一個具體的 bucket 時,里層循環(huán)就是遍歷這個 bucket 里所有的 cell,或者說所有的槽位,也就是 bucketCnt=8 個槽位。整個循環(huán)過程:

再說一下 minTopHash,當(dāng)一個 cell 的 tophash 值小于 minTopHash 時,標(biāo)志這個 cell 的遷移狀態(tài)。因為這個狀態(tài)值是放在 tophash 數(shù)組里,為了和正常的哈希值區(qū)分開,會給 key 計算出來的哈希值一個增量:minTopHash。這樣就能區(qū)分正常的 top hash 值和表示狀態(tài)的哈希值。

下面的這幾種狀態(tài)就表征了 bucket 的情況:

// 空的 cell,也是初始時 bucket 的狀態(tài)
empty          = 0
// 空的 cell,表示 cell 已經(jīng)被遷移到新的 bucket
evacuatedEmpty = 1
// key,value 已經(jīng)搬遷完畢,但是 key 都在新 bucket 前半部分,
// 后面擴(kuò)容部分會再講到。
evacuatedX     = 2
// 同上,key 在后半部分
evacuatedY     = 3
// tophash 的最小正常值
minTopHash     = 4

源碼里判斷這個 bucket 是否已經(jīng)搬遷完畢,用到的函數(shù):

func evacuated(b *bmap) bool {
	h := b.tophash[0]
	return h > empty && h < minTopHash
}

只取了 tophash 數(shù)組的第一個值,判斷它是否在 0-4 之間。對比上面的常量,當(dāng) top hash 是 evacuatedEmpty、evacuatedX、evacuatedY 這三個值之一,說明此 bucket 中的 key 全部被搬遷到了新 bucket。

map 的兩種 get 操作

Go 語言中讀取 map 有兩種語法:帶 comma 和 不帶 comma。當(dāng)要查詢的 key 不在 map 里,帶 comma 的用法會返回一個 bool 型變量提示 key 是否在 map 中;而不帶 comma 的語句則會返回一個 key 類型的零值。如果 key 是 int 型就會返回 0,如果 key 是 string 類型,就會返回空字符串。

package main

import "fmt"

func main() {
	ageMap := make(map[string]int)
	ageMap["qcrao"] = 18

    // 不帶 comma 用法
	age1 := ageMap["stefno"]
	fmt.Println(age1)

    // 帶 comma 用法
	age2, ok := ageMap["stefno"]
	fmt.Println(age2, ok)
}

運行結(jié)果:

0
0 false

以前一直覺得好神奇,怎么實現(xiàn)的?這其實是編譯器在背后做的工作:分析代碼后,將兩種語法對應(yīng)到底層兩個不同的函數(shù)。

// src/runtime/hashmap.go
func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer
func mapaccess2(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, bool)

源碼里,函數(shù)命名不拘小節(jié),直接帶上后綴 1,2,完全不理會《代碼大全》里的那一套命名的做法。從上面兩個函數(shù)的聲明也可以看出差別了,mapaccess2 函數(shù)返回值多了一個 bool 型變量,兩者的代碼也是完全一樣的,只是在返回值后面多加了一個 false 或者 true。

另外,根據(jù) key 的不同類型,編譯器還會將查找、插入、刪除的函數(shù)用更具體的函數(shù)替換,以優(yōu)化效率:

key 類型 查找
uint32 mapaccess1_fast32(t *maptype, h *hmap, key uint32) unsafe.Pointer
uint32 mapaccess2_fast32(t *maptype, h *hmap, key uint32) (unsafe.Pointer, bool)
uint64 mapaccess1_fast64(t *maptype, h *hmap, key uint64) unsafe.Pointer
uint64 mapaccess2_fast64(t *maptype, h *hmap, key uint64) (unsafe.Pointer, bool)
string mapaccess1_faststr(t *maptype, h *hmap, ky string) unsafe.Pointer
string mapaccess2_faststr(t *maptype, h *hmap, ky string) (unsafe.Pointer, bool)

這些函數(shù)的參數(shù)類型直接是具體的 uint32、unt64、string,在函數(shù)內(nèi)部由于提前知曉了 key 的類型,所以內(nèi)存布局是很清楚的,因此能節(jié)省很多操作,提高效率。

上面這些函數(shù)都是在文件 src/runtime/hashmap_fast.go 里。

如何進(jìn)行擴(kuò)容

使用哈希表的目的就是要快速查找到目標(biāo) key,然而,隨著向 map 中添加的 key 越來越多,key 發(fā)生碰撞的概率也越來越大。bucket 中的 8 個 cell 會被逐漸塞滿,查找、插入、刪除 key 的效率也會越來越低。最理想的情況是一個 bucket 只裝一個 key,這樣,就能達(dá)到 O(1) 的效率,但這樣空間消耗太大,用空間換時間的代價太高。

Go 語言采用一個 bucket 里裝載 8 個 key,定位到某個 bucket 后,還需要再定位到具體的 key,這實際上又用了時間換空間。

當(dāng)然,這樣做,要有一個度,不然所有的 key 都落在了同一個 bucket 里,直接退化成了鏈表,各種操作的效率直接降為 O(n),是不行的。

因此,需要有一個指標(biāo)來衡量前面描述的情況,這就是裝載因子。Go 源碼里這樣定義 裝載因子

loadFactor := count / (2^B)

count 就是 map 的元素個數(shù),2^B 表示 bucket 數(shù)量。

再來說觸發(fā) map 擴(kuò)容的時機(jī):在向 map 插入新 key 的時候,會進(jìn)行條件檢測,符合下面這 2 個條件,就會觸發(fā)擴(kuò)容:

    裝載因子超過閾值,源碼里定義的閾值是 6.5。

    overflow 的 bucket 數(shù)量過多:當(dāng) B 小于 15,也就是 bucket 總數(shù) 2^B 小于 2^15 時,如果 overflow 的 bucket 數(shù)量超過 2^B;當(dāng) B >= 15,也就是 bucket 總數(shù) 2^B 大于等于 2^15,如果 overflow 的 bucket 數(shù)量超過 2^15。

通過匯編語言可以找到賦值操作對應(yīng)源碼中的函數(shù)是 mapassign,對應(yīng)擴(kuò)容條件的源碼如下:

// src/runtime/hashmap.go/mapassign

// 觸發(fā)擴(kuò)容時機(jī)
if !h.growing() && (overLoadFactor(int64(h.count), h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
		hashGrow(t, h)
	}

// 裝載因子超過 6.5
func overLoadFactor(count int64, B uint8) bool {
	return count >= bucketCnt && float32(count) >= loadFactor*float32((uint64(1)<// overflow buckets 太多
func tooManyOverflowBuckets(noverflow uint16, B uint8) bool {
	if B < 16 {
		return noverflow >= uint16(1)<return noverflow >= 1<<15
}

解釋一下:

第 1 點:我們知道,每個 bucket 有 8 個空位,在沒有溢出,且所有的桶都裝滿了的情況下,裝載因子算出來的結(jié)果是 8。因此當(dāng)裝載因子超過 6.5 時,表明很多 bucket 都快要裝滿了,查找效率和插入效率都變低了。在這個時候進(jìn)行擴(kuò)容是有必要的。

第 2 點:是對第 1 點的補(bǔ)充。就是說在裝載因子比較小的情況下,這時候 map 的查找和插入效率也很低,而第 1 點識別不出來這種情況。表面現(xiàn)象就是計算裝載因子的分子比較小,即 map 里元素總數(shù)少,但是 bucket 數(shù)量多(真實分配的 bucket 數(shù)量多,包括大量的 overflow bucket)。

不難想像造成這種情況的原因:不停地插入、刪除元素。先插入很多元素,導(dǎo)致創(chuàng)建了很多 bucket,但是裝載因子達(dá)不到第 1 點的臨界值,未觸發(fā)擴(kuò)容來緩解這種情況。之后,刪除元素降低元素總數(shù)量,再插入很多元素,導(dǎo)致創(chuàng)建很多的 overflow bucket,但就是不會觸犯第 1 點的規(guī)定,你能拿我怎么辦?overflow bucket 數(shù)量太多,導(dǎo)致 key 會很分散,查找插入效率低得嚇人,因此出臺第 2 點規(guī)定。這就像是一座空城,房子很多,但是住戶很少,都分散了,找起人來很困難。

對于命中條件 1,2 的限制,都會發(fā)生擴(kuò)容。但是擴(kuò)容的策略并不相同,畢竟兩種條件應(yīng)對的場景不同。

對于條件 1,元素太多,而 bucket 數(shù)量太少,很簡單:將 B 加 1,bucket 最大數(shù)量(2^B)直接變成原來 bucket 數(shù)量的 2 倍。于是,就有新老 bucket 了。注意,這時候元素都在老 bucket 里,還沒遷移到新的 bucket 來。而且,新 bucket 只是最大數(shù)量變?yōu)樵瓉碜畲髷?shù)量(2^B)的 2 倍(2^B * 2)。

對于條件 2,其實元素沒那么多,但是 overflow bucket 數(shù)特別多,說明很多 bucket 都沒裝滿。解決辦法就是開辟一個新 bucket 空間,將老 bucket 中的元素移動到新 bucket,使得同一個 bucket 中的 key 排列地更緊密。這樣,原來,在 overflow bucket 中的 key 可以移動到 bucket 中來。結(jié)果是節(jié)省空間,提高 bucket 利用率,map 的查找和插入效率自然就會提升。

對于條件 2 的解決方案,曹大的博客里還提出了一個極端的情況:如果插入 map 的 key 哈希都一樣,就會落到同一個 bucket 里,超過 8 個就會產(chǎn)生 overflow bucket,結(jié)果也會造成 overflow bucket 數(shù)過多。移動元素其實解決不了問題,因為這時整個哈希表已經(jīng)退化成了一個鏈表,操作效率變成了 O(n)

再來看一下擴(kuò)容具體是怎么做的。由于 map 擴(kuò)容需要將原有的 key/value 重新搬遷到新的內(nèi)存地址,如果有大量的 key/value 需要搬遷,會非常影響性能。因此 Go map 的擴(kuò)容采取了一種稱為“漸進(jìn)式”地方式,原有的 key 并不會一次性搬遷完畢,每次最多只會搬遷 2 個 bucket。

上面說的 hashGrow() 函數(shù)實際上并沒有真正地“搬遷”,它只是分配好了新的 buckets,并將老的 buckets 掛到了 oldbuckets 字段上。真正搬遷 buckets 的動作在 growWork() 函數(shù)中,而調(diào)用 growWork() 函數(shù)的動作是在 mapassign 和 mapdelete 函數(shù)中。也就是插入或修改、刪除 key 的時候,都會嘗試進(jìn)行搬遷 buckets 的工作。先檢查 oldbuckets 是否搬遷完畢,具體來說就是檢查 oldbuckets 是否為 nil。

我們先看 hashGrow() 函數(shù)所做的工作,再來看具體的搬遷 buckets 是如何進(jìn)行的。

func hashGrow(t *maptype, h *hmap) {
	// B+1 相當(dāng)于是原來 2 倍的空間
	bigger := uint8(1)

	// 對應(yīng)條件 2
	if !overLoadFactor(int64(h.count), h.B) {
		// 進(jìn)行等量的內(nèi)存擴(kuò)容,所以 B 不變
		bigger = 0
		h.flags |= sameSizeGrow
	}
	// 將老 buckets 掛到 buckets 上
	oldbuckets := h.buckets
	// 申請新的 buckets 空間
	newbuckets, nextOverflow := makeBucketArray(t, h.B+bigger)

	flags := h.flags &^ (iterator | oldIterator)
	if h.flags&iterator != 0 {
		flags |= oldIterator
	}
	// 提交 grow 的動作
	h.B += bigger
	h.flags = flags
	h.oldbuckets = oldbuckets
	h.buckets = newbuckets
	// 搬遷進(jìn)度為 0
	h.nevacuate = 0
	// overflow buckets 數(shù)為 0
	h.noverflow = 0

	// ……
}

主要是申請到了新的 buckets 空間,把相關(guān)的標(biāo)志位都進(jìn)行了處理:例如標(biāo)志 nevacuate 被置為 0, 表示當(dāng)前搬遷進(jìn)度為 0。

值得一說的是對 h.flags 的處理:

flags := h.flags &^ (iterator | oldIterator)
if h.flags&iterator != 0 {
	flags |= oldIterator
}

這里得先說下運算符:&^。這叫按位置 0運算符。例如:

x = 01010011
y = 01010100
z = x &^ y = 00000011

如果 y bit 位為 1,那么結(jié)果 z 對應(yīng) bit 位就為 0,否則 z 對應(yīng) bit 位就和 x 對應(yīng) bit 位的值相同。

所以上面那段對 flags 一頓操作的代碼的意思是:先把 h.flags 中 iterator 和 oldIterator 對應(yīng)位清 0,然后如果發(fā)現(xiàn) iterator 位為 1,那就把它轉(zhuǎn)接到 oldIterator 位,使得 oldIterator 標(biāo)志位變成 1。潛臺詞就是:buckets 現(xiàn)在掛到了 oldBuckets 名下了,對應(yīng)的標(biāo)志位也轉(zhuǎn)接過去吧。

幾個標(biāo)志位如下:

// 可能有迭代器使用 buckets
iterator     = 1
// 可能有迭代器使用 oldbuckets
oldIterator  = 2
// 有協(xié)程正在向 map 中寫入 key
hashWriting  = 4
// 等量擴(kuò)容(對應(yīng)條件 2)
sameSizeGrow = 8

再來看看真正執(zhí)行搬遷工作的 growWork() 函數(shù)。

func growWork(t *maptype, h *hmap, bucket uintptr) {
	// 確認(rèn)搬遷老的 bucket 對應(yīng)正在使用的 bucket
	evacuate(t, h, bucket&h.oldbucketmask())

	// 再搬遷一個 bucket,以加快搬遷進(jìn)程
	if h.growing() {
		evacuate(t, h, h.nevacuate)
	}
}

h.growing() 函數(shù)非常簡單:

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

如果 oldbuckets 不為空,說明還沒有搬遷完畢,還得繼續(xù)搬。

bucket&h.oldbucketmask() 這行代碼,如源碼注釋里說的,是為了確認(rèn)搬遷的 bucket 是我們正在使用的 bucket。oldbucketmask() 函數(shù)返回擴(kuò)容前的 map 的 bucketmask。

所謂的 bucketmask,作用就是將 key 計算出來的哈希值與 bucketmask 相與,得到的結(jié)果就是 key 應(yīng)該落入的桶。比如 B = 5,那么 bucketmask 的低 5 位是 11111,其余位是 0,hash 值與其相與的意思是,只有 hash 值的低 5 位決策 key 到底落入哪個 bucket。

接下來,我們集中所有的精力在搬遷的關(guān)鍵函數(shù) evacuate。源碼貼在下面,不要緊張,我會加上大面積的注釋,通過注釋絕對是能看懂的。之后,我會再對搬遷過程作詳細(xì)說明。

源碼如下:

func evacuate(t *maptype, h *hmap, oldbucket uintptr) {
	// 定位老的 bucket 地址
	b := (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.bucketsize)))
	// 結(jié)果是 2^B,如 B = 5,結(jié)果為32
	newbit := h.noldbuckets()
	// key 的哈希函數(shù)
	alg := t.key.alg
	// 如果 b 沒有被搬遷過
	if !evacuated(b) {
		var (
			// 表示bucket 移動的目標(biāo)地址
			x, y   *bmap
			// 指向 x,y 中的 key/val
			xi, yi int
			// 指向 x,y 中的 key
			xk, yk unsafe.Pointer
			// 指向 x,y 中的 value
			xv, yv unsafe.Pointer
		)
		// 默認(rèn)是等 size 擴(kuò)容,前后 bucket 序號不變
		// 使用 x 來進(jìn)行搬遷
		x = (*bmap)(add(h.buckets, oldbucket*uintptr(t.bucketsize)))
		xi = 0
		xk = add(unsafe.Pointer(x), dataOffset)
		xv = add(xk, bucketCnt*uintptr(t.keysize))、

		// 如果不是等 size 擴(kuò)容,前后 bucket 序號有變
		// 使用 y 來進(jìn)行搬遷
		if !h.sameSizeGrow() {
			// y 代表的 bucket 序號增加了 2^B
			y = (*bmap)(add(h.buckets, (oldbucket+newbit)*uintptr(t.bucketsize)))
			yi = 0
			yk = add(unsafe.Pointer(y), dataOffset)
			yv = add(yk, bucketCnt*uintptr(t.keysize))
		}

		// 遍歷所有的 bucket,包括 overflow buckets
		// b 是老的 bucket 地址
		for ; b != nil; b = b.overflow(t) {
			k := add(unsafe.Pointer(b), dataOffset)
			v := add(k, bucketCnt*uintptr(t.keysize))

			// 遍歷 bucket 中的所有 cell
			for i := 0; i < bucketCnt; i, k, v = i+1, add(k, uintptr(t.keysize)), add(v, uintptr(t.valuesize)) {
				// 當(dāng)前 cell 的 top hash 值
				top := b.tophash[i]
				// 如果 cell 為空,即沒有 key
				if top == empty {
					// 那就標(biāo)志它被"搬遷"過
					b.tophash[i] = evacuatedEmpty
					// 繼續(xù)下個 cell
					continue
				}
				// 正常不會出現(xiàn)這種情況
				// 未被搬遷的 cell 只可能是 empty 或是
				// 正常的 top hash(大于 minTopHash)
				if top < minTopHash {
					throw("bad map state")
				}

				k2 := k
				// 如果 key 是指針,則解引用
				if t.indirectkey {
					k2 = *((*unsafe.Pointer)(k2))
				}

				// 默認(rèn)使用 X,等量擴(kuò)容
				useX := true
				// 如果不是等量擴(kuò)容
				if !h.sameSizeGrow() {
					// 計算 hash 值,和 key 第一次寫入時一樣
					hash := alg.hash(k2, uintptr(h.hash0))

					// 如果有協(xié)程正在遍歷 map
					if h.flags&iterator != 0 {
						// 如果出現(xiàn) 相同的 key 值,算出來的 hash 值不同
						if !t.reflexivekey && !alg.equal(k2, k2) {
							// 只有在 float 變量的 NaN() 情況下會出現(xiàn)
							if top&1 != 0 {
								// 第 B 位置 1
								hash |= newbit
							} else {
								// 第 B 位置 0
								hash &^= newbit
							}
							// 取高 8 位作為 top hash 值
							top = uint8(hash >> (sys.PtrSize*8 - 8))
							if top < minTopHash {
								top += minTopHash
							}
						}
					}

					// 取決于新哈希值的 oldB+1 位是 0 還是 1
					// 詳細(xì)看后面的文章
					useX = hash&newbit == 0
				}

				// 如果 key 搬到 X 部分
				if useX {
					// 標(biāo)志老的 cell 的 top hash 值,表示搬移到 X 部分
					b.tophash[i] = evacuatedX
					// 如果 xi 等于 8,說明要溢出了
					if xi == bucketCnt {
						// 新建一個 bucket
						newx := h.newoverflow(t, x)
						x = newx
						// xi 從 0 開始計數(shù)
						xi = 0
						// xk 表示 key 要移動到的位置
						xk = add(unsafe.Pointer(x), dataOffset)
						// xv 表示 value 要移動到的位置
						xv = add(xk, bucketCnt*uintptr(t.keysize))
					}
					// 設(shè)置 top hash 值
					x.tophash[xi] = top
					// key 是指針
					if t.indirectkey {
						// 將原 key(是指針)復(fù)制到新位置
						*(*unsafe.Pointer)(xk) = k2 // copy pointer
					} else {
						// 將原 key(是值)復(fù)制到新位置
						typedmemmove(t.key, xk, k) // copy value
					}
					// value 是指針,操作同 key
					if t.indirectvalue {
						*(*unsafe.Pointer)(xv) = *(*unsafe.Pointer)(v)
					} else {
						typedmemmove(t.elem, xv, v)
					}

					// 定位到下一個 cell
					xi++
					xk = add(xk, uintptr(t.keysize))
					xv = add(xv, uintptr(t.valuesize))
				} else { // key 搬到 Y 部分,操作同 X 部分
					// ……
					// 省略了這部分,操作和 X 部分相同
				}
			}
		}
		// 如果沒有協(xié)程在使用老的 buckets,就把老 buckets 清除掉,幫助gc
		if h.flags&oldIterator == 0 {
			b = (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.bucketsize)))
			// 只清除bucket 的 key,value 部分,保留 top hash 部分,指示搬遷狀態(tài)
			if t.bucket.kind&kindNoPointers == 0 {
				memclrHasPointers(add(unsafe.Pointer(b), dataOffset), uintptr(t.bucketsize)-dataOffset)
			} else {
				memclrNoHeapPointers(add(unsafe.Pointer(b), dataOffset), uintptr(t.bucketsize)-dataOffset)
			}
		}
	}

	// 更新搬遷進(jìn)度
	// 如果此次搬遷的 bucket 等于當(dāng)前進(jìn)度
	if oldbucket == h.nevacuate {
		// 進(jìn)度加 1
		h.nevacuate = oldbucket + 1
		// Experiments suggest that 1024 is overkill by at least an order of magnitude.
		// Put it in there as a safeguard anyway, to ensure O(1) behavior.
		// 嘗試往后看 1024 個 bucket
		stop := h.nevacuate + 1024
		if stop > newbit {
			stop = newbit
		}
		// 尋找沒有搬遷的 bucket
		for h.nevacuate != stop && bucketEvacuated(t, h, h.nevacuate) {
			h.nevacuate++
		}
		
		// 現(xiàn)在 h.nevacuate 之前的 bucket 都被搬遷完畢
		
		// 所有的 buckets 搬遷完畢
		if h.nevacuate == newbit {
			// 清除老的 buckets
			h.oldbuckets = nil
			// 清除老的 overflow bucket
			// 回憶一下:[0] 表示當(dāng)前 overflow bucket
			// [1] 表示 old overflow bucket
			if h.extra != nil {
				h.extra.overflow[1] = nil
			}
			// 清除正在擴(kuò)容的標(biāo)志位
			h.flags &^= sameSizeGrow
		}
	}
}

evacuate 函數(shù)的代碼注釋非常清晰,對著代碼和注釋是很容易看懂整個的搬遷過程的,耐心點。

搬遷的目的就是將老的 buckets 搬遷到新的 buckets。而通過前面的說明我們知道,應(yīng)對條件 1,新的 buckets 數(shù)量是之前的一倍,應(yīng)對條件 2,新的 buckets 數(shù)量和之前相等。

對于條件 1,從老的 buckets 搬遷到新的 buckets,由于 bucktes 數(shù)量不變,因此可以按序號來搬,比如原來在 0 號 bucktes,到新的地方后,仍然放在 0 號 buckets。

對于條件 2,就沒這么簡單了。要重新計算 key 的哈希,才能決定它到底落在哪個 bucket。例如,原來 B = 5,計算出 key 的哈希后,只用看它的低 5 位,就能決定它落在哪個 bucket。擴(kuò)容后,B 變成了 6,因此需要多看一位,它的低 6 位決定 key 落在哪個 bucket。這稱為 rehash。

因此,某個 key 在搬遷前后 bucket 序號可能和原來相等,也可能是相比原來加上 2^B(原來的 B 值),取決于 hash 值 第 6 bit 位是 0 還是 1。

理解了上面 bucket 序號的變化,我們就可以回答另一個問題了:為什么遍歷 map 是無序的?

map 在擴(kuò)容后,會發(fā)生 key 的搬遷,原來落在同一個 bucket 中的 key,搬遷后,有些 key 就要遠(yuǎn)走高飛了(bucket 序號加上了 2^B)。而遍歷的過程,就是按順序遍歷 bucket,同時按順序遍歷 bucket 中的 key。搬遷后,key 的位置發(fā)生了重大的變化,有些 key 飛上高枝,有些 key 則原地不動。這樣,遍歷 map 的結(jié)果就不可能按原來的順序了。

當(dāng)然,如果我就一個 hard code 的 map,我也不會向 map 進(jìn)行插入刪除的操作,按理說每次遍歷這樣的 map 都會返回一個固定順序的 key/value 序列吧。的確是這樣,但是 Go 杜絕了這種做法,因為這樣會給新手程序員帶來誤解,以為這是一定會發(fā)生的事情,在某些情況下,可能會釀成大錯。

當(dāng)然,Go 做得更絕,當(dāng)我們在遍歷 map 時,并不是固定地從 0 號 bucket 開始遍歷,每次都是從一個隨機(jī)值序號的 bucket 開始遍歷,并且是從這個 bucket 的一個隨機(jī)序號的 cell 開始遍歷。這樣,即使你是一個寫死的 map,僅僅只是遍歷它,也不太可能會返回一個固定序列的 key/value 對了。

多說一句,“迭代 map 的結(jié)果是無序的”這個特性是從 go 1.0 開始加入的。

再明確一個問題:如果擴(kuò)容后,B 增加了 1,意味著 buckets 總數(shù)是原來的 2 倍,原來 1 號的桶“裂變”到兩個桶。

例如,原始 B = 2,1號 bucket 中有 2 個 key 的哈希值低 3 位分別為:010,110。由于原來 B = 2,所以低 2 位 10 決定它們落在 2 號桶,現(xiàn)在 B 變成 3,所以 010、110 分別落入 2、6 號桶。

理解了這個,后面講 map 迭代的時候會用到。

再來講搬遷函數(shù)中的幾個關(guān)鍵點:

evacuate 函數(shù)每次只完成一個 bucket 的搬遷工作,因此要遍歷完此 bucket 的所有的 cell,將有值的 cell copy 到新的地方。bucket 還會鏈接 overflow bucket,它們同樣需要搬遷。因此會有 2 層循環(huán),外層遍歷 bucket 和 overflow bucket,內(nèi)層遍歷 bucket 的所有 cell。這樣的循環(huán)在 map 的源碼里到處都是,要理解透了。

源碼里提到 X, Y part,其實就是我們說的如果是擴(kuò)容到原來的 2 倍,桶的數(shù)量是原來的 2 倍,前一半桶被稱為 X part,后一半桶被稱為 Y part。一個 bucket 中的 key 可能會分裂落到 2 個桶,一個位于 X part,一個位于 Y part。所以在搬遷一個 cell 之前,需要知道這個 cell 中的 key 是落到哪個 Part。很簡單,重新計算 cell 中 key 的 hash,并向前“多看”一位,決定落入哪個 Part,這個前面也說得很詳細(xì)了。

有一個特殊情況是:有一種 key,每次對它計算 hash,得到的結(jié)果都不一樣。這個 key 就是 math.NaN() 的結(jié)果,它的含義是 not a number,類型是 float64。當(dāng)它作為 map 的 key,在搬遷的時候,會遇到一個問題:再次計算它的哈希值和它當(dāng)初插入 map 時的計算出來的哈希值不一樣!

你可能想到了,這樣帶來的一個后果是,這個 key 是永遠(yuǎn)不會被 Get 操作獲取的!當(dāng)我使用 m[math.NaN()] 語句的時候,是查不出來結(jié)果的。這個 key 只有在遍歷整個 map 的時候,才有機(jī)會現(xiàn)身。所以,可以向一個 map 插入任意數(shù)量的 math.NaN() 作為 key。

當(dāng)搬遷碰到 math.NaN() 的 key 時,只通過 tophash 的最低位決定分配到 X part 還是 Y part(如果擴(kuò)容后是原來 buckets 數(shù)量的 2 倍)。如果 tophash 的最低位是 0 ,分配到 X part;如果是 1 ,則分配到 Y part。

這是通過 tophash 值與新算出來的哈希值進(jìn)行運算得到的:

if top&1 != 0 {
    // top hash 最低位為 1
    // 新算出來的 hash 值的 B 位置 1
	hash |= newbit
} else {
    // 新算出來的 hash 值的 B 位置 0
	hash &^= newbit
}

// hash 值的 B 位為 0,則搬遷到 x part
// 當(dāng) B = 5時,newbit = 32,二進(jìn)制低 6 位為 10 0000
useX = hash&newbit == 0

其實這樣的 key 我隨便搬遷到哪個 bucket 都行,當(dāng)然,還是要搬遷到上面裂變那張圖中的兩個 bucket 中去。但這樣做是有好處的,在后面講 map 迭代的時候會再詳細(xì)解釋,暫時知道是這樣分配的就行。

確定了要搬遷到的目標(biāo) bucket 后,搬遷操作就比較好進(jìn)行了。將源 key/value 值 copy 到目的地相應(yīng)的位置。

設(shè)置 key 在原始 buckets 的 tophash 為 evacuatedX 或是 evacuatedY,表示已經(jīng)搬遷到了新 map 的 x part 或是 y part。新 map 的 tophash 則正常取 key 哈希值的高 8 位。

下面通過圖來宏觀地看一下擴(kuò)容前后的變化。

擴(kuò)容前,B = 2,共有 4 個 buckets,lowbits 表示 hash 值的低位。假設(shè)我們不關(guān)注其他 buckets 情況,專注在 2 號 bucket。并且假設(shè) overflow 太多,觸發(fā)了等量擴(kuò)容(對應(yīng)于前面的條件 2)。

擴(kuò)容完成后,overflow bucket 消失了,key 都集中到了一個 bucket,更為緊湊了,提高了查找的效率。

假設(shè)觸發(fā)了 2 倍的擴(kuò)容,那么擴(kuò)容完成后,老 buckets 中的 key 分裂到了 2 個 新的 bucket。一個在 x part,一個在 y 的 part。依據(jù)是 hash 的 lowbits。新 map 中 0-3 稱為 x part,4-7 稱為 y part。

注意,上面的兩張圖忽略了其他 buckets 的搬遷情況,表示所有的 bucket 都搬遷完畢后的情形。實際上,我們知道,搬遷是一個“漸進(jìn)”的過程,并不會一下子就全部搬遷完畢。所以在搬遷過程中,oldbuckets 指針還會指向原來老的 []bmap,并且已經(jīng)搬遷完畢的 key 的 tophash 值會是一個狀態(tài)值,表示 key 的搬遷去向。

map 的遍歷

本來 map 的遍歷過程比較簡單:遍歷所有的 bucket 以及它后面掛的 overflow bucket,然后挨個遍歷 bucket 中的所有 cell。每個 bucket 中包含 8 個 cell,從有 key 的 cell 中取出 key 和 value,這個過程就完成了。

但是,現(xiàn)實并沒有這么簡單。還記得前面講過的擴(kuò)容過程嗎?擴(kuò)容過程不是一個原子的操作,它每次最多只搬運 2 個 bucket,所以如果觸發(fā)了擴(kuò)容操作,那么在很長時間里,map 的狀態(tài)都是處于一個中間態(tài):有些 bucket 已經(jīng)搬遷到新家,而有些 bucket 還待在老地方。

因此,遍歷如果發(fā)生在擴(kuò)容的過程中,就會涉及到遍歷新老 bucket 的過程,這是難點所在。

我先寫一個簡單的代碼樣例,假裝不知道遍歷過程具體調(diào)用的是什么函數(shù):

package main

import "fmt"

func main
                 
               
              

文章版權(quán)歸作者所有,未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址:http://specialneedsforspecialkids.com/yun/7175.html

相關(guān)文章

  • 深度解密Go語言 map

    摘要:當(dāng)然,哈希查找表的平均查找效率是,如果哈希函數(shù)設(shè)計的很好,最壞的情況基本不會出現(xiàn)。選擇函數(shù)主要考察的是兩點性能碰撞概率。再用哈希值的高位,找到此在中的位置,這是在尋找已有的。這篇文章主要講 map 的賦值、刪除、查詢、擴(kuò)容的具體執(zhí)行過程,仍然是從底層的角度展開。結(jié)合源碼,看完本文一定會徹底明白 map 底層原理。 我要說明的是,這里對 map 的基本用法涉及比較少,我相信可以通過閱讀其他入門...

    siberiawolf 評論0 收藏0
  • Golang 實現(xiàn)RSA 加密解密(附帶php)

    摘要:安全總是很重要的,各個語言對于通用的加密算法都會有實現(xiàn)。對于和加密算法本身,請查閱相關(guān)資料在中,很多功能經(jīng)常是一個函數(shù)解決而中的卻不是。該文討論加密解密。一概要這是一個非對稱加密算法,一般通過公鑰加密,私鑰解密。 安全總是很重要的,各個語言對于通用的加密算法都會有實現(xiàn)。前段時間,用Go實現(xiàn)了RSA和DES的加密解密,在這分享一下。(對于RSA和DES加密算法本身,請查閱相關(guān)資料) 在P...

    kun_jian 評論0 收藏0
  • 剝開比原看代碼04:如何連上一個比原節(jié)點

    摘要:總的來說,在比原中有一個類,它用于集中處理節(jié)點與外界交互的邏輯,而它的創(chuàng)建和啟動,又都是在中進(jìn)行的。我考慮的是這樣一種情況,比如某用戶在筆記本上運行比原節(jié)點,然后在公開場合上網(wǎng),使用了黑客提供的。 作者:freewind 比原項目倉庫: Github地址:https://github.com/Bytom/bytom Gitee地址:https://gitee.com/BytomBloc...

    BigNerdCoding 評論0 收藏0
  • 【好東西傳送門日報】2017-12-08 星期五

    摘要:好東西傳送門日報星期五機(jī)器學(xué)習(xí)語義分割中的弱監(jiān)督學(xué)習(xí)亮點摘要解密谷歌機(jī)器學(xué)習(xí)工程最佳實踐深度解析京東個性化推薦系統(tǒng)演進(jìn)史最著名的個機(jī)器學(xué)習(xí)項目新技術(shù)與新應(yīng)用高通驍龍解析這次圍繞著人工智能和沉浸式體驗高通量人工智能一體機(jī)首次亮相北京時空大 【好東西傳送門日報】2017-12-08 星期五 【機(jī)器學(xué)習(xí)】 1) 語義分割中的弱監(jiān)督學(xué)習(xí) http://t.cn/RYBWyIZ 2) +NIPS...

    taowen 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<