MAP結(jié)構(gòu)是什么

本篇內(nèi)容介紹了“MAP結(jié)構(gòu)是什么”的有關(guān)知識(shí)，在實(shí)際案例的操作過(guò)程中，不少人都會(huì)遇到這樣的困境，接下來(lái)就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧！希望大家仔細(xì)閱讀，能夠?qū)W有所成！

MAP結(jié)構(gòu)

Map的實(shí)現(xiàn)主要有兩種方式：哈希表（hash table）和搜索樹(shù)（search tree）。例如Java中的hashMap是基于哈希表實(shí)現(xiàn)，而C++中的Map是基于一種平衡搜索二叉樹(shù)——紅黑樹(shù)而實(shí)現(xiàn)的。以下是不同實(shí)現(xiàn)方式的時(shí)間復(fù)雜度對(duì)比。

可以看到，對(duì)于元素查找而言，二叉搜索樹(shù)的平均和最壞效率都是O(log n)，哈希表實(shí)現(xiàn)的平均效率是O(1)，但最壞情況下能達(dá)到O(n)，不過(guò)如果哈希表設(shè)計(jì)優(yōu)秀，最壞情況基本不會(huì)出現(xiàn)（所以，讀者不想知道Go是如何設(shè)計(jì)的Map嗎）。另外二叉搜索樹(shù)返回的key是有序的，而哈希表則是亂序。

哈希表

由于Go中map的基于哈希表（也被稱(chēng)為散列表）實(shí)現(xiàn)，本文不探討搜索樹(shù)的map實(shí)現(xiàn)。以下是Go官方博客對(duì)map的說(shuō)明。

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.

學(xué)習(xí)哈希表首先要理解兩個(gè)概念：哈希函數(shù)和哈希沖突。

哈希函數(shù)

哈希函數(shù)（常被稱(chēng)為散列函數(shù)）是可以用于將任意大小的數(shù)據(jù)映射到固定大小值的函數(shù)，常見(jiàn)的包括MD5、SHA系列等。

一個(gè)設(shè)計(jì)優(yōu)秀的哈希函數(shù)應(yīng)該包含以下特性：

• 均勻性：一個(gè)好的哈希函數(shù)應(yīng)該在其輸出范圍內(nèi)盡可能均勻地映射，也就是說(shuō)，應(yīng)以大致相同的概率生成輸出范圍內(nèi)的每個(gè)哈希值。

• 效率高：哈希效率要高，即使很長(zhǎng)的輸入?yún)?shù)也能快速計(jì)算出哈希值。

• 可確定性：哈希過(guò)程必須是確定性的，這意味著對(duì)于給定的輸入值，它必須始終生成相同的哈希值。

• 雪崩效應(yīng)：微小的輸入值變化也會(huì)讓輸出值發(fā)生巨大的變化。

• 不可逆：從哈希函數(shù)的輸出值不可反向推導(dǎo)出原始的數(shù)據(jù)。

哈希沖突

重復(fù)一遍，哈希函數(shù)是將任意大小的數(shù)據(jù)映射到固定大小值的函數(shù)。那么，我們可以預(yù)見(jiàn)到，即使哈希函數(shù)設(shè)計(jì)得足夠優(yōu)秀，幾乎每個(gè)輸入值都能映射為不同的哈希值。但是，當(dāng)輸入數(shù)據(jù)足夠大，大到能超過(guò)固定大小值的組合能表達(dá)的最大數(shù)量數(shù)，沖突將不可避免?。▍⒁?jiàn)抽屜原理）

抽屜原理：桌上有十個(gè)蘋(píng)果，要把這十個(gè)蘋(píng)果放到九個(gè)抽屜里，無(wú)論怎樣放，我們會(huì)發(fā)現(xiàn)至少會(huì)有一個(gè)抽屜里面放不少于兩個(gè)蘋(píng)果。抽屜原理有時(shí)也被稱(chēng)為鴿巢原理。

map

源碼解析

嚄 你也是今天的主角了

數(shù)據(jù)結(jié)構(gòu)？

好像和java很像，數(shù)組鏈表。多說(shuō)無(wú)益，沒(méi)什么比源碼更清楚。

