锐客网

  1. 首页 > 睿知 > it技术 > >

go语言map固定顺序 go语言map底层实现原理( 四 )

IT技术Hung


map 本身是无序的，且遍历时顺序还会被随机化，如果想顺序遍历 map ， 需要对 map key 先排序，再按照 key 的顺序遍历 map 。
map默认是并发不安全的，原因如下：
Go 官方在经过了长时间的讨论后，认为 Go map 更应适配典型使用场景（不需要从多个 goroutine 中进行安全访问），而不是为了小部分情况（并发访问），导致大部分程序付出加锁代价（性能），决定了不支持 。
场景:2个协程同时读和写，以下程序会出现致命错误：fatal error: concurrent map writes
如果想实现map线程安全 ， 有两种方式：
方式一：使用读写锁map+sync.RWMutex
方式二：使用golang提供的sync.Map
sync.map是用读写分离实现的 ， 其思想是空间换时间 。和map+RWLock的实现方式相比，它做了一些优化：可以无锁访问read map，而且会优先操作read map，倘若只操作read map就可以满足要求(增删改查遍历)，那就不用去操作write map(它的读写都要加锁)，所以在某些特定场景中它发生锁竞争的频率会远远小于map+RWLock的实现方式 。
golang中map是一个kv对集合 。底层使用hash table，用链表来解决冲突，出现冲突时，不是每一个key都申请一个结构通过链表串起来 ， 而是以bmap为最小粒度挂载，一个bmap可以放8个kv 。在哈希函数的选择上 ， 会在程序启动时，检测 cpu 是否支持 aes，如果支持，则使用 aes hash，否则使用 memhash 。
map有3钟初始化方式，一般通过make方式创建
map的创建通过生成汇编码可以知道，make创建map时调用的底层函数是 runtime.makemap。如果你的map初始容量小于等于8会发现走的是 runtime.fastrand 是因为容量小于8时不需要生成多个桶，一个桶的容量就可以满足
makemap函数会通过fastrand创建一个随机的哈希种子，然后根据传入的hint计算出需要的最小需要的桶的数量，最后再使用makeBucketArray 创建用于保存桶的数组，这个方法其实就是根据传入的B计算出的需要创建的桶数量在内存中分配一片连续的空间用于存储数据，在创建桶的过程中还会额外创建一些用于保存溢出数据的桶，数量是2^(B-4)个 。初始化完成返回hmap指针 。
找到一个 B ， 使得 map 的装载因子在正常范围内
Go 语言中读取 map 有两种语法：带 comma 和 不带 comma 。当要查询的 key 不在 map 里 ， 带 comma 的用法会返回一个 bool 型变量提示 key 是否在 map 中；而不带 comma 的语句则会返回一个 value 类型的零值 。如果 value 是 int 型就会返回 0，如果 value 是 string 类型，就会返回空字符串 。
map的查找通过生成汇编码可以知道 ， 根据 key 的不同类型，编译器会将查找函数用更具体的函数替换，以优化效率：
函数首先会检查 map 的标志位 flags 。如果 flags 的写标志位此时被置 1 了，说明有其他协程在执行“写”操作 ， 进而导致程序 panic 。这也说明了 map 对协程是不安全的 。
key经过哈希函数计算后，得到的哈希值如下（主流64位机下共 64 个 bit 位）：
m: 桶的个数
从buckets 通过 hashm 得到对应的bucket，如果bucket正在扩容，并且没有扩容完成 ， 则从oldbuckets得到对应的bucket
计算hash所在桶编号：
用上一步哈希值最后的 5 个 bit 位，也就是01010  ， 值为 10 ， 也就是 10 号桶（范围是0~31号桶）
计算hash所在的槽位:
用上一步哈希值哈希值的高8个bit 位，也就是 10010111，转化为十进制，也就是151，在 10 号 bucket 中寻找** tophash 值（HOB hash）为 151* 的 槽位** ， 即为key所在位置，找到了 2 号槽位，这样整个查找过程就结束了 。

推荐阅读


上一篇：chatgpt替代软件，chatter软件

下一篇：关于chatGPT，关于ChatGPT的论文