码农桃花源
  • README
  • channel
    • 06 - 从一个关闭的 channel 仍然能读出数据吗
    • 12 - channel 有哪些应用
    • 08 - 如何优雅地关闭 channel
    • 10 - channel 在什么情况下会引起资源泄漏
    • 00 - 什么是 CSP
    • channel 底层的数据结构是什么
    • 09 - channel 发送和接收元素的本质是什么
    • 11 - 关于 channel 的 happened-before 有哪些
    • 04 - 向 channel 发送数据的过程是怎样的
    • 03 - 从 channel 接收数据的过程是怎样的
    • 07 - 操作 channel 的情况总结
    • 05 - 关闭一个 channel 的过程是怎样的
  • map
    • map 的底层实现原理是什么
    • 可以边遍历边删除吗
    • map 的删除过程是怎样的
    • 可以对 map 的元素取地址吗
    • 如何比较两个 map 相等
    • 如何实现两种 get 操作
    • map 是线程安全的吗
    • map 的遍历过程是怎样的
    • map 中的 key 为什么是无序的
    • float 类型可以作为 map 的 key 吗
    • map 的赋值过程是怎样的
    • map 的扩容过程是怎样的
  • interface
    • iface 和 eface 的区别是什么
    • Go 接口与 C++ 接口有何异同
    • 如何用 interface 实现多态
    • 接口转换的原理
    • Go 语言与鸭子类型的关系
    • 值接收者和指针接收者的区别
    • 接口的构造过程是怎样的
    • 编译器自动检测类型是否实现接口
    • 类型转换和断言的区别
    • 接口的动态类型和动态值
  • 标准库
    • context
      • context.Value 的查找过程是怎样的
      • context 如何被取消
      • context 有什么作用
      • context 是什么
    • unsafe
      • 如何利用unsafe包修改私有成员
      • Go指针和unsafe.Pointer有什么区别
      • 如何实现字符串和byte切片的零拷贝转换
      • 如何利用unsafe获取slice&map的长度
  • goroutine 调度器
    • M 如何找工作
    • goroutine 调度时机有哪些
    • 什么是 go shceduler
    • goroutine 如何退出
    • 描述 scheduler 的初始化过程
    • 什么是workstealing
    • mian gorutine 如何创建
    • 什么是M:N模型
    • g0 栈何用户栈如何切换
    • schedule 循环如何运转
    • GPM 是什么
    • schedule 循环如何启动
    • sysmon 后台监控线程做了什么
    • goroutine和线程的区别
    • 一个调度相关的陷阱
  • 编译和链接
    • 逃逸分析是怎么进行的
    • GoRoot 和 GoPath 有什么用
    • Go 编译链接过程概述
    • Go 编译相关的命令详解
    • Go 程序启动过程是怎样的
  • 反射
    • Go 语言中反射有哪些应用
    • 什么情况下需要使用反射
    • 如何比较两个对象完全相同
    • Go 语言如何实现反射
    • 什么是反射
  • 数组和切片
    • 数组和切片有什么异同
    • 切片作为函数参数
    • 切片的容量是怎样增长的
  • GC
    • GC
Powered by GitBook
On this page

Was this helpful?

  1. map

map 的赋值过程是怎样的

通过汇编语言可以看到,向 map 中插入或者修改 key,最终调用的是 mapassign 函数。

实际上插入或修改 key 的语法是一样的,只不过前者操作的 key 在 map 中不存在,而后者操作的 key 存在 map 中。

mapassign 有一个系列的函数,根据 key 类型的不同,编译器会将其优化为相应的“快速函数”。

key 类型

插入

uint32

mapassign_fast32(t maptype, h hmap, key uint32) unsafe.Pointer

uint64

mapassign_fast64(t maptype, h hmap, key uint64) unsafe.Pointer

string

mapassign_faststr(t maptype, h hmap, ky string) unsafe.Pointer

我们只用研究最一般的赋值函数 mapassign。

整体来看,流程非常得简单:对 key 计算 hash 值,根据 hash 值按照之前的流程,找到要赋值的位置(可能是插入新 key,也可能是更新老 key),对相应位置进行赋值。

源码大体和之前讲的类似,核心还是一个双层循环,外层遍历 bucket 和它的 overflow bucket,内层遍历整个 bucket 的各个 cell。限于篇幅,这部分代码的注释我也不展示了,有兴趣的可以去看,保证理解了这篇文章内容后,能够看懂。

我这里会针对这个过程提几点重要的。

函数首先会检查 map 的标志位 flags。如果 flags 的写标志位此时被置 1 了,说明有其他协程在执行“写”操作,进而导致程序 panic。这也说明了 map 对协程是不安全的。

通过前文我们知道扩容是渐进式的,如果 map 处在扩容的过程中,那么当 key 定位到了某个 bucket 后,需要确保这个 bucket 对应的老 bucket 完成了迁移过程。即老 bucket 里的 key 都要迁移到新的 bucket 中来(分裂到 2 个新 bucket),才能在新的 bucket 中进行插入或者更新的操作。

上面说的操作是在函数靠前的位置进行的,只有进行完了这个搬迁操作后,我们才能放心地在新 bucket 里定位 key 要安置的地址,再进行之后的操作。

现在到了定位 key 应该放置的位置了,所谓找准自己的位置很重要。准备两个指针,一个(inserti)指向 key 的 hash 值在 tophash 数组所处的位置,另一个(insertk)指向 cell 的位置(也就是 key 最终放置的地址),当然,对应 value 的位置就很容易定位出来了。这三者实际上都是关联的,在 tophash 数组中的索引位置决定了 key 在整个 bucket 中的位置(共 8 个 key),而 value 的位置需要“跨过” 8 个 key 的长度。

在循环的过程中,inserti 和 insertk 分别指向第一个找到的空闲的 cell。如果之后在 map 没有找到 key 的存在,也就是说原来 map 中没有此 key,这意味着插入新 key。那最终 key 的安置地址就是第一次发现的“空位”(tophash 是 empty)。

如果这个 bucket 的 8 个 key 都已经放置满了,那在跳出循环后,发现 inserti 和 insertk 都是空,这时候需要在 bucket 后面挂上 overflow bucket。当然,也有可能是在 overflow bucket 后面再挂上一个 overflow bucket。这就说明,太多 key hash 到了此 bucket。

在正式安置 key 之前,还要检查 map 的状态,看它是否需要进行扩容。如果满足扩容的条件,就主动触发一次扩容操作。

这之后,整个之前的查找定位 key 的过程,还得再重新走一次。因为扩容之后,key 的分布都发生了变化。

最后,会更新 map 相关的值,如果是插入新 key,map 的元素数量字段 count 值会加 1;在函数之初设置的 hashWriting 写标志出会清零。

另外,有一个重要的点要说一下。前面说的找到 key 的位置,进行赋值操作,实际上并不准确。我们看 mapassign 函数的原型就知道,函数并没有传入 value 值,所以赋值操作是什么时候执行的呢?

func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer

答案还得从汇编语言中寻找。我直接揭晓答案,有兴趣可以私下去研究一下。mapassign 函数返回的指针就是指向的 key 所对应的 value 值位置,有了地址,就很好操作赋值了。

Previousfloat 类型可以作为 map 的 key 吗Nextmap 的扩容过程是怎样的

Last updated 5 years ago

Was this helpful?