map
和slice類似, map也是引用類型, 當map被復(fù)制為一個新的變量時, 他們只想同一個內(nèi)部數(shù)據(jù)結(jié)構(gòu). 因此改變其中一個變量, 另一個也會收到影響.
package main
import "fmt"
func main() {
personSalary := map[string]int{
"steve": 12000,
"jamie": 15000,
}
personSalary["mike"] = 9000
fmt.Println("Original person salary", personSalary)
newPersonSalary := personSalary
newPersonSalary["mike"] = 18000
fmt.Println("Person Salary changed", personSalary)
}
map的相等性
map之間不餓能使用==操作符判斷, ==只能用來檢查map是否為nil
map底層實現(xiàn)原理
map整體結(jié)構(gòu)圖
go中map底層實現(xiàn)是一個散列表, 因此實現(xiàn)map的過程就是實現(xiàn)散列表的過程. 在這個散列表中, 主要出現(xiàn)的結(jié)構(gòu)體有兩個, 一個叫hmap, 一個叫bucket
hmap:
bucket:
由此可以看出, hmap和bucket的關(guān)系是這樣的:
而bucket又是一個鏈表, 所以, 整體結(jié)構(gòu)應(yīng)該是這樣的:
哈希函數(shù)
哈希表的特點是會有一個哈希函數(shù), 對傳過來的key進行hash運算, 得到唯一分值, 一般情況下都是一個數(shù)值.
在go中, 將求到的hash值一分為二: 高位和低位
key ---> hash函數(shù)f(x) ---> 1234567887654321
在上個公式中, 12345678為高位, 87654321為低位. 低位用于尋找當前key屬于哪個bucket, 而高位用于尋找bucket中的哪個key
特別指出: 在map中的key/value都是存儲到同一個數(shù)組中的
map的擴容
當以上哈希表持續(xù)增長時, Go會將bucket數(shù)組的數(shù)量擴充一倍, 產(chǎn)生一個新的bucket數(shù)組, 并將就數(shù)組數(shù)據(jù)遷移到新數(shù)組
加載因子
加載因子是一個閾值, 一般表示為:
加載因子 = 散列包含的元素數(shù) / 位置總數(shù)
加載因子越小, 說明空間空置率越高, 空間使用率小, 加載因子越大, 說明空間利用率上去了, 但是產(chǎn)生沖突概率高了
當go的map長度增長到大于加載因子所需的長度時, 就會產(chǎn)生一個新的bucket數(shù)組, 然后將舊的bucket數(shù)組遷移到一個屬性字段oldbucket中
注意: 遷移時并不會立即將舊數(shù)組中的元素遷移到新的bucket中, 只有在訪問到具體bucket時才會把數(shù)據(jù)轉(zhuǎn)移到新的bucket中
刪除數(shù)據(jù)
- 如果key是一個指針類型, 則直接將其置為空, 等待GC清除;
- 如果是值類型, 則清除相關(guān)內(nèi)存
- 對value也做同樣的操作
- 最后把key對應(yīng)的高位值的數(shù)組index置為空
