Q
- 怎么平滑的扩容
冲突解决的2种方法
开放寻址法
open-addressing-and-get
开放寻址中对性能影响最大的计算装载因子。
随着装载因子的怎额更多，线性探测的时间就会逐渐增加。如果装载因子到1，那么查找和插入的复杂度都会退化到O(n)。
拉链法
separate-chaing-and-get
在一个性能比较好的哈希表中，每一个桶中都应该有01个元素，有时会有23个。再多性能就会比较差了。
名词
装载因子
它是数组中元素的数量与数组大小的比值。
并发写问题
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。并且每次修改之前都会做判断，如果不符合预期，则会报错。
如何避免
- 尽量少定义全局map变量
- 如果必须定义全局map变量，可以加锁
- 优化1.可以采用cow策略，read不加锁，每次修改copy修改，再赋值
- 优化2.可以采用分片锁，减小锁的粒度
- 使用
sync.Map
