专栏首页后端golang 系列:深入认识 map!
原创

golang 系列:深入认识 map!

摘要

map 通过 hasTable 实现了我们最常见的 key-value 存储,能快速的对数据集增删查改。同时 Go 里的 map 也有很多特殊的地方,比如它的无序性、并发不安全等。今天,就让我们对 map 进行深入研究,看看它是怎么设计的。

map 基本认识

当我们用 dataMap := make(map[int]string)创建一个 map 对象的时候,得到的是一个 hmap 指针结构。通过对 src/runtime/map.go文件分析,我们看到了对应的结构体如下:

type hmap struct {
        count     int // 当前的元素个数
        flags     uint8
        B         uint8  // 字段 buckets 数组的长度关联参数,即 buckets 长度为 2^B
        noverflow uint16 // overflow buckets 的近似数
        hash0     uint32 // 哈希种子,作 hash 运算用的
        buckets    unsafe.Pointer // 数组对象,存 key-value的
        oldbuckets unsafe.Pointer // 扩容时用到的 buckets,大小是之前 buckets 的一半。
        nevacuate  uintptr        // 扩容进度

        extra *mapextra // optional fields
}

在这里面,有一个非常关键的字段: buckets,它就是用来存储 key-value 的。

当 Go 对 key 进行 hash 运算后,会通过一定的规则映射到 buckets 的某个位置,然后就会将 key、value 一起存在这个对应位置的桶里。

而这个桶实际上会指向下面这个结构体:

type bmap struct {
        tophash [bucketCnt]uint8
}

之所以会这么简洁,是因为 map 是在编译时才知道对应的 key-value 类型的,所以对于 mapstringint 这样的 map 在编译过后,bmap 最终会变成这样的结构体:

type bmap struct {
	tophash  [bucketCnt]uint8
	keys     [bucketCnt]string
	values   [bucketCnt]int
	overflow *bmap
}

在这里,就有一个 keys,values 数组来存储 key-value 了,其中还有个 tophash 数组,可以先认为它是用来定位 key-value 在对应数组里的存储位置,后面会详细说明它的定位过程。

现在我们大概知道了 key-value 在 map 里的存储走向了:

深入认识 map

map 的存储

接下来,我们来看看 map 存储 key-value 时的具体动作。

首先在程序初始化时,Go 会为 hmap 找到一个合适的 B 值,以创建合适大小的 buckets 数组。

假设 B = 5,则此时 hmap 的 buckets 桶数量为 2^5 = 32。

当我们往 map 添加一个 key 时,Go 会对 key 进行 hash 计算,得到一个 hash 值

在得到这个 hash 值后,会取它的低 5 位,作为定位到 buckets 数组里某个 bucket 的索引位置

这里解释下为何取低 5 位,这里的 5 即是 hmap 的 B 值。 假设低 5 位都是 11111,那么最大值也只会是 31,不超过桶的数量,有点类似取余的操作,这样就不会有越界行为了。

hashCode := hash(key, h.hash0) // 获取 key 的 hash 值
bucketIndex := hashCode & 0x1F // 利用位运算取低 B 位,定位到桶的位置

当我们定位到桶的位置后,后面就是存放 key-value 了。

Go 会继续对 hash 值 取高 8 位,得到一个 top hash 值。然后遍历 bmap 里的 tophash 数组,找到一个空的位置存放。

这里之所以要存储 top hash 值,除了下次找 key 时会先对比下 top hash,还添加了一些扩容进度的状态位,辅助 map 的扩容。

需要注意的是,bmap 的 tophash 数组也是有固定大小的,即 bucketCnt = 8,最多存放 8 个元素。

一旦超过这个数量,则会再创建一个 bmap 对象,通过 overflow 字段指向新的 bmap,这样就又可以存放 8 个元素了。

当确定好在 tophash 的位置后,就可以用这个索引位置也作为 key,value 在 keys,values 数组的位置了,此时 key、value 就存储起来了。

map 的读取

map 的读取基本上也是按上面的流程来进行。同样的对 key 进行 hash 运算,然后取低 B 位,以确定 key 在桶里的位置。

