現在面試都這麼直接的嘛?(golang map)

語言: CN / TW / HK

現在面試都這麼直接的嘛?

面試難如狗,肝不過年輕人怎麼辦,只能多總結。

閒聊

MAP結構

Map的實現主要有兩種方式:雜湊表(hash table)和搜尋樹(search tree)。例如Java中的hashMap是基於雜湊表實現,而C++中的Map是基於一種平衡搜尋二叉樹——紅黑樹而實現的。以下是不同實現方式的時間複雜度對比。

可以看到,對於元素查詢而言,二叉搜尋樹的平均和最壞效率都是O(log n),雜湊表實現的平均效率是O(1),但最壞情況下能達到O(n),不過如果雜湊表設計優秀,最壞情況基本不會出現(所以,讀者不想知道Go是如何設計的Map嗎)。另外二叉搜尋樹返回的key是有序的,而雜湊表則是亂序。

雜湊表

由於Go中map的基於雜湊表(也被稱為散列表)實現,本文不探討搜尋樹的map實現。以下是Go官方部落格對map的說明。

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.

學習雜湊表首先要理解兩個概念:雜湊函式和雜湊衝突。

雜湊函式

雜湊函式(常被稱為雜湊函式)是可以用於將任意大小的資料對映到固定大小值的函式,常見的包括MD5、SHA系列等。

一個設計優秀的雜湊函式應該包含以下特性:

  • 均勻性:一個好的雜湊函式應該在其輸出範圍內儘可能均勻地對映,也就是說,應以大致相同的概率生成輸出範圍內的每個雜湊值。
  • 效率高:雜湊效率要高,即使很長的輸入引數也能快速計算出雜湊值。
  • 可確定性:雜湊過程必須是確定性的,這意味著對於給定的輸入值,它必須始終生成相同的雜湊值。
  • 雪崩效應:微小的輸入值變化也會讓輸出值發生巨大的變化。
  • 不可逆:從雜湊函式的輸出值不可反向推匯出原始的資料。

雜湊衝突

重複一遍,雜湊函式是將任意大小的資料對映到固定大小值的函式。那麼,我們可以預見到,即使雜湊函式設計得足夠優秀,幾乎每個輸入值都能對映為不同的雜湊值。但是,當輸入資料足夠大,大到能超過固定大小值的組合能表達的最大數量數,衝突將不可避免!(參見抽屜原理)

抽屜原理:桌上有十個蘋果,要把這十個蘋果放到九個抽屜裡,無論怎樣放,我們會發現至少會有一個抽屜裡面放不少於兩個蘋果。抽屜原理有時也被稱為鴿巢原理。

map

原始碼解析

嚄 你也是今天的主角了

資料結構?

好像和java很像,陣列連結串列。多說無益,沒什麼比原始碼更清楚。

// A header for a Go map.
type hmap struct {
    count     int // 代表雜湊表中的元素個數,呼叫len(map)時,返回的就是該欄位值。
    flags     uint8 // 狀態標誌,下文常量中會解釋四種狀態位含義。
    B         uint8  // buckets(桶)的對數log_2(雜湊表元素數量最大可達到裝載因子*2^B)
    noverflow uint16 // 溢位桶的大概數量。
    hash0     uint32 // 雜湊種子。

    buckets    unsafe.Pointer // 指向buckets陣列的指標,陣列大小為2^B,如果元素個數為0,它為nil。
    oldbuckets unsafe.Pointer // 如果發生擴容,oldbuckets是指向老的buckets陣列的指標,老的buckets陣列大小是新的buckets的1/2。非擴容狀態下,它為nil。
    nevacuate  uintptr        // 表示擴容進度,小於此地址的buckets代表已搬遷完成。

    extra *mapextra // 這個欄位是為了優化GC掃描而設計的。當key和value均不包含指標,並且都可以inline時使用。extra是指向mapextra型別的指標。
}

然後還有個bmap結構這,每個bucket裡面儲存了kv對。buckets是一個指標,指向實際儲存的bucket陣列的首地址。 bucket的結構體如下:

type bmap struct {
	tophash [bucketCnt]uint8  //一個8個長度的uint8組成 
}

其實上面這個資料結構並不是 golang runtime 時的結構,在編譯時候編譯器會給它動態建立一個新的結構,如下:

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

bmap 就是我們常說的“bucket”結構,每個 bucket 裡面最多儲存 8 個 key,這些 key 之所以會落入同一個桶,是因為它們經過雜湊計算後,雜湊結果是“一類”的。在桶內,又會根據 key 計算出來的 hash 值的高 8 位來決定 key 到底落入桶內的哪個位置(一個桶內最多有8個位置,ps:一類的計算)。

