字典的操作、約束

字典（map）它能存儲的不是單一值的集合，而是鍵值對的集合。什么是鍵值對？它是從英文 key-value pair 直譯過來的一個詞。顧名思義，一個鍵值對就代表了一對鍵和值。注意，一個“鍵”和一個“值”分別代表了一個從屬于某一類型的獨立值，把它們兩個捆綁在一起就是一個鍵值對了。Go 語言規(guī)范中，應(yīng)該是為了避免歧義，他們將鍵值對換了一種稱呼，叫做：“鍵 - 元素對”

1、為什么字典的鍵類型會受到約束？

Go 語言的字典類型其實是一個哈希表（hash table）的特定實現(xiàn)，在這個實現(xiàn)中，鍵和元素的最大不同在于，鍵的類型是受限的，而元素卻可以是任意類型的。

如果要探究限制的原因，我們就先要了解哈希表中最重要的一個過程：映射。

鍵和元素的這種對應(yīng)關(guān)系，在數(shù)學(xué)里就被稱為“映射”，這也是“map”這個詞的本意，哈希表的映射過程就存在于對鍵 - 元素對的增、刪、改、查的操作之中。

我們要在哈希表中查找與某個鍵值對應(yīng)的那個元素值，那么我們需要先把鍵值作為參數(shù)傳給這個哈希表。

哈希表會先用哈希函數(shù)（hash function）把鍵值轉(zhuǎn)換為哈希值。哈希值通常是一個無符號的整數(shù)。一個哈希表會持有一定數(shù)量的桶（bucket），我們也可以叫它哈希桶，這些哈希桶會均勻地儲存其所屬哈希表收納的鍵 - 元素對。

因此，哈希表會先用這個鍵哈希值的低幾位去定位到一個哈希桶，然后再去這個哈希桶中，查找這個鍵。

由于鍵 - 元素對總是被捆綁在一起存儲的，所以一旦找到了鍵，就一定能找到對應(yīng)的元素值。隨后，哈希表就會把相應(yīng)的元素值作為結(jié)果返回。

只要這個鍵 - 元素對存在哈希表中就一定會被查找到，因為哈希表增、改、刪鍵 - 元素對時的映射過程，與前文所述如出一轍。

package main
import "fmt"
func main() {
    aMap := map[string]int{
        "one":   1,
        "two":   2,
        "three": 3,
    }
    k := "two"
    v, ok := aMap[k] //這里能夠找到key="two"的鍵，賦值給v，ok返回true
    if ok {
        fmt.Printf("The element of key %q: %d\n", k, v)
    } else {
        fmt.Println("Not found!")
    }
}

go run demo18.go 
The element of key "two": 2

映射過程的第一步就是：把鍵值轉(zhuǎn)換為哈希值。

在 Go 語言的字典中，每一個鍵值都是由它的哈希值代表的。也就是說，字典不會獨立存儲任何鍵的值，但會獨立存儲它們的哈希值。

2、字典的鍵類型不能是哪些類型？

回答是：Go 語言字典的鍵類型不可以是函數(shù)類型、字典類型和切片類型。

Go 語言規(guī)范規(guī)定，在鍵類型的值之間必須可以施加操作符==和!=。換句話說，鍵類型的值必須要支持判等操作。由于函數(shù)類型、字典類型和切片類型的值并不支持判等操作，所以字典的鍵類型不能是這些類型。

另外，如果鍵的類型是接口類型的，那么鍵值的實際類型也不能是上述三種類型，否則在程序運行過程中會引發(fā) panic（即運行時恐慌）。

package main

func main() {
    // 示例1。
    // var badMap1 = map[[]int]int{} // 這里會引發(fā)編譯錯誤。
    // _ = badMap1

    // 示例2。
    //var badMap2 = map[interface{}]int{
    //  "1":      1,
    //  []int{2}: 2, // 這里會引發(fā)panic。
    //  3:        3,
    //}
    //_ = badMap2

    // 示例3。
    //var badMap3 map[[1][]string]int // 這里會引發(fā)編譯錯誤。
    //_ = badMap3

    // 示例4。
    //type BadKey1 struct {
    //  slice []string
    //}
    //var badMap4 map[BadKey1]int // 這里會引發(fā)編譯錯誤。
    //_ = badMap4

    // 示例5。
    //var badMap5 map[[1][2][3][]string]int // 這里會引發(fā)編譯錯誤。
    //_ = badMap5

    // 示例6。
    //type BadKey2Field1 struct {
    //  slice []string
    //}
    //type BadKey2 struct {
    //  field BadKey2Field1
    //}
    //var badMap6 map[BadKey2]int // 這里會引發(fā)編譯錯誤。
    //_ = badMap6

}

示例2 變量badMap2的類型是鍵類型為interface{}、值類型為int的字典類型。這樣聲明并不會引起什么錯誤?；蛘哒f，我通過這樣的聲明躲過了 Go 語言編譯器的檢查

注意，我用字面量在聲明該字典的同時對它進行了初始化，使它包含了三個鍵 - 元素對。其中第二個鍵 - 元素對的鍵值是[]int{2}，元素值是2。這樣的鍵值也不會讓 Go 語言編譯器報錯，因為從語法上說，這樣做是可以的。

當(dāng)我們運行這段代碼的時候，Go 語言的運行時（runtime）系統(tǒng)就會發(fā)現(xiàn)這里的問題，它會拋出一個 panic，并把根源指向字面量中定義第二個鍵 - 元素對的那一行。我們越晚發(fā)現(xiàn)問題，修正問題的成本就會越高，所以最好不要把字典的鍵類型設(shè)定為任何接口類型。如果非要這么做，請一定確保代碼在可控的范圍之內(nèi)。

