Q

1. 怎么平滑的扩容

冲突解决的2种方法

开放寻址法

open-addressing-and-get

开放寻址中对性能影响最大的计算装载因子。

随着装载因子的怎额更多，线性探测的时间就会逐渐增加。如果装载因子到1，那么查找和插入的复杂度都会退化到O(n)。

拉链法

separate-chaing-and-get

在一个性能比较好的哈希表中，每一个桶中都应该有0_{1个元素，有时会有2}3个。再多性能就会比较差了。

名词

装载因子

它是数组中元素的数量与数组大小的比值。

并发写问题

fatal error: concurrent map writes

问题出现的原因

go中的map不是并发安全的，所以当多个goroutine同时对map执行写操作的时候，就会报刚刚的错误。

示例代码

package main

import (
    "math/rand"
    "time"
)

func init() {
    rand.Seed(time.Now().UnixNano())
}

func main() {
    ConcurrentWrite()
}

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

    f := func() {
        k, v := rand.Int()%50, rand.Int()%1000
        m[k] = v
    }
    for i := 0; i < 10; i++ {
        go f()
    }
    time.Sleep(time.Second * 5)
}

上面代码里，我们启动了10个协程对同一个map执行写操作，强制触发并发写。

运行结果

fatal error: concurrent map writes
fatal error: concurrent map writes

go是如何检测到对map的并发写的

那么我们知道发生的原因之后，追本溯源，我们一起来看下go是如果检测到并进行报错的

首先对map的写在源码上映射为 mapassign函数

// Like mapaccess, but allocates a slot for the key if it is not present in the map.
func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer{
 ...
}

因为在这个函数里面执行写操作，那么panic也是在这里报出来的了。

我们忽略到无关的代码，先force在 concurrent map writes 报错。我们发现有如下代码

...
if h.flags&hashWriting != 0 { // h是指向map,
        throw("concurrent map writes")
}
...
// Set hashWriting after calling t.hasher, since t.hasher may panic,
// in which case we have not actually done a write.
h.flags ^= hashWriting // 位操作，把hasWriting 标志位记为1
...
// do wirte things
...
if h.flags&hashWriting == 0 {
  throw("concurrent map writes")
}
h.flags &^= hashWriting // 清空标志位

可以看到，go是通过标志位实现的。在写之前，先吧标志位置为1，写之后，改为0。并且每次修改之前都会做判断，如果不符合预期，则会报错。

如何避免

1. 尽量少定义全局map变量
2. 如果必须定义全局map变量，可以加锁
   1. 优化1.可以采用cow策略，read不加锁，每次修改copy修改，再赋值
   2. 优化2.可以采用分片锁，减小锁的粒度
3. 使用sync.Map