当得到桶的位置后,会继续取 hash 值的高 8 位得到 top hash,然后遍历 tophash 数组,寻找到 top hash 元素的 index 位置。

如果当前找不到,但 overflow 不为空,则继续到 overflow 里寻找 index 位置。

当找到 top hash 的 index 位置后,也就确定了 key 在 keys 数组里的索引位置了,此时会再比较一下是否跟想寻找的 key 相等。

如果相等,则说明找到 key 了,就可以到 values 数组上的相同 index 位置提取 value 了。

如果不一样,则说明还得继续遍历寻找,直到没有元素,也没有 overflow 可继续遍历。

总的存取流程如下:

深入认识 map

上面提到一个 key 的比较过程,所以这里注定了 key 是一个可比较类型,像 int,string 等基础类型是可以作为 key 的。如果是 slice,map,channel 这种不可比较类型,则不能作为 key 来使用了。

map 的扩容

map 之所以能快速的存取元素,是因为用 hash table 快速的进行数组位置的映射。

然而如果出现过多的 hash 冲突,即有多个 key 映射到同一个桶里,就得在读取时进行遍历 bmap 的动作,最差的情况下时间复杂度将达到 O(n)。

因此当 map 的元素过多,超过一定的阈值后,就应该对 map 的数据元素进行重整,平衡数据的读取速度。

Go 通过扩容来实现了数据的读取平衡,在添加或删除数据时,会先判断装载因子的值是否达到扩容要求,达到了则进行扩容动作。

装载因子的计算方式如下:

loadFactor := count / (2^B)

count 指的是当前 map 里的元素个数,2^B 是指当前 map 里 buckets 数组长度,从这可以看出元素越来越多,即 count 越来越大,则越可能触发扩容。

map 除了判断装载因子来进行扩容外,还有另外一种情况也会进行数据重整:overflow 数量过多,但元素很少。这种情况的产生,是因为出现了大量数据的插入和删除,导致 overflow 不能回收,所以也要进行数据重整。

我们重点来看看第一种情况的扩容过程。首先,hmap 会先增加 B 的值,也就是 buckets 数组的数量。然后,重新计算 key 所需要迁移的桶的位置,以便让数据能均衡的分布在新老 buckets 桶里。

当然,Go 并不会一下子就把所有的数据都迁移完毕,而是等到用到某个 key 时,检查此时 key 的迁移状态,再作出迁移动作。

从上面的扩容过程我们也可以看出为什么 map 是无序的了,因为原本在一个 bucket 上的数据有可能被迁移到其他的 bucket 上了,会被打乱顺序。

当然,Go 官方也可以将 key 全部获取到后做排序动作,但显然 Go 官方不想这么做,想明明白白的告诉开发者,map 的实现就是 hash 无序的。

对于第二种情况的数据重整,就比较简单了。只要在当前 bucket 里收缩各个 overflow 到空位上即可。

其他特性

1)并发不安全:map 在进行读取 key 的时候会检查当前的 hmap.flags 字段,如果发现该值是一个写状态值的话,则会直接 panic。

2)当使用 float 作为 map 的 key 时,由于 float 精度问题,会出现获取不到 float key 对应 value 的情况,所以应该慎用 float 作为 key。

总结

Go 里的 map 设计的比较精巧,通过获取 hash 值,并且对 hash 值进行低位运算来找到对应的 bucket,接着再利用 hash 值的高几位,来确定 key 在 bucket 里的具体位置。

而且 map 在扩容时也是懒扩容的,并不会一次性阻塞在迁移过程。

当然,map 的并发不安全也是我们需要注意的,以免程序 pannic。

以上大概就是 map 的精髓所在了!


感兴趣的朋友可以搜一搜公众号「 阅新技术 」,关注更多的推送文章。

可以的话,就顺便点个赞、留个言、分享下,感谢各位支持!

阅新技术,阅读更多的新知识。

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

关注作者,阅读全部精彩内容

我来说两句

0 条评论
登录 后参与评论