// A header for a Go map.
type hmap struct {
    count     int // 代表哈希表中的元素個(gè)數(shù)，調(diào)用len(map)時(shí)，返回的就是該字段值。
    flags     uint8 // 狀態(tài)標(biāo)志，下文常量中會(huì)解釋四種狀態(tài)位含義。
    B         uint8  // buckets（桶）的對(duì)數(shù)log_2（哈希表元素?cái)?shù)量最大可達(dá)到裝載因子*2^B）
    noverflow uint16 // 溢出桶的大概數(shù)量。
    hash0     uint32 // 哈希種子。

    buckets    unsafe.Pointer // 指向buckets數(shù)組的指針，數(shù)組大小為2^B，如果元素個(gè)數(shù)為0，它為nil。
    oldbuckets unsafe.Pointer // 如果發(fā)生擴(kuò)容，oldbuckets是指向老的buckets數(shù)組的指針，老的buckets數(shù)組大小是新的buckets的1/2。非擴(kuò)容狀態(tài)下，它為nil。
    nevacuate  uintptr        // 表示擴(kuò)容進(jìn)度，小于此地址的buckets代表已搬遷完成。

    extra *mapextra // 這個(gè)字段是為了優(yōu)化GC掃描而設(shè)計(jì)的。當(dāng)key和value均不包含指針，并且都可以inline時(shí)使用。extra是指向mapextra類(lèi)型的指針。
}

然后還有個(gè)bmap結(jié)構(gòu)這，每個(gè)bucket里面存儲(chǔ)了kv對(duì)。buckets是一個(gè)指針，指向?qū)嶋H存儲(chǔ)的bucket數(shù)組的首地址。 bucket的結(jié)構(gòu)體如下：

type bmap struct {
	tophash [bucketCnt]uint8  //一個(gè)8個(gè)長(zhǎng)度的uint8組成 
}

其實(shí)上面這個(gè)數(shù)據(jù)結(jié)構(gòu)并不是 golang runtime 時(shí)的結(jié)構(gòu)，在編譯時(shí)候編譯器會(huì)給它動(dòng)態(tài)創(chuàng)建一個(gè)新的結(jié)構(gòu)，如下：

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

bmap 就是我們常說(shuō)的“bucket”結(jié)構(gòu)，每個(gè) bucket 里面最多存儲(chǔ) 8 個(gè) key，這些 key 之所以會(huì)落入同一個(gè)桶，是因?yàn)樗鼈兘?jīng)過(guò)哈希計(jì)算后，哈希結(jié)果是“一類(lèi)”的。在桶內(nèi)，又會(huì)根據(jù) key 計(jì)算出來(lái)的 hash 值的高 8 位來(lái)決定 key 到底落入桶內(nèi)的哪個(gè)位置（一個(gè)桶內(nèi)最多有8個(gè)位置,ps:一類(lèi)的計(jì)算）。

對(duì)應(yīng)一個(gè)圖的話

使用

golang使用，直接用make的。

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

make函數(shù)實(shí)際上會(huì)被編譯器定位到調(diào)用 runtime.makemap()，主要做的工作就是初始化 hmap 結(jié)構(gòu)體的各種字段，例如計(jì)算 B 的大小，設(shè)置哈希種子 hash0 等等。

// 如果編譯器認(rèn)為map和第一個(gè)bucket可以直接創(chuàng)建在棧上，h和bucket可能都是非空
// 如果h != nil，那么map可以直接在h中創(chuàng)建
// 如果h.buckets != nil，那么h指向的bucket可以作為map的第一個(gè)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的值，根據(jù)平臺(tái)系統(tǒng)的差異而不同，具體計(jì)算方式參照src/runtime/malloc.go
    if overflow || mem > maxAlloc {
        hint = 0
    }

// initialize Hmap
    if h == nil {
        h = new(hmap)
    }
  // 通過(guò)fastrand得到哈希種子
    h.hash0 = fastrand()

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

    // 分配初始哈希表
  // 如果B為0，那么buckets字段后續(xù)會(huì)在mapassign方法中l(wèi)azily分配
    if h.B != 0 {
        var nextOverflow *bmap
    // makeBucketArray創(chuàng)建一個(gè)map的底層保存buckets的數(shù)組，它最少會(huì)分配h.B^2的大小。
        h.buckets, nextOverflow = makeBucketArray(t, h.B, nil)
        if nextOverflow != nil {
    h.extra = new(mapextra)
            h.extra.nextOverflow = nextOverflow
        }
    }

    return h
}

根據(jù)上述代碼，我們能確定在正常情況下，正常桶和溢出桶在內(nèi)存中的存儲(chǔ)空間是連續(xù)的，只是被 hmap 中的不同字段引用而已。

注意，這個(gè)函數(shù)返回的結(jié)果：*hmap 是一個(gè)指針，而我們之前講過(guò)的 makeslice 函數(shù)返回的是 Slice 結(jié)構(gòu)體對(duì)象。這也是 makemap 和 makeslice 返回值的區(qū)別所帶來(lái)一個(gè)不同點(diǎn)：當(dāng) map 和 slice 作為函數(shù)參數(shù)時(shí)，在函數(shù)參數(shù)內(nèi)部對(duì) map 的操作會(huì)影響 map 自身；而對(duì) slice 卻不會(huì)（之前講 slice 的文章里有講過(guò)）。

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

hash函數(shù)

哈希函數(shù)的算法與key的類(lèi)型一一對(duì)應(yīng)的。根據(jù) key 的類(lèi)型， maptype結(jié)構(gòu)體的 key字段的alg 字段會(huì)被設(shè)置對(duì)應(yīng)類(lèi)型的 hash 和 equal 函數(shù)。

在初始化go程序運(yùn)行環(huán)境時(shí)（src/runtime/proc.go中的schedinit），就需要通過(guò)alginit方法完成對(duì)哈希的初始化。

hash key桶的分配

對(duì)于 hashmap 來(lái)說(shuō)，最重要的就是根據(jù)key定位實(shí)際存儲(chǔ)位置。key 經(jīng)過(guò)哈希計(jì)算后得到哈希值，哈希值是 64 個(gè) bit 位（針對(duì)64位機(jī)）。根據(jù)hash值的最后B個(gè)bit位來(lái)確定這個(gè)key落在哪個(gè)桶。如果 B = 5，那么桶的數(shù)量，也就是 buckets 數(shù)組的長(zhǎng)度是 2^5 = 32。

suppose，現(xiàn)在有一個(gè) key 經(jīng)過(guò)哈希函數(shù)計(jì)算后，得到的哈希結(jié)果是：

10010111 | 000011110110110010001111001010100010010110010101010 │ 00110

定位key，如果在 bucket 中沒(méi)找到，并且 overflow 不為空，還要繼續(xù)去 overflow bucket 中尋找，直到找到或是所有的 key 槽位都找遍了，包括所有的 overflow bucket。(這里需要遍歷bucket數(shù)組中某個(gè)槽位的bucket鏈表的所有bucket)

擴(kuò)容

使用 key 的 hash 值可以快速定位到目標(biāo) key，然而，隨著向 map 中添加的 key 越來(lái)越多，key 發(fā)生碰撞的概率也越來(lái)越大。bucket 中的 8 個(gè) cell 會(huì)被逐漸塞滿(mǎn)，查找、插入、刪除 key 的效率也會(huì)越來(lái)越低。最理想的情況是一個(gè) bucket 只裝一個(gè) key，這樣，就能達(dá)到 O(1) 的效率，但這樣空間消耗太大，用空間換時(shí)間的代價(jià)太高。

Go 語(yǔ)言采用一個(gè) bucket 里裝載 8 個(gè) key，定位到某個(gè) bucket 后，還需要再定位到具體的 key，這實(shí)際上又用了時(shí)間換空間。

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

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

loadFactor := count / (2^B)

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

再來(lái)說(shuō)觸發(fā) map 擴(kuò)容的時(shí)機(jī)：在向 map 插入新 key 的時(shí)候，會(huì)進(jìn)行條件檢測(cè)，符合下面這 2 個(gè)條件，就會(huì)觸發(fā)擴(kuò)容：

1. 加載因子超過(guò)閾值，源碼里定義的閾值是 6.5。

2. overflow 的 bucket 數(shù)量過(guò)多，這有兩種情況：

• 當(dāng) B 大于15時(shí)，也就是 bucket 總數(shù)大于 2^15 時(shí)，如果overflow的bucket數(shù)量大于2^15，就觸發(fā)擴(kuò)容。

• 當(dāng)B小于15時(shí)，如果overflow的bucket數(shù)量大于2^B 也會(huì)觸發(fā)擴(kuò)容。

如何降低map擴(kuò)容的影響

因?yàn)閙ap擴(kuò)容是很消耗性能的，（桶的新建、復(fù)制），因此我們要盡量減少擴(kuò)容，初始化的時(shí)候?qū)?shù)據(jù)進(jìn)行預(yù)期分配。

sync.Map如何降低鎖的粒度

