1. 版权

按https://golang.org/doc/copyright.html, 原文内容使用 Creative Commons Attribution 3.0 License, 代码使用 BSD license.

使用原文之外的部分, 需注明出处: https://blog.csdn.net/big_cheng/article/details/107987424.

2. 原文

Go maps in action
Andrew Gerrand
6 February 2013

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.

Declaration and initialization

A Go map type looks like this:

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!

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

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:

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.

Working with maps

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

m[“route”] = 66
This statement retrieves the value stored under the key “route” and assigns it to a new variable 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:

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

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

n := len(m)

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

delete(m, "route")

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

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

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.

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

_, ok := m["route"]

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

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

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

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:

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

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

3. 笔记

// var m: nil. 可读不可写.
var m map[string]int
println(m == nil, len(m), m[“x”]) // true 0 0
// m[“x”] = 123 // panic: assignment to entry in nil map
for k, v := range m { println(k, v) } // 不报错, 未循环

var 申明的map 像empty map 但实际未初始化.
m := make(map[string]int) 初始化了, 返回对象 (非地址).

m[“root”] 如果不存在该项, 返回map 值类型的零值 (int => 0).
i, ok := m[“route”] - ok=该项存在否(不存在时i 是零值).
//
m := make(map[string]interface{})
m[“k1”] = “v1”
m[“k2”] = nil // 可设nil值
fmt.Printf("%v\n", m) // map[k1:v1 k2:<nil>]

make(map[string]int, 100) - 指示该map初始要能容纳100个元素(len仍=0).

Composite literal:
====
m := map[string]int{“k1”: 1, “k2”: 2} (返回对象).
//
type Point struct {x, y float64}
map[string]Point{“orig”: Point{0, 0}}
或省略为: map[string]Point{“orig”: {0, 0}}
//
m := map[string]*Point{“orig”: &Point{0, 0}}
或省略为: m := map[string]*Point{“orig”: {0, 0}}
fmt.Printf("%v", m[“orig”]) // &{0 0}

读不存在的项时返回零值的用途如:
visited := make(map[string]bool); visited[“not-visited”] 为false.
//
利用append nil slice时会新建一个slice:
visitedRooms := make(map[string][]int)
visitedRooms[“newGuest”] = append(visitedRooms[“newGuest”], 1)
fmt.Printf("%v", visitedRooms) // map[newGuest:[1]]

Map key要是可比较类型, 如string和bool|number|pointer|channel|interface、以及只包含这些类型的struct/array. 不能是slice/map/function.
//
如有个两层map 记录各页面各国家访问的次数:
hits := make(map[string]map[string]int) // 页面 => (国家=>次数)
添加一项时需做两层处理不方便, 改用struct key:
type Key struct {Page, Country string}
hits := make(map[Key]int)
hits[Key{"/doc", “cn”}]++
print(hits[Key{"/doc", “cn”}]) // 1

Go map 并发不安全. 可增加sync.RWMutex 做并发控制(见文内), 或改用sync.Map. 2种典型场景下可使用sync.Map, 见其godoc.

Range遍历map时 顺序不固定.

注: map对象内部实际仍会使用指针, 但这是runtime具体实现细节. 传递map时 传对象和传地址 都可以修改其内容, 区别不大.

赋值

将一个map赋值给另一个map, 会发生什么?

m1, m2 := map[string]int{}, map[string]int{"k2": 2}
m1 = m2
fmt.Printf("m1=%v\n", m1) // m1=map[k2:2]
m2["k2"] = 22
fmt.Printf("m1=%v\n", m1) // m1=map[k2:22]
m1["k2"] = 222
fmt.Printf("m2=%v\n", m2) // m2=map[k2:222]

由上可推测, 赋值实际是在内部指向同一块内存.

改用 *指针 赋值:

m1 := new(map[string]int)
m2 := &map[string]int{"k2": 2}
*m1 = *m2
fmt.Printf("m1=%v\n", *m1) // m1=map[k2:2]
(*m2)["k2"] = 22
fmt.Printf("m1=%v\n", *m1) // m1=map[k2:22]
(*m1)["k2"] = 222
fmt.Printf("m2=%v\n", *m2) // m2=map[k2:222]

可见 *map1指针 = *map2指针, 即 map1 = map2.

如果m1 指向m2 后, 扩张m2 超出其原定容量(capacity), 此时runtime 应该给m2 重新申请一块内部存储区, 那m1 会自动指向新的内存吗?

m1, m2 := make(map[int]int, 10), make(map[int]int, 10)
m2[2] = 2
m1 = m2
fmt.Printf("m1=%v\n", m1)   // m1=map[2:2]
for i := 0; i < 1000; i++ { // grow m2
    m2[i] = i
}
println(len(m1), len(m2)) // 1000 1000

由上可知, m1 始终指向m2 当前的内存区, 没有意外.

多层map的赋值测试:

m1 := map[string]map[string]int{"k1": {"sub1": 1}}
m2 := map[string]map[string]int{"k2": {"sub2": 2}}
m1["k1"] = m2["k2"]
fmt.Printf("m1=%v\n", m1) // m1=map[k1:map[sub2:2]]
m1["k1"]["sub2"] = 1
fmt.Printf("m2=%v\n", m2) // m2=map[k2:map[sub2:1]]

验证了m1[“k1”]=m2[“k2”]后, m1.k1 指向m2.k2.

传递map指针修改map自己, 如:

func main() {
	m1, m2 := map[string]int{"k1": 1}, map[string]int{"k2": 2}
	fmt.Printf("m1=%v, m2=%v\n", m1, m2) // m1=map[k1:1], m2=map[k2:2]
	swap(&m1, &m2)
	fmt.Printf("m1=%v, m2=%v\n", m1, m2) // m1=map[k2:2], m2=map[k1:1]
}

func swap(p1 *map[string]int, p2 *map[string]int) {
	m := *p1  // m指向p1的内存
	*p1 = *p2 // p1指向p2的内存
	*p2 = m   // p2指向原p1(即m)的内存
}

补充: map间不可使用==比较. 2个map即使地址不同, 其内部仍可以指向同一块内存.