Go语言核心之美 3.3-Map

erlib · · 1625 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

哈希表是一种非常好用、适用面很广的数据结构,是key-value对的无序集合。它的key是唯一的,通过key可以在常数复杂度时间内进行查询、更新或删除,无论哈希表有多大。

Go语言的map类型就是对哈希表的引用,表示为map[key]value。map中所有的key都是相同的类型,所有的value也是相同的类型,不过key和value可以是不同的类型。key代表的数据类型必须支持==和!=运算符,这样map才能检测指定的key是否已经存在。虽然浮点数支持相等运算符,但是正如我们在第二章提到的,浮点数是不精确的,因此用它做key,不是个好想法,甚至最坏的情况可能发生用NaN来进行比较。value的数据类型是没有限制的。

使用内置函数make创建map:

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

也可以使用类似slice语法来创建map:

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

这相当于:

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

可以通过map[string]int{}来创建空map。

Map中的元素可以通过key来访问:

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

使用内置的delete函数可以删除元素:

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

上面的所有操作都是安全的,不用担心报错,即使map中不存在相应的元素!查询失败时将返回value类型对应的零值,例如,虽然map中并不存在"bob",但是下面的代码仍然可以正常工作,因为ages["bob"]会返回0:

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

x += y和 x++ 等短赋值语法也可以用在map上:

ages["bob"] += 1

更简洁的版本:

ages["bob"]++

有一点很重要:map中的元素不是变量,因此不能寻址!!

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

不能寻址的原因是:map可能会随着元素的增多重新分配更大的内存空间,旧值都会拷贝到新的内存空间,因此之前的地址就会失效。

可以使用for...range来遍历map中的所有key-value对,这个类似slice的遍历语法,下面的代码中map的key是name,map的value是age:

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

Map的迭代顺序是不确定的,而且不同的哈希算法会导致不同的迭代顺序。在实际应用中,遍历的顺序是随机的,甚至每次的遍历顺序可能都不相同。Go语言是有意这么实现的,使用随机的遍历顺序可以避免程序依赖于某种哈希实现,让程序更加强壮。如果要按顺序遍历,必须显式对key排序,可以使用sort包的String函数:

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

我们可以获取map中key的数目,因此可以提前给slice分配一个合适的大小,避免内存分配和拷贝。下面的代码创建了一个空的slice,容量刚好可以放下map中所有的key:

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

在上面的第一个range循环中,我们只关心具体的key,所以忽略了第二个变量。在第二个循环中,我们只关心value,所以使用'_'空白标识符来忽略第一个变量。

map是引用类型,对应的零值是nil,这时表示map没有引用任何哈希表。

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

map中的大部分操作:查询、删除、len和range都可以安全地工作在nil map上,nil map的行为和空map类似。但是,向nil map中添加元素时将导致panic:

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

因此,向map中添加数据前,必须先初始化map。

对map的查询总是会成功的。如果key在map中存在,那么获取相应的value;如果key不存在,获取对应value类型的零值,正如之前的ages["bob"]。在一些情况下,这样的机制是没问题的,但是有时候我们需要知道要查询的元素是否真的存在,例如value是int类型时,查询的返回值0就很令人迷惑,到底是value的值就是0呢还是key不存在返回的零值。可以使用下面的方法:

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

也可以结合起来使用:

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

上面的场景下,map的访问产生了两个值,第一个值是value,第二个值是个布尔值,用于报告元素是否存在。布尔变量一般声明为ok,这样在if中使用时意义会非常明确。

和slice一样,map之间也不能进行相等比较,唯一的例外是和nil比较。如果要判断两个map是否相等,我们必须自己实现:

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来判断y中的元素是否存在,不能简单的用xv != y[k]来判断,不然可能会导致错误的结果:

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

Go语言没有set类型,不过我们可以使用map来实现set,利用map中的key是唯一的这个特性。debup程序会读取多行输入,然后打印出第一次出现的行,这里使用map来做所有输入行的集合,确保已经存在的行不会被重复打印:

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程序员经常利用上面这种编程范式来实现集合。

有的时候我们需要key为slice类型的map,但是因为map的key必须是可比较的,因此slice并不满足条件。不过可以通过映射来解决,首先,定义一个辅助函数k,将slice映射为字符串,确保只有x和y相等时,k(x) == k(y);其次,使用slice时,将slice转换为字符串,再作为map的key使用。

下面的例子中,使用map来记录Add函数的调用次数,这里使用了fmt.Sprintf将字符串列表转换为一个字符串,然后用于map的key,使用%q参数可以给输出的字符串加上双引号:

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

使用类似的思想可以处理任何不可比较的key类型,不仅仅是slice。对于可比较的类型,也可以使用上面的思想来实现自定义的比较函数,例如比较字符串时忽略大小写,而不是直接用==比较。同时,k(x)也未必要返回字符串类型,可以返回任何可比较的类型,例如整形、浮点、结构体等。

再看另外一个例子,统计输入中每个Unicode码点出现的次数。虽然Unicode的全部码点(int32)数量巨大,但是实际世界中已使用的码点值并不多,因此这里可以使用map来追踪码点的个数:

// 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会执行UTF-8解码并返回三个值:解码后的rune值、rune经过UTF-8编码后的字节长度以及一个错误值,文件的结尾io.EOF是我们唯一预期的错误值。如果输入不是合法的UTF-8编码字符,那么返回的将是unicode.ReplacementChar字符,且编码长度为1。

charcount还会统计各个UTF-8编码长度对应的字符数目,对此,map并不合适,因为UTF-8编码的长度只有1、2、3、4 四种情况,因此更适合使用数组(数组在内存中是连续排列的,读取性能高很多)。

作为一个实验,我们可以使用charcount程序对本书的英文版进行统计(gopl.io)。虽然书中大部分是英文字符,但是也有一些非ASCII字符。下面是排名前10的非ASCII字符:

下面是不同UTF-8编码长度对应的字符数目:

len count
1   765391
2   60
3   70
4   0

map的value也可以是聚合类型,例如map或slice。在下面的代码中,graph的key是字符串类型,value的类型是map[string]bool,代表一个字符串集合。这里,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展现了一个理想的惰性初始化map的方式,也就是只在key第一次出现时才初始化value的值。函数还展示了如何让map的零值也能正常工作:即使from到to的边不存在,graph[from][to]依然可以返回一个有意义的结果。


练习 4.8: 修改charcount程序,使用unicode.IsLetter等函数,统计字母、数字等不同类别字符出现的个数。

练习 4.9: 编写wordfreq程序,统计输入文本中每个单词出现的频率,在第一次调用Scan前先调用input.Split(bufio.ScanWords)函数,把输入按自此分割而不是按行分割。


文章所有权:Golang隐修会 联系人:孙飞,CTO@188.com!


有疑问加站长微信联系(非本文作者)

本文来自:CSDN博客

感谢作者:erlib

查看原文:Go语言核心之美 3.3-Map

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

1625 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传