對應一個圖的話

使用

golang使用,直接用make的。

make(map[K]V)
make(map[K]V, len) //我靠,今天踩知道map可以分配初始大小,是我失策了

make函式實際上會被編譯器定位到呼叫 runtime.makemap(),主要做的工作就是初始化 hmap 結構體的各種欄位,例如計算 B 的大小,設定雜湊種子 hash0 等等。

// 如果編譯器認為map和第一個bucket可以直接建立在棧上,h和bucket可能都是非空
// 如果h != nil,那麼map可以直接在h中建立
// 如果h.buckets != nil,那麼h指向的bucket可以作為map的第一個bucket使用
func makemap(t *maptype, hint int, h *hmap) *hmap {
  // math.MulUintptr返回hint與t.bucket.size的乘積,並判斷該乘積是否溢位。
    mem, overflow := math.MulUintptr(uintptr(hint), t.bucket.size)
// maxAlloc的值,根據平臺系統的差異而不同,具體計算方式參照src/runtime/malloc.go
    if overflow || mem > maxAlloc {
        hint = 0
    }

// initialize Hmap
    if h == nil {
        h = new(hmap)
    }
  // 通過fastrand得到雜湊種子
    h.hash0 = fastrand()

    // 根據輸入的元素個數hint,找到能裝下這些元素的B值
    B := uint8(0)
    for overLoadFactor(hint, B) {
        B++
    }
    h.B = B

    // 分配初始雜湊表
  // 如果B為0,那麼buckets欄位後續會在mapassign方法中lazily分配
    if h.B != 0 {
        var nextOverflow *bmap
    // makeBucketArray建立一個map的底層儲存buckets的陣列,它最少會分配h.B^2的大小。
        h.buckets, nextOverflow = makeBucketArray(t, h.B, nil)
        if nextOverflow != nil {
    h.extra = new(mapextra)
            h.extra.nextOverflow = nextOverflow
        }
    }

    return h
}

根據上述程式碼,我們能確定在正常情況下,正常桶和溢位桶在記憶體中的儲存空間是連續的,只是被 hmap 中的不同欄位引用而已。

注意,這個函式返回的結果:*hmap 是一個指標,而我們之前講過的 makeslice 函式返回的是 Slice 結構體物件。這也是 makemap 和 makeslice 返回值的區別所帶來一個不同點:當 map 和 slice 作為函式引數時,在函式引數內部對 map 的操作會影響 map 自身;而對 slice 卻不會(之前講 slice 的文章裡有講過)。

主要原因:一個是指標(*hmap),一個是結構體(slice)。Go 語言中的函式傳參都是值傳遞,在函式內部,引數會被 copy 到本地。*hmap指標 copy 完之後,仍然指向同一個 map,因此函式內部對 map 的操作會影響實參。而 slice 被 copy 後,會成為一個新的 slice,對它進行的操作不會影響到實參。

hash函式

雜湊函式的演算法與key的型別一一對應的。根據 key 的型別, maptype結構體的 key欄位的alg 欄位會被設定對應型別的 hash 和 equal 函式。

在初始化go程式執行環境時(src/runtime/proc.go中的schedinit),就需要通過alginit方法完成對雜湊的初始化。

hash key桶的分配

對於 hashmap 來說,最重要的就是根據key定位實際儲存位置。key 經過雜湊計算後得到雜湊值,雜湊值是 64 個 bit 位(針對64位機)。根據hash值的最後B個bit位來確定這個key落在哪個桶。如果 B = 5,那麼桶的數量,也就是 buckets 陣列的長度是 2^5 = 32。

suppose,現在有一個 key 經過雜湊函式計算後,得到的雜湊結果是:

10010111 | 000011110110110010001111001010100010010110010101010 │ 00110

定位key,如果在 bucket 中沒找到,並且 overflow 不為空,還要繼續去 overflow bucket 中尋找,直到找到或是所有的 key 槽位都找遍了,包括所有的 overflow bucket。(這裡需要遍歷bucket陣列中某個槽位的bucket連結串列的所有bucket)

擴容

使用 key 的 hash 值可以快速定位到目標 key,然而,隨著向 map 中新增的 key 越來越多,key 發生碰撞的概率也越來越大。bucket 中的 8 個 cell 會被逐漸塞滿,查詢、插入、刪除 key 的效率也會越來越低。最理想的情況是一個 bucket 只裝一個 key,這樣,就能達到 O(1) 的效率,但這樣空間消耗太大,用空間換時間的代價太高。

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

當然,這樣做,要有一個度,不然所有的 key 都落在了同一個 bucket 裡,直接退化成了連結串列,各種操作的效率直接降為 O(n),是不行的。

