Go 語言 Map

原文鏈接：https://gopl-zh.github.io/ch4/ch4-03.html

4.3. Map

哈希表是一種巧妙并且實用的數(shù)據(jù)結(jié)構(gòu)。它是一個無序的key/value對的集合，其中所有的key都是不同的，然后通過給定的key可以在常數(shù)時間復(fù)雜度內(nèi)檢索、更新或刪除對應(yīng)的value。

在Go語言中，一個map就是一個哈希表的引用，map類型可以寫為map[K]V，其中K和V分別對應(yīng)key和value。map中所有的key都有相同的類型，所有的value也有著相同的類型，但是key和value之間可以是不同的數(shù)據(jù)類型。其中K對應(yīng)的key必須是支持==比較運算符的數(shù)據(jù)類型，所以map可以通過測試key是否相等來判斷是否已經(jīng)存在。雖然浮點數(shù)類型也是支持相等運算符比較的，但是將浮點數(shù)用做key類型則是一個壞的想法，正如第三章提到的，最壞的情況是可能出現(xiàn)的NaN和任何浮點數(shù)都不相等。對于V對應(yīng)的value數(shù)據(jù)類型則沒有任何的限制。

內(nèi)置的make函數(shù)可以創(chuàng)建一個map：

ages := make(map[string]int) // mapping from strings to ints

我們也可以用map字面值的語法創(chuàng)建map，同時還可以指定一些最初的key/value：

ages := map[string]int{
    "alice":   31,
    "charlie": 34,
}

這相當(dāng)于

ages := make(map[string]int)
ages["alice"] = 31
ages["charlie"] = 34

因此，另一種創(chuàng)建空的map的表達式是map[string]int{}。

Map中的元素通過key對應(yīng)的下標(biāo)語法訪問：

ages["alice"] = 32
fmt.Println(ages["alice"]) // "32"

使用內(nèi)置的delete函數(shù)可以刪除元素：

delete(ages, "alice") // remove element ages["alice"]

所有這些操作是安全的，即使這些元素不在map中也沒有關(guān)系；如果一個查找失敗將返回value類型對應(yīng)的零值，例如，即使map中不存在“bob”下面的代碼也可以正常工作，因為ages["bob"]失敗時將返回0。

ages["bob"] = ages["bob"] + 1 // happy birthday!

而且x += y和x++等簡短賦值語法也可以用在map上，所以上面的代碼可以改寫成

ages["bob"] += 1

更簡單的寫法

ages["bob"]++

但是map中的元素并不是一個變量，因此我們不能對map的元素進行取址操作：

_ = &ages["bob"] // compile error: cannot take address of map element

禁止對map元素取址的原因是map可能隨著元素數(shù)量的增長而重新分配更大的內(nèi)存空間，從而可能導(dǎo)致之前的地址無效。

要想遍歷map中全部的key/value對的話，可以使用range風(fēng)格的for循環(huán)實現(xiàn)，和之前的slice遍歷語法類似。下面的迭代語句將在每次迭代時設(shè)置name和age變量，它們對應(yīng)下一個鍵/值對：

for name, age := range ages {
    fmt.Printf("%s\t%d\n", name, age)
}

Map的迭代順序是不確定的，并且不同的哈希函數(shù)實現(xiàn)可能導(dǎo)致不同的遍歷順序。在實踐中，遍歷的順序是隨機的，每一次遍歷的順序都不相同。這是故意的，每次都使用隨機的遍歷順序可以強制要求程序不會依賴具體的哈希函數(shù)實現(xiàn)。如果要按順序遍歷key/value對，我們必須顯式地對key進行排序，可以使用sort包的Strings函數(shù)對字符串slice進行排序。下面是常見的處理方式：

import "sort"

var names []string
for name := range ages {
    names = append(names, name)
}
sort.Strings(names)
for _, name := range names {
    fmt.Printf("%s\t%d\n", name, ages[name])
}

因為我們一開始就知道names的最終大小，因此給slice分配一個合適的大小將會更有效。下面的代碼創(chuàng)建了一個空的slice，但是slice的容量剛好可以放下map中全部的key：

names := make([]string, 0, len(ages))

在上面的第一個range循環(huán)中，我們只關(guān)心map中的key，所以我們忽略了第二個循環(huán)變量。在第二個循環(huán)中，我們只關(guān)心names中的名字，所以我們使用“_”空白標(biāo)識符來忽略第一個循環(huán)變量，也就是迭代slice時的索引。

