Go語言基礎學習之map的示例詳解
Map
map是一種無序的基于key-value的數(shù)據(jù)結構,Go語言中的map是引用類型,必須初始化才能使用。
map定義
Go語言中 map的定義語法如下
map[KeyType]ValueType
其中,
KeyType:表示鍵的類型。
ValueType:表示鍵對應的值的類型。
map類型的變量默認初始值為nil,需要使用make()函數(shù)來分配內存。語法為:
make(map[KeyType]ValueType, [cap])
其中cap表示map的容量,該參數(shù)雖然不是必須的,但是我們應該在初始化map的時候就為其指定一個合適的容量。
map基本使用
map中的數(shù)據(jù)都是成對出現(xiàn)的,map的基本使用示例代碼如下:
func main() {
scoreMap := make(map[string]int, 8)
scoreMap["張三"] = 90
scoreMap["小明"] = 100
fmt.Println(scoreMap)
fmt.Println(scoreMap["小明"])
fmt.Printf("type of a:%T\n", scoreMap)
}
輸出:
map[小明:100 張三:90]
100
type of a:map[string]int
map也支持在聲明的時候填充元素,例如:
func main() {
userInfo := map[string]string{
"username": "pprof.cn",
"password": "123456",
}
fmt.Println(userInfo) //
}
判斷某個鍵是否存在
Go語言中有個判斷map中鍵是否存在的特殊寫法,格式如下:
value, ok := map[key]
舉個例子:
func main() {
scoreMap := make(map[string]int)
scoreMap["張三"] = 90
scoreMap["小明"] = 100
// 如果key存在ok為true,v為對應的值;不存在ok為false,v為值類型的零值
v, ok := scoreMap["張三"]
if ok {
fmt.Println(v)
} else {
fmt.Println("查無此人")
}
}
map的遍歷
Go語言中使用for range遍歷map。
func main() {
scoreMap := make(map[string]int)
scoreMap["張三"] = 90
scoreMap["小明"] = 100
scoreMap["王五"] = 60
for k, v := range scoreMap {
fmt.Println(k, v)
}
}
但我們只想遍歷key的時候,可以按下面的寫法:
func main() {
scoreMap := make(map[string]int)
scoreMap["張三"] = 90
scoreMap["小明"] = 100
scoreMap["王五"] = 60
for k := range scoreMap {
fmt.Println(k)
}
}
注意: 遍歷map時的元素順序與添加鍵值對的順序無關。
使用delete()函數(shù)刪除鍵值對
使用delete()內建函數(shù)從map中刪除一組鍵值對,delete()函數(shù)的格式如下:
delete(map, key)
其中,
map:表示要刪除鍵值對的map
key:表示要刪除的鍵值對的鍵
示例代碼如下:
func main(){
scoreMap := make(map[string]int)
scoreMap["張三"] = 90
scoreMap["小明"] = 100
scoreMap["王五"] = 60
delete(scoreMap, "小明")//將小明:100從map中刪除
for k,v := range scoreMap{
fmt.Println(k, v)
}
}
按照指定順序遍歷map
func main() {
rand.Seed(time.Now().UnixNano()) //初始化隨機數(shù)種子
var scoreMap = make(map[string]int, 200)
for i := 0; i < 100; i++ {
key := fmt.Sprintf("stu%02d", i) //生成stu開頭的字符串
value := rand.Intn(100) //生成0~99的隨機整數(shù)
scoreMap[key] = value
}
//取出map中的所有key存入切片keys
var keys = make([]string, 0, 200)
for key := range scoreMap {
keys = append(keys, key)
}
//對切片進行排序
sort.Strings(keys)
//按照排序后的key遍歷map
for _, key := range keys {
fmt.Println(key, scoreMap[key])
}
}
元素為map類型的切片
下面的代碼演示了切片中的元素為map類型時的操作:
func main() {
var mapSlice = make([]map[string]string, 3)
for index, value := range mapSlice {
fmt.Printf("index:%d value:%v\n", index, value)
}
fmt.Println("after init")
// 對切片中的map元素進行初始化
mapSlice[0] = make(map[string]string, 10)
mapSlice[0]["name"] = "王五"
mapSlice[0]["password"] = "123456"
mapSlice[0]["address"] = "紅旗大街"
for index, value := range mapSlice {
fmt.Printf("index:%d value:%v\n", index, value)
}
}
值為切片類型的map
下面的代碼演示了map中值為切片類型的操作:
func main() {
var sliceMap = make(map[string][]string, 3)
fmt.Println(sliceMap)
fmt.Println("after init")
key := "中國"
value, ok := sliceMap[key]
if !ok {
value = make([]string, 0, 2)
}
value = append(value, "北京", "上海")
sliceMap[key] = value
fmt.Println(sliceMap)
}
len(m)獲取map的長度,go不支持對map上執(zhí)行cap函數(shù)。
map中的key可以是任意能夠用==操作符比較的類型,不能是函數(shù)、map、切片,以及包含上述3中類型成員變量的的struct。map的value可以是任意類型。
type f func(int) bool
type m map[int]byte
type s []int
type i int
var m1 map[i]f
fmt.Println(m1)
/** 函數(shù)、map、切片不能當key **/
// var m2 map[f]bool
// fmt.Println(m2)
// var m3 map[m]bool
// fmt.Println(m3)
// var m4 map[s]bool
// fmt.Println(m4)
type user struct {
scores float32 //如果scores是slice,則user不能作為map的key
}
u := user{}
m5 := make(map[user]interface{})
m5[u] = 5
fmt.Println(m5)
Map實現(xiàn)原理
什么是Map
go map的底層實現(xiàn)是hash table,根據(jù)key查找value的時間復雜度是O(1)。