因此,需要有一個指標來衡量前面描述的情況,這就是裝載因子。Go 原始碼裡這樣定義 裝載因子:

loadFactor := count / (2^B)

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

再來說觸發 map 擴容的時機:在向 map 插入新 key 的時候,會進行條件檢測,符合下面這 2 個條件,就會觸發擴容:

  1. 載入因子超過閾值,原始碼裡定義的閾值是 6.5。

  2. overflow 的 bucket 數量過多,這有兩種情況:

    • 當 B 大於15時,也就是 bucket 總數大於 2^15 時,如果overflow的bucket數量大於2^15,就觸發擴容。
    • 當B小於15時,如果overflow的bucket數量大於2^B 也會觸發擴容。

如何降低map擴容的影響

因為map擴容是很消耗效能的,(桶的新建、複製),因此我們要儘量減少擴容,初始化的時候對資料進行預期分配。

sync.Map如何降低鎖的粒度

從map設計可以知道,它並不是一個併發安全的資料結構。同時對map進行讀寫時,程式很容易出錯。因此,要想在併發情況下使用map,請加上鎖(sync.Mutex或者sync.RwMutex)。其實,Go標準庫中已經為我們實現了併發安全的map——sync.Map。

sync.Map介紹

go 1.9 官方提供了sync.Map 來優化執行緒安全的併發讀寫的map。該實現也是基於內建map關鍵字來實現的。

這個實現類似於一個執行緒安全的 map[interface{}]interface{} . 這個map的優化主要適用了以下場景:

(1)給定key的鍵值對只寫了一次,但是讀了很多次,比如在只增長的快取中; (2)當多個goroutine讀取、寫入和覆蓋的key值不相交時。

在這兩種情況下,使用Map可能比使用單獨互斥鎖或RWMutex的Go Map大大減少鎖爭用。

對於其餘情況最好還是使用RWMutex保證執行緒安全。

// 封裝的執行緒安全的map
type Map struct {
	// lock
	mu Mutex

	// 實際是readOnly這個結構
	// 一個只讀的資料結構,因為只讀,所以不會有讀寫衝突。
	// readOnly包含了map的一部分資料,用於併發安全的訪問。(冗餘,記憶體換效能)
	// 訪問這一部分不需要鎖。
	read atomic.Value // readOnly

	// dirty資料包含當前的map包含的entries,它包含最新的entries(包括read中未刪除的資料,雖有冗餘,但是提升dirty欄位為read的時候非常快,不用一個一個的複製,而是直接將這個資料結構作為read欄位的一部分),有些資料還可能沒有移動到read欄位中。
	// 對於dirty的操作需要加鎖,因為對它的操作可能會有讀寫競爭。
	// 當dirty為空的時候, 比如初始化或者剛提升完,下一次的寫操作會複製read欄位中未刪除的資料到這個資料中。
	dirty map[interface{}]*entry

	// 當從Map中讀取entry的時候,如果read中不包含這個entry,會嘗試從dirty中讀取,這個時候會將misses加一,
	// 當misses累積到 dirty的長度的時候, 就會將dirty提升為read,避免從dirty中miss太多次。因為操作dirty需要加鎖。
	misses int
}
// readOnly is an immutable struct stored atomically in the Map.read field.
type readOnly struct {
	m       map[interface{}]*entry
	// 如果Map.dirty有些資料不在m中,這個值為true
	amended bool
}

// An entry is a slot in the map corresponding to a particular key.
type entry struct {
	// *interface{}
	p unsafe.Pointer 
}

從原始碼可以看出,此鎖保持了兩個map,雖然會額外佔據空間,但是並不大多少(典型空間換時間)。

讀資料流程

寫資料流程

刪資料流程

總結優化點
  1. 無鎖讀與讀寫分離;
  2. 寫加鎖與延遲提升;
  3. 指標與惰性刪除,map儲存的value都是指標。惰性刪除,實際刪除是在 Store時候去check 然後刪除。
實現方式 原理 適用場景
map+Mutex 通過Mutex互斥鎖來實現多個goroutine對map的序列化訪問 讀寫都需要通過Mutex加鎖和釋放鎖 適用於讀寫比接近的場景
map+RWMutex 通過RWMutex來實現對map的讀寫進行讀寫鎖分離加鎖,從而實現讀的併發效能提高 同Mutex相比適用於讀多寫少的場景
sync.Map 底層通分離讀寫map和原子指令來實現讀的近似無鎖,並通過延遲更新的方式來保證讀的無鎖化 讀多修改少,元素增加刪除頻率不高的情況,在大多數情況下替代上述兩種實現
分享到: