快捷導(dǎo)航

Golang Map簡介以及底層原理

更新時間：2024年10月18日 10:46:28 作者：大廣哥

這篇文章主要介紹了Golang Map簡介以及底層原理的相關(guān)資料,Go語言提供的map是一種鍵值對存儲結(jié)構(gòu),支持基本操作如len、delete等,map是非線程安全的,可用sync.Mutex確保并發(fā)安全,為高效查找和插入,需要的朋友可以參考下

Map 簡介

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

Map 定義

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

Map Iteration

Go語言提供了兩個方法來遍歷map中的所有鍵值對，分別是range方法和Len()方法。

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

Map 的線程安全

在Go語言中，map是非線程安全的，在多線程并發(fā)訪問時可能導(dǎo)致程序報錯。當(dāng)map被多個協(xié)程同時訪問時，我們需要使用sync包中的sync.Mutex來確保操作的原子性和并發(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語言的map在設(shè)計上是一種哈希表的數(shù)據(jù)結(jié)構(gòu)。它利用哈希函數(shù)將鍵映射到不同的存儲空間，從而實(shí)現(xiàn)高效的查找和插入操作。

哈希函數(shù)

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

哈希函數(shù)的計算結(jié)果必須是非負(fù)整數(shù)，因?yàn)樨?fù)數(shù)無法在數(shù)組中表示。
兩個不同字符串的哈希值盡量不要相等，這樣可以避免在查找時產(chǎn)生沖突。

在Go語言中，字符串的哈希函數(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
}

哈希沖突

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

開放尋址法：將發(fā)生沖突的條目逐個檢索新的空棑直到找到一個空位置來存儲當(dāng)前鍵值對
再哈希法：對于發(fā)生沖突的鍵，用另一個不同的哈希函數(shù)計算地址
鏈地址法：對于發(fā)生沖突的鍵，將其存儲在一個鏈表中

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

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

Growing

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

// 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() 將一個bucket中的鍵值對重新映射到新的數(shù)組中
func evacuate(h *hmap, oldbuck *bucket, newbuck *[]keyValue) {
// ...
}

map擴(kuò)容

雙倍擴(kuò)容

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

當(dāng)map的已存儲元素數(shù)量小于map數(shù)組長度的一半時，元素的數(shù)量未達(dá)到哈希表效率的最大值，無需擴(kuò)容；
當(dāng)map已存儲的元素數(shù)量大于等于map數(shù)組長度的一半時，哈希表的查找效率已達(dá)到最大值，所以需要擴(kuò)容。

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

Growing過程

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

避免溢出

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