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

4.3. Map

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

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

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

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

我們也可以用map字面值的語(yǔ)法創(chuàng)建map，同時(shí)還可以指定一些最初的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的表達(dá)式是map[string]int{}。

Map中的元素通過(guò)key對(duì)應(yīng)的下標(biāo)語(yǔ)法訪問(wèn)：

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

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

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

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

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

而且x += y和x++等簡(jiǎn)短賦值語(yǔ)法也可以用在map上，所以上面的代碼可以改寫(xiě)成

ages["bob"] += 1

更簡(jiǎn)單的寫(xiě)法

ages["bob"]++

但是map中的元素并不是一個(gè)變量，因此我們不能對(duì)map的元素進(jìn)行取址操作：

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

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

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

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

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

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])
}

因?yàn)槲覀円婚_(kāi)始就知道names的最終大小，因此給slice分配一個(gè)合適的大小將會(huì)更有效。下面的代碼創(chuàng)建了一個(gè)空的slice，但是slice的容量剛好可以放下map中全部的key：

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

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

map類(lèi)型的零值是nil，也就是沒(méi)有引用任何哈希表。

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

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

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

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

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

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

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

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

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

和slice一樣，map之間也不能進(jìn)行相等比較；唯一的例外是和nil進(jìn)行比較。要判斷兩個(gè)map是否包含相同的key和value，我們必須通過(guò)一個(gè)循環(huán)實(shí)現(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來(lái)區(qū)分元素不存在，與元素存在但為0的。我們不能簡(jiǎn)單地用xv != y[k]判斷，那樣會(huì)導(dǎo)致在判斷下面兩個(gè)map時(shí)產(chǎn)生錯(cuò)誤的結(jié)果：

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

Go語(yǔ)言中并沒(méi)有提供一個(gè)set類(lèi)型，但是map中的key也是不相同的，可以用map實(shí)現(xiàn)類(lèi)似set的功能。為了說(shuō)明這一點(diǎn)，下面的dedup程序讀取多行輸入，但是只打印第一次出現(xiàn)的行。（它是1.3節(jié)中出現(xiàn)的dup程序的變體。）dedup程序通過(guò)map來(lái)表示所有的輸入行所對(duì)應(yīng)的set集合，以確保已經(jīng)在集合存在的行不會(huì)被重復(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)作一個(gè)字符串集合，并非所有map[string]bool類(lèi)型value都是無(wú)關(guān)緊要的；有一些則可能會(huì)同時(shí)包含true和false的值。

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

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

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類(lèi)型，而不僅僅是slice類(lèi)型。這種技術(shù)對(duì)于想使用自定義key比較函數(shù)的時(shí)候也很有用，例如在比較字符串的時(shí)候忽略大小寫(xiě)。同時(shí)，輔助函數(shù)k(x)也不一定是字符串類(lèi)型，它可以返回任何可比較的類(lèi)型，例如整數(shù)、數(shù)組或結(jié)構(gòu)體等。

這是map的另一個(gè)例子，下面的程序用于統(tǒng)計(jì)輸入中每個(gè)Unicode碼點(diǎn)出現(xiàn)的次數(shù)。雖然Unicode全部碼點(diǎn)的數(shù)量巨大，但是出現(xiàn)在特定文檔中的字符種類(lèi)并沒(méi)有多少，使用map可以用比較自然的方式來(lái)跟蹤那些出現(xiàn)過(guò)的字符的次數(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解碼并返回三個(gè)值：解碼的rune字符的值，字符UTF-8編碼后的長(zhǎng)度，和一個(gè)錯(cuò)誤值。我們可預(yù)期的錯(cuò)誤值只有對(duì)應(yīng)文件結(jié)尾的io.EOF。如果輸入的是無(wú)效的UTF-8編碼的字符，返回的將是unicode.ReplacementChar表示無(wú)效字符，并且編碼長(zhǎng)度是1。

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

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

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

len count
1   765391
2   60
3   70
4   0

Map的value類(lèi)型也可以是一個(gè)聚合類(lèi)型，比如是一個(gè)map或slice。在下面的代碼中，圖graph的key類(lèi)型是一個(gè)字符串，value類(lèi)型map[string]bool代表一個(gè)字符串集合。從概念上講，graph將一個(gè)字符串類(lèi)型的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是一個(gè)慣用方式，也就是說(shuō)在每個(gè)值首次作為key時(shí)才初始化。hasEdge函數(shù)顯示了如何讓map的零值也能正常工作；即使from到to的邊不存在，graph[from][to]依然可以返回一個(gè)有意義的結(jié)果。

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

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