Go語言基礎(chǔ)學習之map的示例詳解

更新時間：2023年04月08日 11:18:35 作者：天亮^說晚安-

哈希表是常見的數(shù)據(jù)結(jié)構(gòu)，有的語言會將哈希稱作字典或者映射，在Go中，哈希就是常見的數(shù)據(jù)類型map，本文就來聊聊Golang中map的相關(guān)知識吧

Map

map是一種無序的基于key-value的數(shù)據(jù)結(jié)構(gòu)，Go語言中的map是引用類型，必須初始化才能使用。

map定義

Go語言中 map的定義語法如下

map[KeyType]ValueType

其中，

KeyType:表示鍵的類型。

ValueType:表示鍵對應(yīng)的值的類型。

map類型的變量默認初始值為nil，需要使用make()函數(shù)來分配內(nèi)存。語法為：

make(map[KeyType]ValueType, [cap])

其中cap表示map的容量，該參數(shù)雖然不是必須的，但是我們應(yīng)該在初始化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為對應(yīng)的值；不存在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時的元素順序與添加鍵值對的順序無關(guān)。

使用delete()函數(shù)刪除鍵值對

使用delete()內(nèi)建函數(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的時間復(fù)雜度是O(1)。

key與value存儲

最通俗的話說Map是一種通過key來獲取value的一個數(shù)據(jù)結(jié)構(gòu)，其底層存儲方式為數(shù)組，在存儲時key不能重復(fù)，當key重復(fù)時，value進行覆蓋，我們通過key進行hash運算（可以簡單理解為把key轉(zhuǎn)化為一個整形數(shù)字）然后對數(shù)組的長度取余，得到key存儲在數(shù)組的哪個下標位置，最后將key和value組裝為一個結(jié)構(gòu)體，放入數(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的位置，假設(shè)我們遇到另一個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對應(yīng)的下標，比較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對應(yīng)的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的結(jié)構(gòu)，我想大家應(yīng)該很納悶，沒看見kv的結(jié)構(gòu)和overflow指針啊，事實上，這兩個結(jié)構(gòu)體并沒有顯示定義，是通過指針運算進行訪問的。

//bucket結(jié)構(gòu)體定義 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值。
    注意：將所有鍵打包在一起，然后將所有值打包在一起，    使得代碼比交替鍵/值/鍵/值/更復(fù)雜。但它允許//我們消除可能需要的填充，    例如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格式存放，則考慮內(nèi)存對齊v也會占用int64，而按照后者存儲時，8個v剛好占用一個int64,從這個就可以看出go的map設(shè)計之巧妙。

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

go的map存儲源碼如下，省略了一些無關(guān)緊要的代碼

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的結(jié)構(gòu)體
    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
}

到此這篇關(guān)于Go語言基礎(chǔ)學習之map的示例詳解的文章就介紹到這了,更多相關(guān)Go map內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: