我们在平常不管是做算法题还是写程序，map都是一种十分常用的数据结构，而他的实现也并不复杂，一般是通过hash计算出key的值，然后寻找到key可以存储的位置，这是由于key是无穷大的，可能会出现两个key映射到同一个位置的情况，这就会出现hash冲突，那解决hash冲突的方法一般是拉链法和开放寻址法。
我们在上面看到的了map的大概实现原理，但是有很多细节可以优化map的查询速度和存储效率，下面我们来看一下go语言是如何实现map结构的
map在go的结构
桶数组
map在go中使用桶数组来存储同一个key的值，并且每个桶最多可以存储8个key-value，如果有超过8个key-value映射到同一个桶当中，会使用创建桶链表的方式来解决这一问题。
那go的map是如何解决哈希冲突的问题呢，它是结合了开放寻址法和拉链法
- 当一个key通过hash计算出它属于哪一个桶的时候，他会现在这个桶中通过开放寻址法找到空位插入，然后如果当前桶的8个key已经被填满了就通过溢出桶指针到下一个桶中查看，看下一个桶是否有空位置，如果都没有，他会新创建一个桶用来存储这个key。
扩容提高性能
根据我们在上面对于go，map的大致介绍我们应该可以理解，如果不进行桶的数量扩容的话，很可能有很多个key同时映射到一个桶中，那么我们想要找到这个key对应的value就只能历遍桶，那么它是时间复杂度就会变成线性的，所以我们需要在key-value的数量满足一定的个数的时候进行桶的扩容，那我们现在来看一下go map是如何进行扩容的。
- 增量扩容：增量扩容就是增加桶的数量，它是当key-value / buckets > 6.5时发生，它会把桶的数量扩容到原来的两倍。
- 等量扩容，等量扩容并不会改变桶的数量，但是他会调整结构，它是在溢出桶的数量超过桶数组长度时发生扩容
- 渐进式扩容，这里如果看过redis扩容的话应该是有了解，他就是一步步的将原来桶中的数据移到目标桶，从而避免一次性扩容引发性能抖动.。
数据结构
hmap
type hmap struct {
count int
flags uint8
B uint8
noverflow uint16
hash0 uint32
buckets unsafe.Pointer
oldbuckets unsafe.Pointer
nevacuate uintptr
extra *mapextra
}这里我来对结构的属性做一下声明
- count：桶中key-value的数量
- flags：map的状态标识，可以标识出map是否被goroutine并发读写
- B：桶数组长度的指数
- noverflow：map中溢出桶的数量
- hash0：hash随机因子，生成key的hash值时会用到
- buckets：桶数组
- olodbuckets：扩容过程中老的buckets
- nevacuate：扩容时的进度标识，index小于nevacuate的桶都已经从老桶转移到新桶中
- extra：预申请的溢出桶
mapextra
就是上面extra的结构
type mapextra struct {
overflow *[]*bmap
oldoverflow *[]*bmap
nextOverflow *bmap
}在 map 初始化时，倘若容量过大，会提前申请好一批溢出桶，以供后续使用，这部分溢出桶存放在 hmap.mapextra 当中：
（1）mapextra.overflow：供桶数组 buckets 使用的溢出桶；
（2）mapextra.oldoverFlow: 扩容流程中，供老桶数组 oldBuckets 使用的溢出桶；
（3）mapextra.nextOverflow：下一个可用的溢出桶.
bmap
const bucketCnt = 8
type bmap struct {
tophash [bucketCnt]uint8
}（1）bmap 就是 map 中的桶，可以存储 8 组 key-value 对的数据，以及一个指向下一个溢出桶的指针；
（2）每组 key-value 对数据包含 key 高 8 位 hash 值 tophash，key 和 val 三部分；
（3）在代码层面只展示了 tophash 部分，但由于 tophash、key 和 val 的数据长度固定，因此可以通过内存地址偏移的方式寻找到后续的 key 数组、val 数组以及溢出桶指针；
（4）为方便理解，把完整的 bmap 类声明代码补充如下：
type bmap struct {
tophash [bucketCnt]uint8
keys [bucketCnt]T
values [bucketCnt]T
overflow uint8
}读流程
map 读流程主要分为以下几步：
（1）根据 key 取 hash 值；
（2）根据 hash 值对桶数组取模，确定所在的桶；
（3）沿着桶链表依次遍历各个桶内的 key-value 对；
（4）命中相同的 key，则返回 value；倘若 key 不存在，则返回零值.
map 读操作最终会走进 runtime/map.go 的 mapaccess 方法中，下面开始阅读源码：
func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
//未初始化或者map的数量为0，直接返回对应类型的0值
if h == nil || h.count == 0 {
return unsafe.Pointer(&zeroVal[0])
}
//如果有其他协程在写，跑出fatal
if h.flags&hashWriting != 0 {
fatal("concurrent map read and map write")
}
//计算相关的哈希值，并对桶去摸获得对应的桶数
hash := t.hasher(key, uintptr(h.hash0))
m := bucketMask(h.B)
b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))
//这里判断是否正在扩容，如果是的话，根据nevacuate判断这个桶是在新桶还是老桶
if c := h.oldbuckets; c != nil {
if !h.sameSizeGrow() {
m >>= 1
}
oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize)))
if !evacuated(oldb) {
b = oldb
}
}
//取key hash的高8位值top
top := tophash(hash)
bucketloop:
//以此历遍每个桶和后面的溢出桶
for ; b != nil; b = b.overflow(t) {
for i := uintptr(0); i < bucketCnt; i++ {
//如果不匹配并且当前tophash为0证明之后都没有，就退出循环
if b.tophash[i] != top {
if b.tophash[i] == emptyRest {
break bucketloop
}
continue
}
k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
if t.indirectkey() {
k = *((*unsafe.Pointer)(k))
}
//如果找到了相同的key就返回value
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])
}
func (h *hmap) sameSizeGrow() bool {
return h.flags&sameSizeGrow != 0
}
func evacuated(b *bmap) bool {
h := b.tophash[0]
return h > emptyOne && h < minTopHash
}写流程
map 写流程主要分为以下几步：
（1）根据 key 取 hash 值；
（2）根据 hash 值对桶数组取模，确定所在的桶；
（3）倘若 map 处于扩容，则迁移命中的桶，帮助推进渐进式扩容；
（4）沿着桶链表依次遍历各个桶内的 key-value 对；
（5）倘若命中相同的 key，则对 value 中进行更新；
（6）倘若 key 不存在，则插入 key-value 对；
（7）倘若发现 map 达成扩容条件，则会开启扩容模式，并重新返回第（2）步.
map 写操作最终会走进 runtime/map.go 的 mapassign 方法中，下面开始阅读源码：
func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
//如果map没有初始化，直接panic
if h == nil {
panic(plainError("assignment to entry in nil map"))
}
//如果其他协程正在进行写或者删除操作，panic
if h.flags&hashWriting != 0 {
fatal("concurrent map writes")
}
//获取hash
hash := t.hasher(key, uintptr(h.hash0))
//标记当前map为写状态
h.flags ^= hashWriting
//如果buckets为空，初始化
if h.buckets == nil {
h.buckets = newobject(t.bucket)
}
again:
//找到对应的桶
bucket := hash & bucketMask(h.B)
//如果发现map正处于扩容阶段，帮助其进行渐进式扩容
if h.growing() {
growWork(t, h, bucket)
}
b := (*bmap)(add(h.buckets, bucket*uintptr(t.bucketsize)))
top := tophash(hash)
//提前申请号变量用于存放key-value的空槽
var inserti *uint8
var insertk unsafe.Pointer
var elem unsafe.Pointer
bucketloop:
for {
for i := uintptr(0); i < bucketCnt; i++ {
if b.tophash[i] != top {
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))
}
//如果发现当前都为空，无需历遍break
if b.tophash[i] == emptyRest {
break bucketloop
}
continue
}
//找到相等的key，到done执行更新操作
k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
if t.indirectkey() {
k = *((*unsafe.Pointer)(k))
}
if !t.key.equal(key, k) {
continue
}
if t.needkeyupdate() {
typedmemmove(t.key, k, key)
}
elem = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
goto done
}
ovf := b.overflow(t)
if ovf == nil {
break
}
b = ovf
}
//这里表示没有找到相同的key，判断是否需啊哟开启扩容，如果需要则道again的位置重新进行插入
if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
hashGrow(t, h)
goto again
}
//如果历遍了桶链表也没有找到一个空位置，会创建一个溢出桶挂到当前桶的尾部
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))
}
//插入到空位并将count++
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++
done:
//更新元素
if h.flags&hashWriting == 0 {
fatal("concurrent map writes")
}
h.flags &^= hashWriting
if t.indirectelem() {
elem = *((*unsafe.Pointer)(elem))
}
return
}删除流程
（1）根据 key 取 hash 值；
（2）根据 hash 值对桶数组取模，确定所在的桶；
（3）倘若 map 处于扩容，则迁移命中的桶，帮助推进渐进式扩容；
（4）沿着桶链表依次遍历各个桶内的 key-value 对；
（5）倘若命中相同的 key，删除对应的 key-value 对；并将当前位置的 tophash 置为 emptyOne，表示为空；
（6）倘若当前位置为末位，或者下一个位置的 tophash 为 emptyRest，则沿当前位置向前遍历，将毗邻的 emptyOne 统一更新为 emptyRest.
这里就不展开讲了
扩容流程
map 的扩容类型分为两类，一类叫做增量扩容，一类叫做等量扩容.
（1）增量扩容：条件是key-value的数量大于桶数组长度的6.5倍
表现：扩容后，桶数组的长度增长为原长度的 2 倍；
目的：降低每个桶中 key-value 对的数量，优化 map 操作的时间复杂度.
（2）等量扩容：条件是溢出桶的数量大于桶的数组长度
表现：扩容后，桶数组的长度和之前保持一致；但是溢出桶的数量会下降.
目的：提高桶主体结构的数据填充率，减少溢出桶数量，避免发生内存泄漏.
何时扩容：只有在map的写流程可能开启扩容模式
怎么开启扩容模式
func hashGrow(t *maptype, h *hmap) {
//增量扩容bigger取1
bigger := uint8(1)
if !overLoadFactor(h.count+1, h.B) {
bigger = 0
h.flags |= sameSizeGrow
}
//将原数组赋值给old数组，并创建一批新的桶数据和溢出桶
oldbuckets := h.buckets
newbuckets, nextOverflow := makeBucketArray(t, h.B+bigger, nil)
//更新B，flags，old，buckets，nevacuate，noverflow
flags := h.flags &^ (iterator | oldIterator)
if h.flags&iterator != 0 {
flags |= oldIterator
}
// commit the grow (atomic wrt gc)
h.B += bigger
h.flags = flags
h.oldbuckets = oldbuckets
h.buckets = newbuckets
h.nevacuate = 0
h.noverflow = 0
if h.extra != nil && h.extra.overflow != nil {
// Promote current overflow buckets to the old generation.
if h.extra.oldoverflow != nil {
throw("oldoverflow is not nil")
}
h.extra.oldoverflow = h.extra.overflow
h.extra.overflow = nil
}
if nextOverflow != nil {
if h.extra == nil {
h.extra = new(mapextra)
}
h.extra.nextOverflow = nextOverflow
}增量扩容与等量扩容
（1）在等量扩容中，新桶数组长度与原桶数组相同；
（2）key-value 对在新桶数组和老桶数组的中的索引号保持一致；
（3）在增量扩容中，新桶数组长度为原桶数组的两倍；
（4）把新桶数组中桶号对应于老桶数组的区域称为 x 区域，新扩展的区域称为 y 区域.
（5）实际上，一个 key 属于哪个桶，取决于其 hash 值对桶数组长度取模得到的结果，因此依赖于其低位的 hash 值结果.；
（6）在增量扩容流程中，新桶数组的长度会扩展一位，假定 key 原本从属的桶号为 i，则在新桶数组中从属的桶号只可能是 i （x 区域）或者 i + 老桶数组长度（y 区域）；
（7）当 key 低位 hash 值向左扩展一位的 bit 位为 0，则应该迁往 x 区域的 i 位置；倘若该 bit 位为 1，应该迁往 y 区域对应的 i + 老桶数组长度的位置.
渐进式扩容
map 采用的是渐进扩容的方式，避免因为一次性的全量数据迁移引发性能抖动.
当每次触发写、删操作时，会为处于扩容流程中的 map 完成两组桶的数据迁移：
（1）一组桶是当前写、删操作所命中的桶；
（2）另一组桶是，当前未迁移的桶中，索引最小的那个桶.
func growWork(t *maptype, h *hmap, bucket uintptr) {
// make sure we evacuate the oldbucket corresponding
// to the bucket we're about to use
evacuate(t, h, bucket&h.oldbucketmask())
// evacuate one more oldbucket to make progress on growing
if h.growing() {
evacuate(t, h, h.nevacuate)
}
}等量扩容的意义：解决什么问题？
想象一下这个场景：
你创建了一个 map，并向里面添加了成千上万的键值对。之后，你又进行了大量的删除操作。
- 删除的坑：Go 的
map删除操作并不是真的把内存释放掉，而只是将对应位置的键值标记为“已删除”（空位）。这些空位无法被后续的插入操作立即充分利用，导致桶的利用率降低。 - 溢出桶的积累：由于大量删除导致桶内有很多空位，新的插入可能无法有效利用这些空位，反而会继续创建新的溢出桶。久而久之，这个
map看起来存储的数据不多，但实际上挂载着非常长的溢出桶链表。
这会带来两个问题：
- 内存浪费：大量几乎为空的溢出桶占着内存不释放。
- 性能下降：查找一个 key 可能需要遍历很长很长的溢出桶链表，即使真正的数据量并不大。
等量扩容就是为了解决这个问题而生的！ 它的核心意义在于：整理和紧缩。
等量扩容是如何工作的？（“怎么扩容”）
过程可以概括为：
- 诊断：运行时系统检测到溢出桶的数量超过了上述的阈值。
- 决策：决定发起一次等量扩容（
hint为sameSizeGrow）。 - 分配：分配一块新的内存区域，其大小和当前的基础桶数组完全一样（注意：是基础桶，不包括那些溢出的桶）。
- 搬迁：启动搬迁过程，将旧的基础桶和所有溢出桶中的键值对，重新哈希并紧凑地排列到新的基础桶数组中。
- 这个过程会跳过所有已删除的（tophash 标记为空的）键值对。
- 它会尽可能地把数据放在新桶数组的“基础桶”里，最大限度地减少甚至消除对溢出桶的需求。
- 切换与回收：搬迁完成后，将
map的指针指向新的桶数组，并释放旧的桶数组和所有溢出桶的内存。
参考：小徐先生的编程世界公众号
Comments NOTHING