從map設(shè)計(jì)可以知道，它并不是一個(gè)并發(fā)安全的數(shù)據(jù)結(jié)構(gòu)。同時(shí)對(duì)map進(jìn)行讀寫(xiě)時(shí)，程序很容易出錯(cuò)。因此，要想在并發(fā)情況下使用map，請(qǐng)加上鎖（sync.Mutex或者sync.RwMutex）。其實(shí)，Go標(biāo)準(zhǔn)庫(kù)中已經(jīng)為我們實(shí)現(xiàn)了并發(fā)安全的map——sync.Map。

sync.Map介紹

go 1.9 官方提供了sync.Map 來(lái)優(yōu)化線程安全的并發(fā)讀寫(xiě)的map。該實(shí)現(xiàn)也是基于內(nèi)置map關(guān)鍵字來(lái)實(shí)現(xiàn)的。

這個(gè)實(shí)現(xiàn)類(lèi)似于一個(gè)線程安全的 map[interface{}]interface{} . 這個(gè)map的優(yōu)化主要適用了以下場(chǎng)景：

（1）給定key的鍵值對(duì)只寫(xiě)了一次，但是讀了很多次，比如在只增長(zhǎng)的緩存中； （2）當(dāng)多個(gè)goroutine讀取、寫(xiě)入和覆蓋的key值不相交時(shí)。

在這兩種情況下，使用Map可能比使用單獨(dú)互斥鎖或RWMutex的Go Map大大減少鎖爭(zhēng)用。

對(duì)于其余情況最好還是使用RWMutex保證線程安全。

// 封裝的線程安全的map
type Map struct {
	// lock
	mu Mutex

	// 實(shí)際是readOnly這個(gè)結(jié)構(gòu)
	// 一個(gè)只讀的數(shù)據(jù)結(jié)構(gòu)，因?yàn)橹蛔x，所以不會(huì)有讀寫(xiě)沖突。
	// readOnly包含了map的一部分?jǐn)?shù)據(jù)，用于并發(fā)安全的訪問(wèn)。(冗余，內(nèi)存換性能)
	// 訪問(wèn)這一部分不需要鎖。
	read atomic.Value // readOnly

	// dirty數(shù)據(jù)包含當(dāng)前的map包含的entries,它包含最新的entries(包括read中未刪除的數(shù)據(jù),雖有冗余，但是提升dirty字段為read的時(shí)候非常快，不用一個(gè)一個(gè)的復(fù)制，而是直接將這個(gè)數(shù)據(jù)結(jié)構(gòu)作為read字段的一部分),有些數(shù)據(jù)還可能沒(méi)有移動(dòng)到read字段中。
	// 對(duì)于dirty的操作需要加鎖，因?yàn)閷?duì)它的操作可能會(huì)有讀寫(xiě)競(jìng)爭(zhēng)。
	// 當(dāng)dirty為空的時(shí)候， 比如初始化或者剛提升完，下一次的寫(xiě)操作會(huì)復(fù)制read字段中未刪除的數(shù)據(jù)到這個(gè)數(shù)據(jù)中。
	dirty map[interface{}]*entry

	// 當(dāng)從Map中讀取entry的時(shí)候，如果read中不包含這個(gè)entry,會(huì)嘗試從dirty中讀取，這個(gè)時(shí)候會(huì)將misses加一，
	// 當(dāng)misses累積到 dirty的長(zhǎng)度的時(shí)候， 就會(huì)將dirty提升為read,避免從dirty中miss太多次。因?yàn)椴僮鱠irty需要加鎖。
	misses int
}
// readOnly is an immutable struct stored atomically in the Map.read field.
type readOnly struct {
	m       map[interface{}]*entry
	// 如果Map.dirty有些數(shù)據(jù)不在m中，這個(gè)值為true
	amended bool
}

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

從源碼可以看出，此鎖保持了兩個(gè)map，雖然會(huì)額外占據(jù)空間，但是并不大多少（典型空間換時(shí)間）。

讀數(shù)據(jù)流程

寫(xiě)數(shù)據(jù)流程

刪數(shù)據(jù)流程

總結(jié)優(yōu)化點(diǎn)

1. 無(wú)鎖讀與讀寫(xiě)分離；

2. 寫(xiě)加鎖與延遲提升；

3. 指針與惰性刪除，map保存的value都是指針。惰性刪除，實(shí)際刪除是在 Store時(shí)候去check 然后刪除。

“MAP結(jié)構(gòu)是什么”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識(shí)可以關(guān)注億速云網(wǎng)站，小編將為大家輸出更多高質(zhì)量的實(shí)用文章！