map類型的零值是nil，也就是沒有引用任何哈希表。

var ages map[string]int
fmt.Println(ages == nil)    // "true"
fmt.Println(len(ages) == 0) // "true"

map上的大部分操作，包括查找、刪除、len和range循環(huán)都可以安全工作在nil值的map上，它們的行為和一個空的map類似。但是向一個nil值的map存入元素將導(dǎo)致一個panic異常：

ages["carol"] = 21 // panic: assignment to entry in nil map

在向map存數(shù)據(jù)前必須先創(chuàng)建map。

通過key作為索引下標(biāo)來訪問map將產(chǎn)生一個value。如果key在map中是存在的，那么將得到與key對應(yīng)的value；如果key不存在，那么將得到value對應(yīng)類型的零值，正如我們前面看到的ages["bob"]那樣。這個規(guī)則很實用，但是有時候可能需要知道對應(yīng)的元素是否真的是在map之中。例如，如果元素類型是一個數(shù)字，你可能需要區(qū)分一個已經(jīng)存在的0，和不存在而返回零值的0，可以像下面這樣測試：

age, ok := ages["bob"]
if !ok { /* "bob" is not a key in this map; age == 0. */ }

你會經(jīng)?？吹綄⑦@兩個結(jié)合起來使用，像這樣：

if age, ok := ages["bob"]; !ok { /* ... */ }

在這種場景下，map的下標(biāo)語法將產(chǎn)生兩個值；第二個是一個布爾值，用于報告元素是否真的存在。布爾變量一般命名為ok，特別適合馬上用于if條件判斷部分。

和slice一樣，map之間也不能進行相等比較；唯一的例外是和nil進行比較。要判斷兩個map是否包含相同的key和value，我們必須通過一個循環(huán)實現(xiàn)：

func equal(x, y map[string]int) bool {
    if len(x) != len(y) {
        return false
    }
    for k, xv := range x {
        if yv, ok := y[k]; !ok || yv != xv {
            return false
        }
    }
    return true
}

從例子中可以看到如何用!ok來區(qū)分元素不存在，與元素存在但為0的。我們不能簡單地用xv != y[k]判斷，那樣會導(dǎo)致在判斷下面兩個map時產(chǎn)生錯誤的結(jié)果：

// True if equal is written incorrectly.
equal(map[string]int{"A": 0}, map[string]int{"B": 42})

Go語言中并沒有提供一個set類型，但是map中的key也是不相同的，可以用map實現(xiàn)類似set的功能。為了說明這一點，下面的dedup程序讀取多行輸入，但是只打印第一次出現(xiàn)的行。（它是1.3節(jié)中出現(xiàn)的dup程序的變體。）dedup程序通過map來表示所有的輸入行所對應(yīng)的set集合，以確保已經(jīng)在集合存在的行不會被重復(fù)打印。

gopl.io/ch4/dedup

func main() {
    seen := make(map[string]bool) // a set of strings
    input := bufio.NewScanner(os.Stdin)
    for input.Scan() {
        line := input.Text()
        if !seen[line] {
            seen[line] = true
            fmt.Println(line)
        }
    }

    if err := input.Err(); err != nil {
        fmt.Fprintf(os.Stderr, "dedup: %v\n", err)
        os.Exit(1)
    }
}

Go程序員將這種忽略value的map當(dāng)作一個字符串集合，并非所有map[string]bool類型value都是無關(guān)緊要的；有一些則可能會同時包含true和false的值。

有時候我們需要一個map或set的key是slice類型，但是map的key必須是可比較的類型，但是slice并不滿足這個條件。不過，我們可以通過兩個步驟繞過這個限制。第一步，定義一個輔助函數(shù)k，將slice轉(zhuǎn)為map對應(yīng)的string類型的key，確保只有x和y相等時k(x) == k(y)才成立。然后創(chuàng)建一個key為string類型的map，在每次對map操作時先用k輔助函數(shù)將slice轉(zhuǎn)化為string類型。

下面的例子演示了如何使用map來記錄提交相同的字符串列表的次數(shù)。它使用了fmt.Sprintf函數(shù)將字符串列表轉(zhuǎn)換為一個字符串以用于map的key，通過%q參數(shù)忠實地記錄每個字符串元素的信息：

var m = make(map[string]int)

func k(list []string) string { return fmt.Sprintf("%q", list) }

func Add(list []string)       { m[k(list)]++ }
func Count(list []string) int { return m[k(list)] }

使用同樣的技術(shù)可以處理任何不可比較的key類型，而不僅僅是slice類型。這種技術(shù)對于想使用自定義key比較函數(shù)的時候也很有用，例如在比較字符串的時候忽略大小寫。同時，輔助函數(shù)k(x)也不一定是字符串類型，它可以返回任何可比較的類型，例如整數(shù)、數(shù)組或結(jié)構(gòu)體等。

這是map的另一個例子，下面的程序用于統(tǒng)計輸入中每個Unicode碼點出現(xiàn)的次數(shù)。雖然Unicode全部碼點的數(shù)量巨大，但是出現(xiàn)在特定文檔中的字符種類并沒有多少，使用map可以用比較自然的方式來跟蹤那些出現(xiàn)過的字符的次數(shù)。

gopl.io/ch4/charcount

// Charcount computes counts of Unicode characters.
package main

import (
    "bufio"
    "fmt"
    "io"
    "os"
    "unicode"
    "unicode/utf8"
)

func main() {
    counts := make(map[rune]int)    // counts of Unicode characters
    var utflen [utf8.UTFMax + 1]int // count of lengths of UTF-8 encodings
    invalid := 0                    // count of invalid UTF-8 characters

    in := bufio.NewReader(os.Stdin)
    for {
        r, n, err := in.ReadRune() // returns rune, nbytes, error
        if err == io.EOF {
            break
        }
        if err != nil {
            fmt.Fprintf(os.Stderr, "charcount: %v\n", err)
            os.Exit(1)
        }
        if r == unicode.ReplacementChar && n == 1 {
            invalid++
            continue
        }
        counts[r]++
        utflen[n]++
    }
    fmt.Printf("rune\tcount\n")
    for c, n := range counts {
        fmt.Printf("%q\t%d\n", c, n)
    }
    fmt.Print("\nlen\tcount\n")
    for i, n := range utflen {
        if i > 0 {
            fmt.Printf("%d\t%d\n", i, n)
        }
    }
    if invalid > 0 {
        fmt.Printf("\n%d invalid UTF-8 characters\n", invalid)
    }
}

ReadRune方法執(zhí)行UTF-8解碼并返回三個值：解碼的rune字符的值，字符UTF-8編碼后的長度，和一個錯誤值。我們可預(yù)期的錯誤值只有對應(yīng)文件結(jié)尾的io.EOF。如果輸入的是無效的UTF-8編碼的字符，返回的將是unicode.ReplacementChar表示無效字符，并且編碼長度是1。

charcount程序同時打印不同UTF-8編碼長度的字符數(shù)目。對此，map并不是一個合適的數(shù)據(jù)結(jié)構(gòu)；因為UTF-8編碼的長度總是從1到utf8.UTFMax（最大是4個字節(jié)），使用數(shù)組將更有效。

作為一個實驗，我們用charcount程序?qū)τ⑽陌嬖宓淖址M行了統(tǒng)計。雖然大部分是英語，但是也有一些非ASCII字符。下面是排名前10的非ASCII字符：

下面是不同UTF-8編碼長度的字符的數(shù)目：

len count
1   765391
2   60
3   70
4   0

Map的value類型也可以是一個聚合類型，比如是一個map或slice。在下面的代碼中，圖graph的key類型是一個字符串，value類型map[string]bool代表一個字符串集合。從概念上講，graph將一個字符串類型的key映射到一組相關(guān)的字符串集合，它們指向新的graph的key。

gopl.io/ch4/graph

var graph = make(map[string]map[string]bool)

func addEdge(from, to string) {
    edges := graph[from]
    if edges == nil {
        edges = make(map[string]bool)
        graph[from] = edges
    }
    edges[to] = true
}

func hasEdge(from, to string) bool {
    return graph[from][to]
}

其中addEdge函數(shù)惰性初始化map是一個慣用方式，也就是說在每個值首次作為key時才初始化。hasEdge函數(shù)顯示了如何讓map的零值也能正常工作；即使from到to的邊不存在，graph[from][to]依然可以返回一個有意義的結(jié)果。

練習(xí) 4.8： 修改charcount程序，使用unicode.IsLetter等相關(guān)的函數(shù)，統(tǒng)計字母、數(shù)字等Unicode中不同的字符類別。

練習(xí) 4.9： 編寫一個程序wordfreq程序，報告輸入文本中每個單詞出現(xiàn)的頻率。在第一次調(diào)用Scan前先調(diào)用input.Split(bufio.ScanWords)函數(shù)，這樣可以按單詞而不是按行輸入。