Map 簡(jiǎn)介

在Go語(yǔ)言中提供了map數(shù)據(jù)結(jié)構(gòu)來(lái)存儲(chǔ)鍵值對(duì)數(shù)據(jù)。map的數(shù)據(jù)類型為map[K]V，其中K為鍵的類型，V為值的類型。map的鍵類型必須支持==操作符，用來(lái)比較兩個(gè)鍵是否相等。Go語(yǔ)言提供了4種內(nèi)置的map操作: len、delete、comparison、assign。

Map 定義

map_var := make(map[K]V) // 用make函數(shù)創(chuàng)建一個(gè)空的map，其中K和V分別為鍵和值的類型
map_var[key] = value // 向map中添加一個(gè)鍵值對(duì)
value := map_var[key] // 獲取指定鍵的值
delete(map_var, key) // 從map中刪除指定的鍵及其對(duì)應(yīng)的值

Map Iteration

Go語(yǔ)言提供了兩個(gè)方法來(lái)遍歷map中的所有鍵值對(duì)，分別是range方法和Len()方法。

// 使用range循環(huán)遍歷map中的所有鍵值對(duì)
for key, value := range map_var {
// TODO ...
}
// 計(jì)算map中的元素?cái)?shù)量
if len(map_var) > 0 {
// TODO ...
}

Map 的線程安全

在Go語(yǔ)言中，map是非線程安全的，在多線程并發(fā)訪問(wèn)時(shí)可能導(dǎo)致程序報(bào)錯(cuò)。當(dāng)map被多個(gè)協(xié)程同時(shí)訪問(wèn)時(shí)，我們需要使用sync包中的sync.Mutex來(lái)確保操作的原子性和并發(fā)安全。

import "sync"
type SafeMap struct {
mu sync.Mutex
m map[string]int
}
func (sm *SafeMap) Get(key string) int {
sm.mu.Lock()
defer sm.mu.Unlock()
return sm.m[key]
}
func (sm *SafeMap) Set(key string, value int) {
sm.mu.Lock()
defer sm.mu.Unlock()
sm.m[key] = value
}
func (sm *SafeMap) Delete(key string) {
sm.mu.Lock()
defer sm.mu.Unlock()
delete(sm.m, key)
}

map 底層原理

Go語(yǔ)言的map在設(shè)計(jì)上是一種哈希表的數(shù)據(jù)結(jié)構(gòu)。它利用哈希函數(shù)將鍵映射到不同的存儲(chǔ)空間，從而實(shí)現(xiàn)高效的查找和插入操作。

哈希函數(shù)

哈希函數(shù)將字符串映射到一個(gè)整數(shù)上，這稱為哈希值。不同的字符串可能會(huì)有相同的哈希值，但相同的字符串必定具有相同的哈希值。哈希函數(shù)需要滿足兩點(diǎn)：

• 哈希函數(shù)的計(jì)算結(jié)果必須是非負(fù)整數(shù)，因?yàn)樨?fù)數(shù)無(wú)法在數(shù)組中表示。

• 兩個(gè)不同字符串的哈希值盡量不要相等，這樣可以避免在查找時(shí)產(chǎn)生沖突。

在Go語(yǔ)言中，字符串的哈希函數(shù)采用的是FNV-1哈希算法，算法代碼如下：

const (
offset64 = 14695981039346656037
prime64 = 1099511628211
)
func stringHash(s string) uint64 {
h := uint64(offset64)
for i := 0; i < len(s); i++ {
h ^= uint64(s[i])
h *= prime64
}
return h
}

哈希沖突

在哈希表中，哈希值相同的多個(gè)字符串可能會(huì)存儲(chǔ)在同一個(gè)位置上，這種現(xiàn)象叫做哈希沖突。哈希沖突處理策略有開(kāi)放尋址法、再哈希法和鏈地址法。

• 開(kāi)放尋址法：將發(fā)生沖突的條目逐個(gè)檢索新的空棑直到找到一個(gè)空位置來(lái)存儲(chǔ)當(dāng)前鍵值對(duì)

• 再哈希法：對(duì)于發(fā)生沖突的鍵，用另一個(gè)不同的哈希函數(shù)計(jì)算地址

• 鏈地址法：對(duì)于發(fā)生沖突的鍵，將其存儲(chǔ)在一個(gè)鏈表中

Go語(yǔ)言使用鏈地址法處理哈希沖突。對(duì)于每個(gè)存儲(chǔ)單元，map結(jié)構(gòu)體中還維護(hù)了一個(gè)[]keyValue類型的鏈表。

type hmap struct {
count int // 映射中的鍵值對(duì)數(shù)量
flags uint8 // 控制哈希表的一些屬性
B uint8 // 用于計(jì)算哈希地址的初始大小
noverflow uint16 // 鏈表上的溢出桶的數(shù)量
}

Growing

在Go語(yǔ)言中，動(dòng)態(tài)數(shù)組會(huì)自動(dòng)地為map分配更多的空間。Growing過(guò)程涉及到將原始的數(shù)組重新復(fù)制到一個(gè)更大的數(shù)組中，其中原數(shù)組的元素需要重新計(jì)算其在新數(shù)組中的位置，而新數(shù)組的元素則需要將其鍵值對(duì)填充到相應(yīng)的位置。Growing的過(guò)程比較復(fù)雜，可以由函數(shù)hashGrow()來(lái)控制。

