[翻译]The Go Blog《Go maps in action》

Andrew Gerrand

6 February 2013



注：
译者：Jordy
时间：2020/01/13



Introduction （介绍）



One of the most useful data structures in computer science is the hash table. Many hash table implementations exist with varying properties, but in general they offer fast lookups, adds, and deletes. Go provides a built-in map type that implements a hash table.

翻译：
哈希表是计算机科学中最有用的数据结构之一。 
存在许多具有不同属性的哈希表实现，但通常它们提供快速查找，添加和删除。 
Go提供了实现哈希表的内置映射类型



Declaration and initialization （定义及初始化）



A Go map type looks like this:

Go 的map类型的定义如下所示：



map[KeyType]ValueType



where KeyType may be any type that is comparable (more on this later), and ValueType may be any type at all, including another map!

其中KeyType可以是任何 可比较 的类型（稍后会详细介绍），ValueType可能是任何类型，包括另一个映射！



This variable m is a map of string keys to int values:

定义变量m是一个key为string类型，值为int类型的map



var m map[string]int



Map types are reference types, like pointers or slices, and so the value of m above is nil; it doesn't point to an initialized map. A nil map behaves like an empty map when reading, but attempts to write to a nil map will cause a runtime panic; don't do that. To initialize a map, use the built in make function:

就如指针和切片一样，Map类型也属于引用类型（译者注：本质上就是指向内存中都某块区域），比如上述m的初始化值为nil（译者注：nil表示空指针）；m未指向任何初始化的map空间；

在读操作时，nil map的行为表现类似于读取到一个空的map，但是如果尝试在nil map中做写入操作，将会触发panic异常，所以不要在未初始化的map中写入元素；我们可以使用golang内置的make函数来初始化一个map结构，如：

m = make(map[string]int)



The make function allocates and initializes a hash map data structure and returns a map value that points to it. The specifics of that data structure are an implementation detail of the runtime and are not specified by the language itself. In this article we will focus on the use of maps, not their implementation.

make 函数的本质是在内存中申请并初始化来一个hash表结构，并返回一个指向该hash结构的指针。

译者注：核心源码如src/runtime/map.go，此处暂不做make 源码深入分析
// makemap_small implements Go map creation for make(map[k]v) and
// make(map[k]v, hint) when hint is known to be at most bucketCnt
// at compile time and the map needs to be allocated on the heap.
func makemap_small() *hmap {
    h := new(hmap)
    h.hash0 = fastrand()
    return h
}

Working with maps（map的使用）

Go provides a familiar syntax for working with maps. This statement sets the key "route" to the value 66:

针对如何使用map，Go为我们提供最为熟悉的语法。比如以下的语句中，我们给"route"的key赋值了一个整型的值"66"

m["route"] = 66



This statement retrieves the value stored under the key "route" and assigns it to a new variable i:

以下语句查找存在在m中的"route"的值，并将其赋值给一个新的变量i

i := m["route"]



If the requested key doesn't exist, we get the value type's zero value. In this case the value type is int, so the zero value is 0:

如果查找的key不存在，我们将得到其对应类型的0值（译者注：如string类型的0值则为空字符串""）

在下述的例子中，m的values类型是int，所以得到的int的0值为0

j := m["root"]
// j == 0



The built in len function returns on the number of items in a map:

内建函数len 返回map中元素的个数

n := len(m)

The built in delete function removes an entry from the map:

内建函数detele 可以将某个key元素从map中删除；

delete(m, "route")



The delete function doesn't return anything, and will do nothing if the specified key doesn't exist.

如果被删除的key不存在时，delete函数什么都不做。

A two-value assignment tests for the existence of a key:

我们可以用双返回值的方式来检测某个key是否存在于map中，如下：

i, ok := m["route"]



In this statement, the first value (i) is assigned the value stored under the key "route". If that key doesn't exist, i is the value type's zero value (0). The second value (ok) is a bool that is true if the key exists in the map, and false if not.

在此语句中，第一个值（i）被分配了存储在键``route''下的值。 如果该键不存在，则i是值类型的零值（0）。 第二个值（ok）是布尔值，如果键存在于映射中则为true，否则为false。

To test for a key without retrieving the value, use an underscore in place of the first value:

如仅仅是为了检测key是否存在，而不需要使用其值，用下划线忽略值（返回参数中第一个）即可；

_, ok := m["route"]

To iterate over the contents of a map, use the range keyword:

可以用range 关键字来遍历map

for key, value := range m {
    fmt.Println("Key:", key, "Value:", value)
}



To initialize a map with some data, use a map literal:

以下示例是以字面量map的方式来初始化一个map结构.

commits := map[string]int{
    "rsc": 3711,
    "r":   2138,
    "gri": 1908,
    "adg": 912,
}



The same syntax may be used to initialize an empty map, which is functionally identical to using the make function:

