简单易懂，解析Go语言中的Map

3. map

3.1 初始化

• var/new声明nil map;make初始化map同时可以指定容量;字面量;
• 向nil map中插入会报panic

func main() {
	var m1 map[int]int 		//panic: assignment to entry in nil map
	m2 := *new(map[int]int)	// panic: assignment to entry in nil map
	m3 := make(map[int]int,10)
	m4 := map[int]int{}
	m1[1] = 2
	m2[1] = 3
	m3[1] = 4
	m4[1] = 5
}

3.2 增删改查

基础增删改查如下

func main() {
	m4 := map[int]int{}
	m4[1] = 10			//增
	m4[1] = 20			//改
	delete(m4, 1)	    //删
	v, exist := m4[1]	//查
	if exist {
		fmt.Println(v)
	}
}

• 若修改的时候，键不存在，则会新增
• 可以对不存在的键进行删除，不会报错
• 查询的时候，如果键不存在，返回：(零值,false)

func main() {
	m4 := map[int]int{}
	m4[2] = 20              //修改没有的键就是新增
	delete(m4, 0)		    //没有key：0的键也不会报错
	v, exist := m4[1]
	fmt.Println(v, exist)	//0 false
}

• map并不是线程安全的，并发读写会触发panic

func main() {
	m4 := map[int]int{}
	go func() {
		for {
			m4[0] = 10
		}
	}()
	go func() {
		for {
			a, b := m4[0]   //fatal error: concurrent map read and map write
			fmt.Println(a, b) // 通常情况下应该是 0 false 但偶尔能在写的空窗期读到 10 true
		}
	}()
	go func() {
		for {
			m4[1] = 10      //fatal error: concurrent map writes
		}
	}()
	time.Sleep(2 * time.Second)
}

3.3 源码

• 源码中的B，只影响buckets数组的长度，也就是bucket的个数，跟bucket内部能装多少个键值对无关

//map的数据结构
type hmap struct {
	count     int               // 元素个数
	B         uint8             // buckets数组大小
	buckets    unsafe.Pointer   // bucket数组，长度为2^b
	oldbuckets unsafe.Pointer   // 旧bucket数组，用于扩容
	...
}

在bucket内的k-v超过8个时，会在创建一个新bucket，由overflow指向它 [扩容]

//bucket的数据结构
type bmap struct {
    tophash [bucketCnt]uint8    //存储Hash值得高8位
    data []byte                 //k-v数据，先存完k，再存v
    overflow uint8              //溢出bucket的位置
}

为什么要存Hash值的高8位？啥叫高8位，Hash低位在干什么？

打个比方，如果一个键k的hash值为113，我们一般会先对113%16(bucket数) = 1。好的，此时这个k就会被放入到buckets[1]中，也就是1号bucket

但是程序取模太慢了，为了加快运算速度，要是能把取模操作换成位运算就快多了

诶，在对2的N次方求余的时候，还真能够转化成位操作

eg：11%4 转化成二进制就是 1011 ;4 =2^2 ;将1011向左移动两位，得到10 就是2 也就是商 ，11 就是3 也就是余数

也就是说，如果一个数除以2的N次方求余，那么我们就是要得到最后这个数最后N位二进制的值

也就是 hash&(2^b-1)

通过上述公式得到的就是低位hash，也就是余数，用来确定桶。

但是这样只要低位相同，高位不同也在一个桶里，如11001111与11111111 低位都是1111，无法区别，此时就用到高位tophash来确定具体在桶中的位置了。

在Java中，为了增加散列程度，减少hash冲突，让bucket中的数据分布更加均匀，HashMap将高16位与低16位做异或运算，来确保每一位hash都参与到了桶运算中来

Go采取的是在hash函数中引入随机种子，来减少hash冲突，并使用高位来定位元素，也算是利用上了每一位hash

PS：为什么用异或？因为异或可以保证两个数值的特性,"&“运算使得结果向0靠近，”|"运算使得结果向1靠近

3.4 负载因子

负载因子 = k数/bucket数  //也就是计算出平均每个bucket包含多少k-v对

负载因子过低过高都不好，当负载因子大于6.5时，会进行rehash，增加桶数量并将这些hash均匀分布到其中

每个hash表对负载因子容忍能力不同，redis只能容忍负载因子为1（因为每个bucket只能存储1个k-v对）

3.5 扩容

触发扩容的两个条件，满足任一即可：

• 负载因子大于6.5
• overflow数量达到2^min(15,B) —— 溢出桶过多

扩容都是成倍数扩容，因为扩容本质上是B+=1;渐进式扩容，每次操作map的时候将2个bucket中的数据转移到新buckets中

扩容分为增量扩容和等量扩容：

• 增量：桶不够用了，加桶
• 等量：溢出桶太多了，有的都空了，重新排一下，减少一下溢出桶

如果处于扩容过程中，新增操作会直接在新buckets中进行， 但仍从oldbuckets开始寻找