map的实现原理

map是一个储存键值对的数据类型，其底层是哈希表，对map的读写操作是O(1)的时间复杂度。实现这样的数据类型需要注意两点——哈希函数和冲突解决方法。

哈希函数

哈希函数是：将任意长度的二进制值转换为固定长度的二进制值，常见的有MD5，取模等。

例子：当一个key为11的数存入map中，这个map的哈希函数为取模于5，这时10会存入编号为1的桶中，当再来一个key为6的数存入，取模后也是1，这时就发生冲突了，需要解决这个冲突。

冲突解决

常用的两种方式为开放寻址法和拉链法。

开放寻址法

开放寻址法的底层是一个一维数组，当我们执行取模后，找到对应的位置，当冲突发生后，通过一定的规律，在数组的后面挑选“空位”，用来放置新的 key。

拉链法

拉链法底层是一个数组加链表，每个数组就是一个 bucket，bucket是一个链表，落在同一个 bucket 中的 key 都会插入这个链表中。

Golang中的map

Golang 采用的是哈希查找表，并且使用拉链法解决哈希冲突。

在runtime下的map.go中可以找到这个结构体

type hmap struct {

	count     int 
	flags     uint8
	B         uint8  
	noverflow uint16 
	hash0     uint32 

	buckets    unsafe.Pointer 
	oldbuckets unsafe.Pointer 
	nevacuate  uintptr

	extra *mapextra 
}

type mapextra struct {
	overflow    *[]*bmap
	oldoverflow *[]*bmap
	nextOverflow *bmap
}

1. count 表示当前哈希表中的元素数量；
2. flags 代表当前 map 的状态（是否处于正在写入的状态等）
3. **B** 表示当前哈希表持有的 **buckets 数量，但是因为哈希表中桶的数量都 2 的倍数，所以该字段会存储对数，也就是 len(buckets) == 2^B；
4. **hash0** 是哈希的种子，它能为哈希函数的结果引入随机性，这个值在创建哈希表时确定，并在调用哈希函数时作为参数传入；
5. buckets 是指向当前 map 对应的桶的指针。
6. **oldbuckets** 是哈希在扩容时用于保存之前 buckets 的字段，它的大小是当前 **buckets** 的一半；
7. extra 存储 map 中的溢出桶。

桶的结构体 [bmap](<https://draveness.me/golang/tree/runtime.bmap>) 在 Go 语言源代码中的定义只包含一个简单的 tophash 字段，tophash 存储了键的哈希的高 8 位，通过比较不同键的哈希的高 8 位可以减少访问键值对次数以提高性能。

在编译时即确定了 map 中 key、value 及桶的大小，所以在运行时仅仅通过指针操作就可以找到特定位置的元素。编译期动态地创建一个新的结构：

type bmap struct {
    topbits  [8]uint8
    keys     [8]keytype
    values   [8]valuetype
    pad      uintptr
    overflow uintptr
}

下图是这几个结构体的关系：

访问过程

map的访问有两种方式，

  v := m[k]
	v , ok := m[k]

第一种返回指向目标值的指针，第二种返回目标值和这个目标值是否存在的bool值。他们的底层逻辑基本一致，只是第二种在第一种的基础上多返回了一个bool

访问时，会现通过哈希函数和种子获取当前键对应的哈希，然后通过运算得到当前键值对所对应的桶序列号和哈希高8位数字，拿到后去对应的桶和溢出桶中寻找，它会先比较哈希的高8位，和桶中储存的 tophash ，相等后再比较key是否相同，相同则返回。

赋值过程

m[k] = "value"

赋值时，程序会根据传入的key经过计算拿到对应的哈希和桶，然后通过遍历比较桶中储存的 tophash 和键的哈希，找到要赋值的位置（可能是插入新 key，也可能是更新老 key），对相应位置进行赋值。

扩容过程

插入key时会在一下两种情况发生扩容：

1. 装载因子超过6.5。
2. map使用的溢出桶太多。

等量扩容

扩容原因：溢出桶的数量太多导致。

等量扩容会创建一组数量相同的新桶和预创建的溢出桶，然后将原有的桶数组设置到 oldbuckets ，并将新桶设置到 buckets ，新建的溢出桶也是用同样的逻辑。经过渐进式转移，将老桶中的元素全部转移到新桶中后，老桶设置位nil。

等量扩容是为了解决大量写入，删除造成的内存泄露问题。

增量扩容

扩容原因：装载因子超过6.5。

Go 源码里这样定义 装载因子：loadFactor := count / (2^B)

count 就是 map 的元素个数，2^B 表示 bucket 数量。

增量扩容可等量扩容流程一样，只是它创建的新桶数量是老桶数量的2倍。

渐进式转移

插入或修改、删除 key 的时候，都会尝试进行搬迁 buckets 的工作。先检查 oldbuckets 是否为 nil。每次搬迁2个桶到新桶上，其中一个是key所在的桶，和一个另外的桶。这样扩容的好处是将扩容的复杂度均摊到每次操作，保证在map操作上耗时稳定，缺点是实现复杂。

删除过程

对map删除操作，调用 delete 关键字。

 	m := map[string]int{
		"1":1,
	}
	delete(m, "1")

删除逻辑和赋值过程一样，找到元素删除。当map再扩容期间，他会将数据转移后再进行删除。