map
一、简略构造
map 类型的变量实质上是一个 hmap 类型的指针，键值对通过哈希表来贮存。如下图：
二、哈希表的设计
1、构造
hash 表首先有一段贮存贮存数据的间断空间，咱们将数据存到这段间断的空间（能够把它当组成一个数组）外面，如下图所示，把 key、value 以及 key 的 hash 值存到间断的空间外面
2、寻址
而后就是以后的 key-value 具体要存到哪一个地位呢？当初支流的通常有两种办法：
1、取模运算：hash % m
2、位运算：hash&(m-1)
咱们都晓得位运算必定是更加的高效，然而必须得限度 m 为 2 的整数幂。golang 外面采纳了幂运算的办法来寻址
3、hash 抵触
当咱们两个 key 产生 hash 抵触了怎么解决呢？咱们也介绍两种的办法
1、拉链法：这种办法会把产生 hash 抵触的 key-value 数据用链表的形式把数据组织起来。如下图所示，当产生 hash 抵触的时候，前面插入的数据会链接到发生冲突的数据前面
2、凋谢地址法：比方下图，咱们编号 0 的地位曾经被占了，那么咱们就把数据放在编号 1 的地位，如果编号 1 的地位也被占了，由此类推，咱们持续寻址，直到找到闲暇的中央。
当咱们去查找数据的时候，咱们先会查找 0 地位，如果不是咱们查找的 key，会持续向下查找，晓得查找到最初的地位，很显然，这种办法不适宜负载因子（前面会介绍）过大的状况
下面两种办法比照：拉链法 绝对于查找数据比拟敌对，查找的次数不会太多。凋谢地址法 则不会产生不间断的内存空间，每次申请的都是一块间断的内存空间。在 golang 中，采纳了相似于拉链法，为什么说相似呢？前面会详细分析一下 map 的数据结构。
4、扩容
当咱们的数据曾经远远超过 8 个，采纳拉链法，那么 hash 表就会进化成链表。开发地址法就更不行了。这时候咱们就会波及到扩容的问题。扩容咱们次要搞清楚两个问题就行了：何时扩容、怎么扩容
何时扩容
还记得咱们上文提到的负载因子吗？负载因子就是来标识何时扩容的一个参数。它是哈希表中存储的键值对数量和桶数量的比值，通常须要设定一个触发扩容的最大负载因子
loadFactor = keyCount / bucketCount
咱们假如咱们的负载因子是 50%, 当咱们来了一个新的 key12 的时候，就会触发扩容
怎么扩容
咱们间接的想法是，当达到负载因子的时候，间接把 buckets 的容量翻倍。而后把数据都 copy 到新的地址空间去。如下所示
这么迁徙会有个问题。当旧桶的数据十分多的时候呢？这时候迁徙数据就会占用大量工夫，影响咱们主程序。所以简直在所有的语言中，都会采纳 渐进式扩容。
这种形式下，旧桶里的键值对是分屡次挪到新桶里的，能够在触发扩容后，先调配新桶，而后标记以后哈希表正在扩容，并在哈希表的读写操作中判断若在扩容中，则迁徙一部分键值对到新桶里，这样能够把扩容耗费的工夫扩散到屡次操作中。
好了，下面咱们大略介绍了 hash 表的一些个性和问题，接下来咱们再介绍一下 golang 中的 map 长什么样子。
三、map 的数据结构
图解构造
map 底层的哈希表通过 与运算 的形式抉择桶，所以 hmap 中并不间接记录桶的个数，而是记录这个数目是 2 的多少次幂。上面咱们先看看 map 应用的桶长什么样子。咱们先看看之前的 map 根本结构图，晓得 golang 中一个桶其实就是一个 bmap。
下图是一个 bmap 的数据结构。咱们能够看到 bmap 其实是一段间断内存空间。
为了内存应用更加紧凑，8 个键放一起，8 个值放一起。对应每个 key 只保留其哈希值的高 8 位（tophash）。而每个键值对的 tophash、key 和 value 的索引程序一一对应。
能够看到这个其实和咱们下面说的拉链法比拟类似，如果产生 hash 抵触的时候，会在 bmap 中向后写入，这样既保证了查找次数较少，又能保障内存比拟间断。
8 个存满了怎么办？为了缩小扩容次数，这里引入了溢出桶 (overflow)。溢出桶的内存布局与惯例桶雷同。如果哈希表要调配的桶的数目大于 2^4，就会预调配 2^(B-4) 个溢出桶备用。这些惯例桶和溢出桶在内存中是间断的，只是前 2^B 个用作惯例桶，前面的用作溢出桶。
源码剖析
上面咱们具体来看看源码：
type hmap struct {
count int //map 中值的数量
flags uint8 // 动作标识（比方正在写数据）B uint8 // 惯例桶个数等于 2^B
noverflow uint16 // 溢出桶数量
hash0 uint32 // hash 种子
buckets unsafe.Pointer // 桶的指针，指向的是 2^B 个 bmap
oldbuckets unsafe.Pointer // 旧桶的指针（扩容时应用）nevacuate uintptr // 扩容时迁徙的地位
extra *mapextra // 所有溢出桶指针
}
type mapextra struct {overflow *[]*bmap // 曾经用到的溢出桶
oldoverflow *[]*bmap // 渐进式扩容时，保留旧桶用到的溢出桶
nextOverflow *bmap // 下一个尚未应用的溢出桶
}
type bmap struct {tophash [bucketCnt]uint8 // 存储 tophash 的值
}
能够看到如果以后桶存满了当前，查看 hmap.extra.nextoverflow 还有可用的溢出桶，就在这个桶前面链上这个溢出桶，而后持续往这个溢出桶里
四、创立 map
咱们晓得创立 map 个别用 make(map) 的形式，上面咱们看看创立 map 具体是怎么操作的，下图是创立 map 时的主流程:
- 依据须要初始化的大小来确定
B的值 - 如果
B的值≥4，确定溢出桶的数量 - 调配桶和溢出桶的内存
源码剖析：
// make map 返回的是指针
func makemap(t *maptype, hint int, h *hmap) *hmap {
if h == nil {h = new(hmap)
}
h.hash0 = fastrand()
// 依据 hint 初始化桶的大小
B := uint8(0)
for overLoadFactor(hint, B) {B++}
h.B = B
// 如果桶的数量大于 0，初始化桶的内存
if h.B != 0 {
var nextOverflow *bmap
h.buckets, nextOverflow = makeBucketArray(t, h.B, nil)
if nextOverflow != nil {h.extra = new(mapextra)
h.extra.nextOverflow = nextOverflow
}
}
return h
}
// 给 map bucket 分配内存
// @param t map 的类型
// @param b 桶的个数 2^b
// @param dirtyalloc 是否要把返回的 buckets 指向 dirtyalloc 地址
// @return buckets buckets 地址
// @return nextOverflow 溢出桶地址
func makeBucketArray(t *maptype, b uint8, dirtyalloc unsafe.Pointer) (buckets unsafe.Pointer, nextOverflow *bmap) {base := bucketShift(b)
nbuckets := base //bucket 的数量
// 当 b 大于 4 是，增加溢出桶，溢出桶的大小为 2^(b-4)个
if b >= 4 {nbuckets += bucketShift(b - 4)
}
// 申请桶的空间
if dirtyalloc == nil {buckets = newarray(t.bucket, int(nbuckets))
} else {
buckets = dirtyalloc
size := t.bucket.size * nbuckets
if t.bucket.ptrdata != 0 {memclrHasPointers(buckets, size)
} else {memclrNoHeapPointers(buckets, size)
}
}
// 有溢出桶，nextOverflow 指向溢出桶的地址
if base != nbuckets {nextOverflow = (*bmap)(add(buckets, base*uintptr(t.bucketsize)))
last := (*bmap)(add(buckets, (nbuckets-1)*uintptr(t.bucketsize)))
last.setoverflow(t, (*bmap)(buckets))
}
return buckets, nextOverflow
}
五、通过 key 获取 val
当咱们应用 val,ok := map[key] 会产生什么呢？同样，咱们先通过一个流程图理解一下主流程：
- 判断 map 是否为空
- 判断是否有协程在并发的写、
- 定位到 key 对应的桶地位，如果 map 正在扩（等量）容且该桶还未被迁徙，定位到旧桶的地位
- 遍历该桶的每个 tophash、key，直到找到和指定 key 相等的数据
上面咱们看看源码：
// @param t map 的类型
// @param h map 数据
// 通过 key 获取 val
func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
//map 为 nil 或者没有数据，返回零值
if h == nil || h.count == 0 {if t.hashMightPanic() {t.hasher(key, 0)
}
return unsafe.Pointer(&zeroVal[0])
}
//@Step1 有并发的协程正在写，抛出异样（panic）if h.flags&hashWriting != 0 {throw("concurrent map read and map write")
}
//@Step2 计算 key 的 hash，定位到以后 key 的 hash 桶地位
hash := t.hasher(key, uintptr(h.hash0))
m := bucketMask(h.B)
b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))
//@Step3 判断有没有旧桶（正在迁徙）// 如果旧桶数据没有被迁徙，定位到以后 key 在旧桶的地位
// 如果以后旧桶没有被迁徙，则迁徙桶
if c := h.oldbuckets; c != nil {if !h.sameSizeGrow() { // 不是进行同长度的扩容（当 map 被删除过多时，须要从新整合数据，避免浪费过多空间）m >>= 1
}
oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize)))
if !evacuated(oldb) {b = oldb}
}
// 取 top hash
top := tophash(hash)
//@Step4 从 bucket 中找出 key 对应的 val，循环遍历 top hash
bucketloop:
for ; b != nil; b = b.overflow(t) { // 是否有溢出桶
for i := uintptr(0); i < bucketCnt; i++ {
//top hash 是否相等
if b.tophash[i] != top {if b.tophash[i] == emptyRest { // 如果 top hash 为 emptyRest，则示意前面没数据了
break bucketloop
}
continue
}
k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
if t.indirectkey() {k = *((*unsafe.Pointer)(k))
}
// key 是否相等，相等则返回对应的 val
if t.key.equal(key, k) {e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
if t.indirectelem() {e = *((*unsafe.Pointer)(e))
}
return e
}
}
}
return unsafe.Pointer(&zeroVal[0])// 返回零值
}六、增加 key value
增加 key-val 的时候产生了什么呢？同样，咱们先来看一下流程图：
- 判断 map 是否为空、判断有没有协程并发写
- 如果 buckets 为空，申请一个长度为 1 的 buckets
- 找出改 key 对应的桶地位
- 如果 map 正在迁徙切该桶没有被迁徙，迁徙该桶
- 遍历该桶，如果找到雷同的 key，返回 val 的地位。如果没有找到，找出下一个空地位，赋值 tophash、key，返回 val 的地位
- 判断 map 是否须要扩容，如果扩容，返回 5 的操作
- 如果以后 buckets 和溢出 buckets 都没有地位了，增加一个溢出 buckets，赋值 tophash、key 到第一个空位，返回 val 的地位
源码剖析：
// 新增或者替换 key val m[key]=val
func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
//@Step1 如果 map 为 nil，panic
if h == nil {panic(plainError("assignment to entry in nil map"))
}
// 判断有没有协程正在写 map
if h.flags&hashWriting != 0 {throw("concurrent map writes")
}
hash := t.hasher(key, uintptr(h.hash0))
// 设置 map 写的标记
h.flags ^= hashWriting
//@Step2 buckets 为 nil，new 一个
if h.buckets == nil {h.buckets = newobject(t.bucket) // newarray(t.bucket, 1)
}
again:
//@Step3 找出 key hash 对应的桶
bucket := hash & bucketMask(h.B)
if h.growing() {
// @Step4 如果桶须要迁徙，则把旧桶迁徙
growWork(t, h, bucket)
}
b := (*bmap)(add(h.buckets, bucket*uintptr(t.bucketsize)))
top := tophash(hash)
var inserti *uint8
var insertk unsafe.Pointer
var elem unsafe.Pointer
//@Step5 寻找 map 中有没有存在的 key
// 5-1 如果存在，更新 key 的值，则返回 val 的地位
// 5-2 如果不存在，则记录 bucket 最近一个空地位的 tophash、key、value 的地位
// 5-2-1 判断 bucket 有没有溢出，如果没有溢出，则下一步。// 5-2-2 溢出了则找出下一个溢出桶，持续 bucketloop 上述操作
bucketloop:
for {for i := uintptr(0); i < bucketCnt; i++ {if b.tophash[i] != top {
// 判断以后元素是否为空，如果为空，记录第一个为空的地位（不便找不到 key 时插入）if isEmpty(b.tophash[i]) && inserti == nil {inserti = &b.tophash[i]
insertk = add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
elem = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
}
if b.tophash[i] == emptyRest {break bucketloop}
continue
}
k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
if !t.key.equal(key, k) {continue}
elem = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
// 找到了 key
goto done
}
// 在惯例桶中没有找到数据，在溢出桶持续找
ovf := b.overflow(t)
if ovf == nil {break}
b = ovf
}
//@Step6 如果增加一个元素会造成 bucket 超过负载（6.5），或者溢出 bucket 太多
// 裁减桶，返回下面逻辑 bucketloop 持续寻找 val 地位
if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {hashGrow(t, h)
goto again
}
//@Step7 以后 bucket 和溢出桶都满了，从新增加一个溢出桶
if inserti == nil {newb := h.newoverflow(t, b)
inserti = &newb.tophash[0]
insertk = add(unsafe.Pointer(newb), dataOffset)
elem = add(insertk, bucketCnt*uintptr(t.keysize))
}
// 贮存 key、tophash 的地位。h.count +1
if t.indirectkey() {kmem := newobject(t.key)
*(*unsafe.Pointer)(insertk) = kmem
insertk = kmem
}
if t.indirectelem() {vmem := newobject(t.elem)
*(*unsafe.Pointer)(elem) = vmem
}
typedmemmove(t.key, insertk, key)
*inserti = top
h.count++
// 返回 val 的地位
done:
if h.flags&hashWriting == 0 {throw("concurrent map writes")
}
h.flags &^= hashWriting
if t.indirectelem() {elem = *((*unsafe.Pointer)(elem))
}
return elem
}七、删除 key value
删除 key 的时候产生了什么呢？同样，咱们先来看一下流程图：
源码剖析：
// 删除 key、val
func mapdelete(t *maptype, h *hmap, key unsafe.Pointer) {
// 判断 map 是否处于写状态
if h.flags&hashWriting != 0 {throw("concurrent map writes")
}
hash := t.hasher(key, uintptr(h.hash0))
// 把 map 置为写状态
h.flags ^= hashWriting
//1 找出对应的桶地位
// 如果须要迁徙，持续迁徙
bucket := hash & bucketMask(h.B)
if h.growing() {growWork(t, h, bucket)
}
b := (*bmap)(add(h.buckets, bucket*uintptr(t.bucketsize)))
bOrig := b
top := tophash(hash)
//2
// 2-1 找出 tophash key val 地位
// 2-2 把 tophash 置为 emptyOne（以后地位为空，但前面还有元素）// 2-3 以后 bucket 前面没有元素，则置为 emptyRest（以后地位为空，且前面没有元素）search:
for ; b != nil; b = b.overflow(t) {for i := uintptr(0); i < bucketCnt; i++ {if b.tophash[i] != top {if b.tophash[i] == emptyRest { // 如果发现对应的 tophash 曾经是 emptyRest 状态，则标识前面没有数据了
break search
}
continue
}
k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
k2 := k
if !t.key.equal(key, k2) {continue}
e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
// 革除 val
if t.indirectelem() {*(*unsafe.Pointer)(e) = nil
} else if t.elem.ptrdata != 0 {memclrHasPointers(e, t.elem.size)
} else {memclrNoHeapPointers(e, t.elem.size)
}
// 把 tophash 置为 emptyOne（以后地位为空，但前面还有元素）b.tophash[i] = emptyOne
//3 判断下一个地位（可能是溢出桶第一个）tophash 是不是 emptyRest
// 3-1 如果不是，间接到 notLast 完结流程
// 3-2 如果是，往前搜寻，把所有 emptyOne 置为 emptyRest
if i == bucketCnt-1 {if b.overflow(t) != nil && b.overflow(t).tophash[0] != emptyRest {goto notLast}
} else {if b.tophash[i+1] != emptyRest {goto notLast}
}
for {b.tophash[i] = emptyRest
if i == 0 {
if b == bOrig {break}
c := b
for b = bOrig; b.overflow(t) != c; b = b.overflow(t) { }
i = bucketCnt - 1
} else {i--}
if b.tophash[i] != emptyOne {break}
}
notLast:
// 数量减 1
h.count--
break search
}
}
}
六、迭代 key value
遍历 key-val 就比较简单了。给定一个随机桶地位 startBucket，和随机桶内数据地位 offset，开始遍历 map 的每个值：
源码剖析：
// 初始化迭代器
func mapiterinit(t *maptype, h *hmap, it *hiter) {
//1 初始化迭代器
it.t = t
if h == nil || h.count == 0 {return}
it.h = h
it.B = h.B
it.buckets = h.buckets
//2 给一个随机数，决定迭代桶的开始地位和桶内开始迭代的程序
r := uintptr(fastrand())
if h.B > 31-bucketCntBits {r += uintptr(fastrand()) << 31
}
it.startBucket = r & bucketMask(h.B) // 桶的偏移量
it.offset = uint8(r >> h.B & (bucketCnt - 1)) // 桶内偏移量
it.bucket = it.startBucket
}
// 迭代器迭代
// 1 从随机偏移桶循环迭代每个桶数据
// 2 桶内从随机偏移量开始遍历
// 3 列出该办法隐掉了当正在进行扩容时怎么迭代，须要理解参考源码
func mapiternext(it *hiter) {
if h.flags&hashWriting != 0 { // 有协程正在写
throw("concurrent map iteration and map write")
}
t := it.t
bucket := it.bucket
b := it.bptr
i := it.i
checkBucket := it.checkBucket
next:
if b == nil { // 以后桶指针为 nil，标识桶内数据曾经遍历实现，须要遍历下一个桶
if bucket == it.startBucket && it.wrapped { // 曾经遍历到开始的桶
it.key = nil
it.elem = nil
return
}
bucket++
if bucket == bucketShift(it.B) {
bucket = 0
it.wrapped = true
}
i = 0
}
for ; i < bucketCnt; i++ {offi := (i + it.offset) & (bucketCnt - 1) // 从桶内哪个地位开始遍历
if isEmpty(b.tophash[offi]) || b.tophash[offi] == evacuatedEmpty {// 没数据
continue
}
k := add(unsafe.Pointer(b), dataOffset+uintptr(offi)*uintptr(t.keysize))
e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+uintptr(offi)*uintptr(t.elemsize))
b = b.overflow(t)
i = 0
goto next
}
参考：
https://github.com/golang/go/…