GO数据-字典（四）

字典（哈希表）是一种使用频率极高的数据结构。将其作为语言内置类型，从运行时层面进行优化，可获得更高效的性能。
作为无序键值对集合，字典要求key必须是支持相等运算符（== ，!=）的数据类型，比如。数字、字符串、指针、数组、结构体、以及对应接口类型。

使用make创建字典

func main() {
    m := make(map[string] int)
    m["a"] = 1
    m["b"] = 2
    fmt.Println(m)
}

使用初始化表达式语句来创建

func main() {
    m2 := map[int]struct {
        x int
    }{
        1: {x: 100},
        2: {x: 200},
    }
    fmt.Println(m2)
}

修改字典

func main() {
    m := map[string]int {
        "a": 1,
        "b": 2,
    }

    m["a"] = 10     //修改
    m["c"] = 30     //新增

    if v, ok := m["d"];ok {     //使用ok-idiom判断key是否存在，返回值
        println(v)
    }

    delete(m, "d")          //删除键值对。不存在时，不会报错
}

函数len返回当前键值对数量，cap不接受字典类型。另外，因内存访问安全和哈希算法等缘故，字典被设计成“not addressable”，故不能直接修改value成员 (结构或数组)。

func main() {
    type user struct {
        name string
        age int
    }

    m := map[int]user {
        1: {"Tom", 19},
    }

    m[1].age += 1 //编译报错cannot assign to struct field m[1].age in map
}

正确的做法是返回整个value，待修改后在设置字典键值，或直接用指针类型。

func main() {
    type user struct {
        name string
        age int
    }

    m := map[int]user {
        1: {"Tom", 19},
    }
    u := m[1]
    u.age += 1
    m[1] = u        //设置整个value

    m2 := map[int]*user {   //value是指针
        1: &user{"Jack", 20},
    }

    m2[1].age++     //m2[1]返回的是指针，可透过指针修改目标对象
    fmt.Println(*m2[1])
}

迭代字典

访问不存在的键值，默认返回零，不会引发错误。但推荐使用ok-idiom模式，毕竟通过零值无法判断键值是否存在，或许存储的value本就是零。

对字典进行迭代每次返回的键值次序都不相同

func main() {
    m := make(map[string]int)
    for i := 0; i< 8;i ++ {
        m[string('a'+i)] = i
    }

    for i := 0;i < 4;i ++ {
        for k,v := range m {
            print(k, ":", v, " ")
        }
        println()
    }
}

输出：

g:6 h:7 a:0 b:1 c:2 d:3 e:4 f:5 
a:0 b:1 c:2 d:3 e:4 f:5 g:6 h:7 
a:0 b:1 c:2 d:3 e:4 f:5 g:6 h:7 
c:2 d:3 e:4 f:5 g:6 h:7 a:0 b:1 

安全

在迭代期间删除或新增键值是安全的。

func main() {
    m := make(map[int]int)

    for i := 0; i< 10; i++ {
        m[i] = i + 10
    }

    for k := range m {
        if k == 5 {
            m[100] = 100
        }
        delete(m, k)
        fmt.Println(k, m)
    }
}

输出：

1 map[0:10 2:12 3:13 4:14 5:15 6:16 7:17 8:18 9:19]
3 map[0:10 2:12 4:14 5:15 6:16 7:17 8:18 9:19]
4 map[0:10 2:12 5:15 6:16 7:17 8:18 9:19]
5 map[0:10 2:12 6:16 7:17 8:18 9:19 100:100]
6 map[0:10 2:12 7:17 8:18 9:19 100:100]
9 map[0:10 2:12 7:17 8:18 100:100]
0 map[2:12 7:17 8:18 100:100]
2 map[7:17 8:18 100:100]
7 map[8:18 100:100]
8 map[100:100]
100 map[]

运行时会字典并发操作作出检测。如果某个任务正在对字典进行写操作，那么其他任务就不能对该字典执行并发操作（读、写、删除），否则会导致进程崩溃。

func main() {
    m := make(map[string]int)

    go func() {
        for {
            m["a"] += 1         //写操作
            time.Sleep(time.Microsecond)
        }
    }()

    go func() {
        for {
            _ = m["b"]          //读操作
            time.Sleep(time.Microsecond)
        }
    }()

    select{}  //阻止进程退出
}

输出

fatal error: concurrent map read and map write

可是使用sync.RWMutex读写锁实现同步，避免读写操作同时进行。

func main() {
    var lock sync.RWMutex       //使用读写锁
    m := make(map[string]int)

    go func() {
        for {
            lock.Lock()         //注意锁的粒度
            m["a"] += 1         //写操作
            lock.Unlock()       //不能使用defer
            time.Sleep(time.Microsecond)
        }
    }()

    go func() {
        for {
            lock.RLock()
            _ = m["b"]          //读操作
            lock.RUnlock()
            time.Sleep(time.Microsecond)
        }
    }()

    select{}  //阻止进程退出
}

性能

字典对象本身就是指针包装，传参时无须再次取地址。

func test(x map[string]int)  {
    fmt.Printf("x: %p\n", x)
}

func main() {
    m := make(map[string]int)
    test(m)
    fmt.Printf("m: %p, %d\n", m, unsafe.Sizeof(m))

    m2 := map[string]int{}
    test(m2)
    fmt.Printf("m: %p, %d\n", m2, unsafe.Sizeof(m2))
}

输出：

x: 0xc000070180
m: 0xc000070180, 8
x: 0xc000096000
m: 0xc000096000, 8

在创建是预先准备足够空间有助于提升性能，减少扩张时内存分配和重新哈希操作。
使用基准测试：

func test() map[int]int {
    m := make(map[int]int)
    for i := 0; i < 1000; i++ {
        m[i] = i
    }
    return m
}

func testCap() map[int]int {
    m := make(map[int]int, 1000)  //预先准备充足的空间
    for i := 0; i < 1000; i++ {
        m[i] = i
    }
    return m
}

//基准测试 是测量一个程序在固定工作负载下的性能
func BenchmarkTest(b *testing.B) {
    for i := 0; i < b.N; i++ {
        test()
    }
}

func BenchmarkTestCap(b *testing.B) {
    for i := 0; i < b.N; i++ {
        testCap()
    }
}

输出：

//BenchmarkTest
goos: darwin
goarch: amd64
pkg: hello/models
BenchmarkTest-12           20000         68202 ns/op
PASS
//BenchmarkTestCap
goos: darwin
goarch: amd64
pkg: hello/models
BenchmarkTestCap-12        50000         27326 ns/op
PASS

对于海量小对象，应直接用字典存储键值数据拷贝，而非指针。这有助于减少需要扫描的对象数量，大概缩短垃圾回收时间。另外，字典不会收缩内存，所以适当替换成新对象是必要的。