map基本操作

map初始化

// 直接定义
var m map[int]string
m[1]="hello"  // 未对map进行初始化操作，值为nil，会报panic。但是可以进行访问

// 使用make初始化
var m = make(map[int]string, 2) // 第二个参数代表map的长度，为空时，默认为0

// 使用字面量初始化
var country = map[string]string{
    "China": "Beijing"
    "Japan": "Tokyo"
}

map访问

v := map[key]       // 可以只接收值
v, ok := map[key]   // 也可以用第二个参数判断key是否存在

map修改

m[key] = value
delete(m, key)   // 删除m中的key，可以对相同的key进行多次删除操作而不会报错

map底层原理

底层结构

map中的数据被存放于一个数组中的，数组的元素是桶（bucket），每个桶至多包含8个键值对数据。哈希值低位（low-order bits）用于选择桶，哈希值高位（high-order bits）用于在一个独立的桶中区别出键。哈希值高低位示意图如下

go语言map的底层结构如下：（runtime/map.go）

type hmap struct {
	count     int    // map中元素的数量
	flags     uint8  // 当前map的状态（是否处于正在写入的状态）
	B         uint8  // 2^B表示当前map中桶的数量 2^B = Buckets Size
	noverflow uint16 // 溢出桶的数量，当溢出桶太多时，map会进行same-size map growth,避免溢出桶过大导致内存泄漏
	hash0     uint32 // hash seed 生成hash的随机数种子
	buckets    unsafe.Pointer // 当前map对应的桶的指针
	oldbuckets unsafe.Pointer // 扩容时存储的旧桶，当旧桶数据都转移到新桶中时，则清空
	nevacuate  uintptr        // 扩容时，标记当期旧桶中小于nevacuate的数据都已转移到了新桶中  
	extra *mapextra           // 存储map中的溢出桶
}

代表桶的bmap结构只列出了首个字段，既一个固定长度为8的数组。此字段顺序存储key的哈希值的前8位

type bmap struct {
	tophash [bucketCnt]uint8   // bucketCnt = 8
}

// map在编译时既确定了map中key、value及桶的大小，因此在运行时仅仅通过指针操作就可以找到特定位置的元素
type bmap struct {
	tophash [bucketCnt]uint8
    key [bucketCnt]T
    value [bucketCnt]T
    ...
}

go选择将key与value分开存储是为了在字节对齐时压缩空间。

溢出桶

在执行hash[key] = value赋值操作时，当指定桶中的数据超过8个，并不会直接开辟一个新桶，而是将数据放置到溢出桶中，每个桶的最后都存储了overflow，即溢出桶的指针。

在上面的hmap中的extra字段保存了溢出桶的指针，溢出桶的结构如下：

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

初始化

如果指定了map的长度N，则在初始化时会生成桶，桶的数量为$\log_2{N}$。如果map的长度大于24，则会在初始化时生成溢出桶，溢出桶的大小为$2^{(b-4)}$，其中b为桶的大小。

赋值

计算key的hash值，标志当前是写入状态
如果没有桶，则会创建一个新桶，接着找到当前key对应的桶
如果发现当前map正在重建，会优先完成重建过程
计算tophash，开始寻找桶中是否有对应的hash值，如果找到并且key相同，在对应的value位置赋值
如果桶里没有位置，就去使用溢出桶，这些多余的溢出桶都用完才会申请新的桶
溢出桶以链表的形式进行延展

并发

map只支持并发读，不支持并发读写

并发读写会报错：fatal error: concurrent map read and map write.

每个map有一个flag标识位，如果正在执行写入操作，当前的map的hashWriting标志位会被设置为1，因此在访问时通过检测hashWriting即可知道是否有其他协程正在访问此map，如果是则报错。

访问

先找到桶的位置，如下伪代码

hash = hashfunc(key)         // 通过hash函数计算key的hash值
index = hash % array_size    // 对桶的数量取模

找到桶的位置后，遍历tophash数组，如果在数组中找到了相同的hash，接着通过指针的寻址操作找到对应的key、value

删除

和赋值操作类似，先根据key找到指定的桶，如果存在指定的key，就释放掉key与value的引用的内存。同时tophash中的指定位置会存储emptyOne，代表当前位置是空的
同时删除操作会探测当前要删除的元素之后是否都是空的，如果是，则tophash会存储为emptyRest。这样在查找时遇到emptyRest直接退出，不用再往后查了

重建

1. map超过了负载因子大小

负载因子 = 哈希表中的元素数量 / 桶的数量。go中的负载因子为6.5，当超过其大小后，map会进行双倍重建，旧桶的数据会存储到oldbuckets字段中，溢出桶也会进行同样的转移。
数据转移遵循写时复制(copy on write)的规则，只有真正赋值时才会选择需要是否转移。
再进行写时复制时，只转移当前需要的旧桶中的数据
双倍重建过程中，两个新桶的距离值总是与旧桶的数量相等
旧桶的数据全部转移到新桶后，旧桶的数据会被清空

2. 溢出桶的数量过多

这时map只会新建和原来大小相同的桶（等量重建），目的时防止溢出桶的数量缓慢增长导致内存泄漏。同样也是使用写时复制规则。

哈希碰撞与解决办法

拉链法：
将同一个桶中的元素通过链表的形式进行链接，是一种最简单最常用的策略。不足之处是需要额外的指针用于链接元素，增加了哈希表的大小，同时由于链表的存储地址不连续，无法高效利用CPU高速缓存。

拉链法对装载因子的容忍度会更高，并且适合存储大对象、大数据量的哈希表。而且相较于开放寻址法，它更加灵活，支持更多的优化策略，比如可采用红黑树代替链表。但是拉链法需要额外的空间来存储指针。
开放寻址法：

所有元素都存储在桶的数组中，当必须插入新条目时，按照某种探测策略操作，直到找到未使用的数组插槽为止。当搜索元素时，按照相同顺序扫描存储桶，直到查找到目标记录或找到未使用的插槽为止。

但是它对内存的利用率不如链地址法，且发生冲突时代价更高。当数据量明确、装载因子小，适合采用开放寻址法。

Go语言中的哈希表采用了优化的拉链法，每一个桶中存储了8个元素用于加速访问

参考

[1] 深入理解golang中的map
[2] 《go语言底层原理剖析》