key與value存儲
最通俗的話說Map是一種通過key來獲取value的一個數(shù)據(jù)結構,其底層存儲方式為數(shù)組,在存儲時key不能重復,當key重復時,value進行覆蓋,我們通過key進行hash運算(可以簡單理解為把key轉化為一個整形數(shù)字)然后對數(shù)組的長度取余,得到key存儲在數(shù)組的哪個下標位置,最后將key和value組裝為一個結構體,放入數(shù)組下標處,看下圖:
length = len(array) = 4
hashkey1 = hash(xiaoming) = 4
index1 = hashkey1% length= 0
hashkey2 = hash(xiaoli) = 6
index2 = hashkey2% length= 2

hash沖突
如上圖所示,數(shù)組一個下標處只能存儲一個元素,也就是說一個數(shù)組下標只能存儲一對key,value, hashkey(xiaoming)=4占用了下標0的位置,假設我們遇到另一個key,hashkey(xiaowang)也是4,這就是hash沖突(不同的key經(jīng)過hash之后得到的值一樣),那么key=xiaowang的怎么存儲?
hash沖突的常見解決方法
開放定址法:也就是說當我們存儲一個key,value時,發(fā)現(xiàn)hashkey(key)的下標已經(jīng)被別key占用,那我們在這個數(shù)組中空間中重新找一個沒被占用的存儲這個沖突的key,那么沒被占用的有很多,找哪個好呢?常見的有線性探測法,線性補償探測法,隨機探測法,這里我們主要說一下線性探測法
線性探測,字面意思就是按照順序來,從沖突的下標處開始往后探測,到達數(shù)組末尾時,從數(shù)組開始處探測,直到找到一個空位置存儲這個key,當數(shù)組都找不到的情況下回擴容(事實上當數(shù)組容量快滿的時候就會擴容了);查找某一個key的時候,找到key對應的下標,比較key是否相等,如果相等直接取出來,否則按照順尋探測直到碰到一個空位置,說明key不存在。如下圖:首先存儲key=xiaoming在下標0處,當存儲key=xiaowang時,hash沖突了,按照線性探測,存儲在下標1處,(紅色的線是沖突或者下標已經(jīng)被占用了) 再者key=xiaozhao存儲在下標4處,當存儲key=xiaoliu是,hash沖突了,按照線性探測,從頭開始,存儲在下標2處 (黃色的是沖突或者下標已經(jīng)被占用了)

拉鏈法:何為拉鏈,簡單理解為鏈表,當key的hash沖突時,我們在沖突位置的元素上形成一個鏈表,通過指針互連接,當查找時,發(fā)現(xiàn)key沖突,順著鏈表一直往下找,直到鏈表的尾節(jié)點,找不到則返回空,如下圖:

開放定址(線性探測)和拉鏈的優(yōu)缺點
- 由上面可以看出拉鏈法比線性探測處理簡單
- 線性探測查找是會被拉鏈法會更消耗時間
- 線性探測會更加容易導致擴容,而拉鏈不會
- 拉鏈存儲了指針,所以空間上會比線性探測占用多一點
- 拉鏈是動態(tài)申請存儲空間的,所以更適合鏈長不確定的
Go中Map的使用
直接用代碼描述,直觀,簡單,易理解
//直接創(chuàng)建初始化一個mao
var mapInit = map[string]string {"xiaoli":"湖南", "xiaoliu":"天津"}
//聲明一個map類型變量,
//map的key的類型是string,value的類型是string
var mapTemp map[string]string
//使用make函數(shù)初始化這個變量,并指定大小(也可以不指定)
mapTemp = make(map[string]string,10)
//存儲key ,value
mapTemp["xiaoming"] = "北京"
mapTemp["xiaowang"]= "河北"
//根據(jù)key獲取value,
//如果key存在,則ok是true,否則是flase
//v1用來接收key對應的value,當ok是false時,v1是nil
v1,ok := mapTemp["xiaoming"]
fmt.Println(ok,v1)
//當key=xiaowang存在時打印value
if v2,ok := mapTemp["xiaowang"]; ok{
fmt.Println(v2)
}
//遍歷map,打印key和value
for k,v := range mapTemp{
fmt.Println(k,v)
}
//刪除map中的key
delete(mapTemp,"xiaoming")
//獲取map的大小
l := len(mapTemp)
fmt.Println(l)
看了上面的map創(chuàng)建,初始化,增刪改查等操作,我們發(fā)現(xiàn)go的api其實挺簡單易學的
Go中Map的實現(xiàn)原理
知其然,更得知其所以然,會使用map了,多問問為什么,go底層map到底怎么存儲呢?接下來我們一探究竟。map的源碼位于 src/runtime/map.go中 筆者go的版本是1.12在go中,map同樣也是數(shù)組存儲的的,每個數(shù)組下標處存儲的是一個bucket,這個bucket的類型見下面代碼,每個bucket中可以存儲8個kv鍵值對,當每個bucket存儲的kv對到達8個之后,會通過overflow指針指向一個新的bucket,從而形成一個鏈表,看bmap的結構,我想大家應該很納悶,沒看見kv的結構和overflow指針啊,事實上,這兩個結構體并沒有顯示定義,是通過指針運算進行訪問的。
//bucket結構體定義 b就是bucket
type bmap{
// tophash generally contains the top byte of the hash value
// for each key in this bucket. If tophash[0] < minTopHash,
// tophash[0] is a bucket evacuation state instead.
//翻譯:top hash通常包含該bucket中每個鍵的hash值的高八位。
如果tophash[0]小于mintophash,則tophash[0]為桶疏散狀態(tài) //bucketCnt 的初始值是8
tophash [bucketCnt]uint8
// Followed by bucketCnt keys and then bucketCnt values.
// NOTE: packing all the keys together and then all the values together makes the // code a bit more complicated than alternating key/value/key/value/... but it allows // us to eliminate padding which would be needed for, e.g., map[int64]int8.// Followed by an overflow pointer. //翻譯:接下來是bucketcnt鍵,然后是bucketcnt值。
注意:將所有鍵打包在一起,然后將所有值打包在一起, 使得代碼比交替鍵/值/鍵/值/更復雜。但它允許//我們消除可能需要的填充, 例如map[int64]int8./后面跟一個溢出指針}
看上面代碼以及注釋,我們能得到bucket中存儲的kv是這樣的,tophash用來快速查找key值是否在該bucket中,而不同每次都通過真值進行比較;還有kv的存放,為什么不是k1v1,k2v2…… 而是k1k2…v1v2…,我們看上面的注釋說的 map[int64]int8,key是int64(8個字節(jié)),value是int8(一個字節(jié)),kv的長度不同,如果按照kv格式存放,則考慮內存對齊v也會占用int64,而按照后者存儲時,8個v剛好占用一個int64,從這個就可以看出go的map設計之巧妙。

最后我們分析一下go的整體內存結構,閱讀一下map存儲的源碼,如下圖所示,當往map中存儲一個kv對時,通過k獲取hash值,hash值的低八位和bucket數(shù)組長度取余,定位到在數(shù)組中的那個下標,hash值的高八位存儲在bucket中的tophash中,用來快速判斷key是否存在,key和value的具體值則通過指針運算存儲,當一個bucket滿時,通過overfolw指針鏈接到下一個bucket。

go的map存儲源碼如下,省略了一些無關緊要的代碼
func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
//獲取hash算法
alg := t.key.alg
//計算hash值
hash := alg.hash(key, uintptr(h.hash0))
//如果bucket數(shù)組一開始為空,則初始化
if h.buckets == nil {
h.buckets = newobject(t.bucket) // newarray(t.bucket, 1)
}
again:
// 定位存儲在哪一個bucket中
bucket := hash & bucketMask(h.B)
//得到bucket的結構體
b := (*bmap)(unsafe.Pointer(uintptr(h.buckets) +bucket*uintptr(t.bucketsize)))
//獲取高八位hash值
top := tophash(hash)
var inserti *uint8
var insertk unsafe.Pointer
var val unsafe.Pointer
bucketloop:
//死循環(huán)
for {
//循環(huán)bucket中的tophash數(shù)組
for i := uintptr(0); i < bucketCnt; i++ {
//如果hash不相等
if b.tophash[i] != top {
//判斷是否為空,為空則插入
if isEmpty(b.tophash[i]) && inserti == nil {
inserti = &b.tophash[i]
insertk = add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
val = add( unsafe.Pointer(b),
dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize) )
}
//插入成功,終止最外層循環(huán)
if b.tophash[i] == emptyRest {
break bucketloop
}
continue
}
//到這里說明高八位hash一樣,獲取已存在的key
k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
if t.indirectkey() {
k = *((*unsafe.Pointer)(k))
}
//判斷兩個key是否相等,不相等就循環(huán)下一個
if !alg.equal(key, k) {
continue
}
// 如果相等則更新
if t.needkeyupdate() {
typedmemmove(t.key, k, key)
}
//獲取已存在的value
val = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))
goto done
}
//如果上一個bucket沒能插入,則通過overflow獲取鏈表上的下一個bucket
ovf := b.overflow(t)
if ovf == nil {
break
}
b = ovf
}
if inserti == nil {
// all current buckets are full, allocate a new one.
newb := h.newoverflow(t, b)
inserti = &newb.tophash[0]
insertk = add(unsafe.Pointer(newb), dataOffset)
val = add(insertk, bucketCnt*uintptr(t.keysize))
}
// store new key/value at insert position
if t.indirectkey() {
kmem := newobject(t.key)
*(*unsafe.Pointer)(insertk) = kmem
insertk = kmem
}
if t.indirectvalue() {
vmem := newobject(t.elem)
*(*unsafe.Pointer)(val) = vmem
}
typedmemmove(t.key, insertk, key)
//將高八位hash值存儲
*inserti = top
h.count++
return val
}
到此這篇關于Go語言基礎學習之map的示例詳解的文章就介紹到這了,更多相關Go map內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家!
相關文章
golang struct, map, json之間的相互轉換
本文用于記錄我在 golang 學習階段遇到的類型轉換問題,針對的是 json 、map、struct 之間相互轉換的問題,感興趣的可以了解一下2021-06-06
Go開發(fā)go-optioner工具實現(xiàn)輕松生成函數(shù)選項模式代碼
go-optioner?是一個在?Go?代碼中生成函數(shù)選項模式代碼的工具,可以根據(jù)給定的結構定義自動生成相應的選項代碼,下面就來聊聊go-optioner是如何使用的吧2023-07-07
詳解Go語言如何利用高階函數(shù)寫出優(yōu)雅的代碼
高階函數(shù)(Hiher-order?Function)定義為:滿足下列條件之一的函數(shù):接收一個或多個函數(shù)作為參數(shù);返回值是一個函數(shù)。本文為大家介紹了如何利用高階函數(shù)寫出優(yōu)雅的代碼,希望對大家有所幫助2023-01-01