// hashGrow() 將map的數(shù)組的大小翻倍，并處理哈希沖突。
func hashGrow(h *hmap) {
// ...
buf := make([]keyValue, newCap)
//...
for i := uintptr(0); i < cap; i++ {
// ...
evacuate(h, &h.oldbuckets[i], &buf)
// ...
}
// ...
}
// evacuate() 將一個(gè)bucket中的鍵值對(duì)重新映射到新的數(shù)組中
func evacuate(h *hmap, oldbuck *bucket, newbuck *[]keyValue) {
// ...
}

map擴(kuò)容

雙倍擴(kuò)容

Go語(yǔ)言中的哈希表在map的數(shù)組容量達(dá)到一定程度時(shí)，就會(huì)自動(dòng)進(jìn)行擴(kuò)容。擴(kuò)容的依據(jù)是當(dāng)前已存儲(chǔ)的元素?cái)?shù)量和數(shù)組的長(zhǎng)度之間的比值：

• 當(dāng)map的已存儲(chǔ)元素?cái)?shù)量小于map數(shù)組長(zhǎng)度的一半時(shí)，元素的數(shù)量未達(dá)到哈希表效率的最大值，無(wú)需擴(kuò)容；

• 當(dāng)map已存儲(chǔ)的元素?cái)?shù)量大于等于map數(shù)組長(zhǎng)度的一半時(shí)，哈希表的查找效率已達(dá)到最大值，所以需要擴(kuò)容。

Go語(yǔ)言的map會(huì)優(yōu)先選擇數(shù)組大小為原數(shù)組大小的2倍，以確保map在存儲(chǔ)過(guò)程中有足夠的空間存放新的元素。當(dāng)元素?cái)?shù)量達(dá)到85%時(shí)，Go語(yǔ)言就會(huì)再次對(duì)數(shù)組進(jìn)行擴(kuò)容，此時(shí)數(shù)組長(zhǎng)度翻倍，以保證數(shù)組長(zhǎng)度和元素?cái)?shù)量的比例始終維持在0.75左右，以平衡效率和空間占用。

Growing過(guò)程

當(dāng)映射中的元素?cái)?shù)量超過(guò)85%時(shí)，Go語(yǔ)言就會(huì)觸發(fā)map的擴(kuò)容過(guò)程。在擴(kuò)容的過(guò)程中，map會(huì)將原有的元素復(fù)制到新的數(shù)組中，并將新數(shù)組的初始大小設(shè)置為原數(shù)組的2倍。對(duì)于發(fā)生哈希沖突的元素，需要在新的數(shù)組中重新計(jì)算哈希地址。

避免溢出

當(dāng)數(shù)組中元素的數(shù)量超過(guò)0x7fffffff(2^31-1，即int類型的最大值)時(shí)，就會(huì)發(fā)生溢出，此時(shí)數(shù)組的大小將無(wú)法達(dá)到原數(shù)組的2倍。所以Go語(yǔ)言會(huì)在初始創(chuàng)建map時(shí)，為其初始化一個(gè)較小的數(shù)組，并設(shè)置map的B值，以便在元素?cái)?shù)量超過(guò)限制時(shí)再次進(jìn)行擴(kuò)容。當(dāng)map中元素的數(shù)量超過(guò)閾值時(shí)，會(huì)再次翻倍，直到數(shù)組大小小于0x7fffffff為止。

代碼分析

hashmap.go包含在Go語(yǔ)言源碼中的src/container/map.go文件中。其中map結(jié)構(gòu)體的定義和Growing實(shí)現(xiàn)都在runtime包中，在src/runtime/map.go文件中。

附錄

• 為什么哈希表的容量要設(shè)置為2的n次冪？為什么不是其他數(shù)字？

• Go語(yǔ)言中的map是如何進(jìn)行線程安全的？原理是什么？

• map的數(shù)據(jù)結(jié)構(gòu)是怎樣的？如何實(shí)現(xiàn)鍵值對(duì)的查找、添加、刪除操作？

• 如何實(shí)現(xiàn)Growing過(guò)程？

• 為什么map的擴(kuò)容條件是85%，而不是100%？

• 在go語(yǔ)言中如何創(chuàng)建map？

• 為什么哈希沖突處理策略有開(kāi)放尋址法、再哈希法和鏈地址法？

• 如果存在沖突，鍵值對(duì)是如何存儲(chǔ)在數(shù)組中的？

• 為什么Growing過(guò)程中會(huì)創(chuàng)建一個(gè)較大的臨時(shí)數(shù)組，而不是直接在原數(shù)組上擴(kuò)展空間？

• 如何實(shí)現(xiàn)map的迭代？

總結(jié)

本節(jié)我們學(xué)習(xí)了Go語(yǔ)言中的map數(shù)據(jù)類型，使用方法以及map的數(shù)據(jù)安全問(wèn)題。

到此這篇關(guān)于Golang Map簡(jiǎn)介以及底層原理的文章就介紹到這了,更多相關(guān)Golang Map詳解內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論