如果鍵的類型是數(shù)組類型，那么還要確保該類型的元素類型不是函數(shù)類型、字典類型或切片類型。

比如，由于類型[1][]string的元素類型是[]string，所以它就不能作為字典類型的鍵類型。另外，如果鍵的類型是結(jié)構(gòu)體類型，那么還要保證其中字段的類型的合法性。無論不合法的類型被埋藏得有多深，比如map[[1][2][3][]string]int，Go 語言編譯器都會把它揪出來。

你可能會有疑問，為什么鍵類型的值必須支持判等操作？我在前面說過，Go 語言一旦定位到了某一個哈希桶，那么就會試圖在這個桶中查找鍵值。具體是怎么找的呢？

首先，每個哈希桶都會把自己包含的所有鍵的哈希值存起來。Go 語言會用被查找鍵的哈希值與這些哈希值逐個對比，看看是否有相等的。如果一個相等的都沒有，那么就說明這個桶中沒有要查找的鍵值，這時 Go 語言就會立刻返回結(jié)果了。

如果有相等的，那就再用鍵值本身去對比一次。為什么還要對比？原因是，不同值的哈希值是可能相同的。這有個術(shù)語，叫做“哈希碰撞”。

所以，即使哈希值一樣，鍵值也不一定一樣。如果鍵類型的值之間無法判斷相等，那么此時這個映射的過程就沒辦法繼續(xù)下去了。最后，只有鍵的哈希值和鍵值都相等，才能說明查找到了匹配的鍵 - 元素對。

3、應(yīng)該優(yōu)先考慮哪些類型作為字典的鍵類型？

在 Go 語言中，有些類型的值是支持判等的，有些是不支持的。那么在這些值支持判等的類型當(dāng)中，哪些更適合作為字典的鍵類型呢？

這里先拋開我們使用字典時的上下文，只從性能的角度看。在前文所述的映射過程中，“把鍵值轉(zhuǎn)換為哈希值”以及“把要查找的鍵值與哈希桶中的鍵值做對比”， 明顯是兩個重要且比較耗時的操作。

因此，可以說，求哈希和判等操作的速度越快，對應(yīng)的類型就越適合作為鍵類型。

對于所有的基本類型、指針類型，以及數(shù)組類型、結(jié)構(gòu)體類型和接口類型，Go 語言都有一套算法與之對應(yīng)。這套算法中就包含了哈希和判等。以求哈希的操作為例，寬度越小的類型速度通常越快。對于布爾類型、整數(shù)類型、浮點數(shù)類型、復(fù)數(shù)類型和指針類型來說都是如此。對于字符串類型，由于它的寬度是不定的，所以要看它的值的具體長度，長度越短求哈希越快。

類型的寬度是指它的單個值需要占用的字節(jié)數(shù)。比如，bool、int8和uint8類型的一個值需要占用的字節(jié)數(shù)都是1，因此這些類型的寬度就都是1。

以上說的都是基本類型，再來看高級類型。對數(shù)組類型的值求哈希實際上是依次求得它的每個元素的哈希值并進行合并，所以速度就取決于它的元素類型以及它的長度。細(xì)則同上。

與之類似，對結(jié)構(gòu)體類型的值求哈希實際上就是對它的所有字段值求哈希并進行合并，所以關(guān)鍵在于它的各個字段的類型以及字段的數(shù)量。而對于接口類型，具體的哈希算法，則由值的實際類型決定

不建議你使用這些高級數(shù)據(jù)類型作為字典的鍵類型，不僅僅是因為對它們的值求哈希，以及判等的速度較慢，更是因為在它們的值中存在變數(shù)。

比如，對一個數(shù)組來說，我可以任意改變其中的元素值，但在變化前后，它卻代表了兩個不同的鍵值。

對于結(jié)構(gòu)體類型的值情況可能會好一些，因為如果我可以控制其中各字段的訪問權(quán)限的話，就可以阻止外界修改它了。把接口類型作為字典的鍵類型最危險。

如果在這種情況下 Go 運行時系統(tǒng)發(fā)現(xiàn)某個鍵值不支持判等操作，那么就會立即拋出一個 panic。在最壞的情況下，這足以使程序崩潰。

那么，在那些基本類型中應(yīng)該優(yōu)先選擇哪一個？答案是，優(yōu)先選用數(shù)值類型和指針類型，通常情況下類型的寬度越小越好。如果非要選擇字符串類型的話，最好對鍵值的長度進行額外的約束。

那什么是不通常的情況？籠統(tǒng)地說，Go 語言有時會對字典的增、刪、改、查操作做一些優(yōu)化。

比如，在字典的鍵類型為字符串類型的情況下；又比如，在字典的鍵類型為寬度為4或8的整數(shù)類型的情況下。

3、在值為nil的字典上執(zhí)行讀操作會成功嗎，那寫操作呢？

為了避免燒腦太久，我們再來說一個簡單些的問題。由于字典是引用類型，所以當(dāng)我們僅聲明而不初始化一個字典類型的變量的時候，它的值會是nil。

在這樣一個變量上試圖通過鍵值獲取對應(yīng)的元素值，或者添加鍵 - 元素對，會成功嗎？這個問題雖然簡單，但卻是我們必須銘記于心的，因為這涉及程序運行時的穩(wěn)定性。

我來說一下答案。除了添加鍵 - 元素對，我們在一個值為nil的字典上做任何操作都不會引起錯誤。當(dāng)我們試圖在一個值為nil的字典中添加鍵 - 元素對的時候，Go 語言的運行時系統(tǒng)就會立即拋出一個 panic。你可以運行一下 demo19.go 文件試試看。

永遠(yuǎn)要注意那些可能引發(fā) panic 的操作，比如像一個值為nil的字典添加鍵 - 元素對。