可以使用相同的语法来初始化一个空的映射，其功能与使用make函数相同：

m = map[string]int{}



Exploiting zero values （利用零值）

It can be convenient that a map retrieval yields a zero value when the key is not present.

For instance, a map of boolean values can be used as a set-like data structure (recall that the zero value for the boolean type is false). This example traverses a linked list of Nodes and prints their values. It uses a map of Node pointers to detect cycles in the list.



    type Node struct {
        Next  *Node
        Value interface{}
    }
    var first *Node
    visited := make(map[*Node]bool)
    for n := first; n != nil; n = n.Next {
        if visited[n] {
            fmt.Println("cycle detected")
            break
        }
        visited[n] = true
        fmt.Println(n.Value)
    }



The expression visited[n] is true if n has been visited, or false if n is not present. There's no need to use the two-value form to test for the presence of n in the map; the zero value default does it for us.



Another instance of helpful zero values is a map of slices. Appending to a nil slice just allocates a new slice, so it's a one-liner to append a value to a map of slices; there's no need to check if the key exists. In the following example, the slice people is populated with Person values. Each Person has a Name and a slice of Likes. The example creates a map to associate each like with a slice of people that like it.



    type Person struct {
        Name  string
        Likes []string
    }
    var people []*Person
    likes := make(map[string][]*Person)
    for _, p := range people {
        for _, l := range p.Likes {
            likes[l] = append(likes[l], p)
        }
    }



To print a list of people who like cheese:



    for _, p := range likes["cheese"] {
        fmt.Println(p.Name, "likes cheese.")
    }



To print the number of people who like bacon:



    fmt.Println(len(likes["bacon"]), "people like bacon.")



Note that since both range and len treat a nil slice as a zero-length slice, these last two examples will work even if nobody likes cheese or bacon (however unlikely that may be).



Key types （key的类型）

译者注：前面提到，map key的类型必须是可笔记的类型，这一点非常关键，hash表的结构决定了我们可以通过比较key来快速的定位和查找元素，具体见下述。



As mentioned earlier, map keys may be of any type that is comparable. The language spec defines this precisely, but in short, comparable types are boolean, numeric, string, pointer, channel, and interface types, and structs or arrays that contain only those types. Notably absent from the list are slices, maps, and functions; these types cannot be compared using ==, and may not be used as map keys.



It's obvious that strings, ints, and other basic types should be available as map keys, but perhaps unexpected are struct keys. Struct can be used to key data by multiple dimensions. For example, this map of maps could be used to tally web page hits by country:



hits := make(map[string]map[string]int)



This is map of string to (map of string to int). Each key of the outer map is the path to a web page with its own inner map. Each inner map key is a two-letter country code. This expression retrieves the number of times an Australian has loaded the documentation page:



n := hits["/doc/"]["au"]



Unfortunately, this approach becomes unwieldy when adding data, as for any given outer key you must check if the inner map exists, and create it if needed:



func add(m map[string]map[string]int, path, country string) {
    mm, ok := m[path]
    if !ok {
        mm = make(map[string]int)
        m[path] = mm
    }
    mm[country]++
}
add(hits, "/doc/", "au")



On the other hand, a design that uses a single map with a struct key does away with all that complexity:



type Key struct {
    Path, Country string
}
hits := make(map[Key]int)



When an Vietnamese person visits the home page, incrementing (and possibly creating) the appropriate counter is a one-liner:



hits[Key{"/", "vn"}]++



And it's similarly straightforward to see how many Swiss people have read the spec:



n := hits[Key{"/ref/spec", "ch"}]



Concurrency（并发）



Maps are not safe for concurrent use: it's not defined what happens when you read and write to them simultaneously. If you need to read from and write to a map from concurrently executing goroutines, the accesses must be mediated by some kind of synchronization mechanism. One common way to protect maps is with sync.RWMutex.



This statement declares a counter variable that is an anonymous struct containing a map and an embedded sync.RWMutex.



var counter = struct{
    sync.RWMutex
    m map[string]int
}{m: make(map[string]int)}



To read from the counter, take the read lock:



counter.RLock()
n := counter.m["some_key"]
counter.RUnlock()
fmt.Println("some_key:", n)



To write to the counter, take the write lock:



counter.Lock()
counter.m["some_key"]++
counter.Unlock()



Iteration order（迭代顺序）



When iterating over a map with a range loop, the iteration order is not specified and is not guaranteed to be the same from one iteration to the next. If you require a stable iteration order you must maintain a separate data structure that specifies that order. This example uses a separate sorted slice of keys to print a map[int]string in key order:



import "sort"
var m map[int]string
var keys []int
for k := range m {
    keys = append(keys, k)
}
sort.Ints(keys)
for _, k := range keys {
    fmt.Println("Key:", k, "Value:", m[k])
}