相关文章

  • js入门(ES6)[三]---认识Symbol、Map、 Set

    输入一个字符串 在全局搜索被登记的 Symbol是否存在,如果不存在就登记输入的字符串。

    代码哈士奇
  • Golang 语言的内存管理

    使用 len() 获取字符串长度,返回的是字节长度,如果想要获取 unicode 长度,需要使用 utf8 包的方法。

    frank.
  • Netty实现高性能IOT服务器(Groza)之精尽代码篇中

    近年来,物联网高歌猛进,美国有“工业互联网”,德国有“工业4.0”,我国也有“中国制造2025”,这背后都是云计算、大数据。据波士顿咨询报告,单单中国制造业,云...

    sanshengshui
  • 《Golang从入门到跑路》之map的初识

    map是一种无序的,基于key-value 的数据结构。它是Go语言中的映射关系容器,其内部是使用散列表(hash) 实现的。

    极客运维圈
  • golang-nsq系列(一)--初识

    nsq 最初是由 bitly 公司开源出来的一款简单易用的分布式消息中间件,它可用于大规模系统中的实时消息服务,并且每天能够处理数亿级别的消息。

    astraw99
  • golang-etcd系列(一)--初识

    etcd 是一个 golang 编写的分布式、高可用的一致性键值存储系统,是目前容器编排领域火热的 Kubernetes(k8s) 内置的服务发现与节点一致性中...

    astraw99
  • 深入浅出Shiro系列——权限认证

    授权,也叫访问控制,即在应用中控制谁能访问哪些资源(如访问页面/编辑数据/页面操作等)。在授权中需了解的几个关键对象:主体(Subject)、资源(Resou ...

    程序员的时光001
  • 乐呵乐呵得了 golang入坑系列

    开场就有料,今天返回去看了看以前的文章,轻松指数有点下降趋势。一琢磨,这不是我的风格呀。一反思,合着是这段时间,脑子里杂七杂八的杂事有点多,事情一多,就忘了快乐...

    随机来个数
  • Golang 语言中 map 的键值类型选择,它是并发安全的吗?

    关于 golang 语言的 map,已经在「Go 基础」系列文章中介绍过,文末会附上文章链接,建议还没有阅读的读者阅读。我们知道 map 的键必须支持判等操作,...

    frank.
  • 【云+社区年度征文】在Golang中如何正确地使用database/sql包访问数据库

    本文记录了我在实际工作中关于数据库操作上一些小经验,也是新手入门golang时我认为一定会碰到问题,没有什么高大上的东西,所以希望能抛砖引玉,也算是对这个问题的...

    HOHO
  • 论golang是世界上最好的语言

    概述 golang is a better C and a simple C++ golang主要特性 1、语法简单 舍弃语法糖,严格控制关键字 C++语法糖之...

    李海彬
  • Flink系列——感性认识

    老板都是复制整个工厂的整体把控的, 一般不亲自动手,只需要管好 工厂的车间组长 就可以了。 JobManager 则是负责整个集群的资源管理与任务管理, ...

    solve
  • Spark系列(一) 认识Spark

    运行速度:Spark拥有DAG执行引擎,支持在内存中对数据进行迭代计算。官方提供的数据表明,如果数据由磁盘读取,速度是Hadoop MapReduce的10倍以...

    张凝可
  • 崩溃 golang入坑系列

    早上(11.30)收到邮件,Vultr东京机房网络故障。当时搭建SS时,考虑到了机房故障。所以特意分出了日本和香港两条线路。但千算万算,忘记数据库还在东京机房中...

    随机来个数
  • Go 问答汇总篇 二

    继上篇 Go 问答汇总,已经过去了一个多月。今天汇总下近一个多月我关于 Go 的回答。

    波罗学
  • 『Go 语言学习专栏』-- 第二期

    谢伟
  • 手把手教你学之golang反射(上)

    orm这个概念相信同学们都非常熟悉,尤其是写过rails的同学,对active_record的强大肯定深有体会(得益于的method_missing和defin...

    李海彬
  • beego golang bootstrap-table做月度考勤(打卡、签到)统计表

    https://blog.csdn.net/abubu123/article/details/78060321

    hotqin888
  • 你才不是只会理论的女同学-seata实践篇

    这里所指的客户端包含所有的资源管理器,包含所有需要seata-server管理的服务

    你呀不牛

扫码关注云+社区

领取腾讯云代金券