专栏首页GoLang那点事深入Go的Map使用和实现原理

深入Go的Map使用和实现原理

开篇语

Map是一种常用的kv数据结构,程序设计中经常使用,且作为一种最基础的数据结构,很多编程语言本身提供的api都会有实现,Go也不例外,今天我们将从一下三个方面为大家分析Go中的Map。

  • 什么是Map?
  • Go中如何使用Map?
  • 以及Go的Map实现机制是什么样?希望通过这几个方面的讲解,让大家真正理解Go的Map使用和实现。

什么是Map

key,value存储

最通俗的话说Map是一种通过key来获取value的一个数据结构,其底层存储方式为数组,在存储时key不能重复,当key重复时,value进行覆盖,我们通过key进行hash运算(可以简单理解为把key转化为一个整形数字)然后对数组的长度取余,得到key存储在数组的哪个下标位置,最后将key和value组装为一个结构体,放入数组下标处,看下图:

length = len(array) = 4
hashkey1 = hash(xiaoming) = 4
index1  = hashkey1% length= 0
hashkey2 = hash(xiaoli) = 6
index2  = hashkey2% length= 2
hash冲突

如上图所示,数组一个下标处只能存储一个元素,也就是说一个数组下标只能存储一对key,value, hashkey(xiaoming)=4占用了下标0的位置,假设我们遇到另一个key,hashkey(xiaowang)也是4,这就是hash冲突(不同的key经过hash之后得到的值一样),那么key=xiaowang的怎么存储? hash冲突的常见解决方法

  • 开放定址法 也就是说当我们存储一个key,value时,发现hashkey(key)的下标已经被别key占用,那我们在这个数组中空间中重新找一个没被占用的存储这个冲突的key,那么没被占用的有很多,找哪个好呢?常见的有线性探测法,线性补偿探测法,随机探测法,这里我们主要说一下线性探测法

线性探测,字面意思就是按照顺序来,从冲突的下标处开始往后探测,到达数组末尾时,从数组开始处探测,直到找到一个空位置存储这个key,当数组都找不到的情况下回扩容(事实上当数组容量快满的时候就会扩容了);查找某一个key的时候,找到key对应的下标,比较key是否相等,如果相等直接取出来,否则按照顺寻探测直到碰到一个空位置,说明key不存在。如下图:首先存储key=xiaoming在下标0处,当存储key=xiaowang时,hash冲突了,按照线性探测,存储在下标1处,(红色的线是冲突或者下标已经被占用了) 再者key=xiaozhao存储在下标4处,当存储key=xiaoliu是,hash冲突了,按照线性探测,从头开始,存储在下标2处 (黄色的是冲突或者下标已经被占用了)

  • 拉链法

何为拉链,简单理解为链表,当key的hash冲突时,我们在冲突位置的元素上形成一个链表,通过指针互连接,当查找时,发现key冲突,顺着链表一直往下找,直到链表的尾节点,找不到则返回空,如下图:

  • 开放定址(线性探测)和拉链的优缺点
    1. 由上面可以看出拉链法比线性探测处理简单
    2. 线性探测查找是会被拉链法会更消耗时间
    3. 线性探测会更加容易导致扩容,而拉链不会
    4. 拉链存储了指针,所以空间上会比线性探测占用多一点
    5. 拉链是动态申请存储空间的,所以更适合链长不确定的

Go中Map的使用

直接用代码描述,直观,简单,易理解

//直接创建初始化一个mao
var mapInit = map[string]string {"xiaoli":"湖南", "xiaoliu":"天津"}
//声明一个map类型变量,
//map的key的类型是string,value的类型是string
var mapTemp map[string]string
//使用make函数初始化这个变量,并指定大小(也可以不指定)
mapTemp = make(map[string]string,10)
//存储key ,value
mapTemp["xiaoming"] = "北京"
mapTemp["xiaowang"]= "河北"
//根据key获取value,
//如果key存在,则ok是true,否则是flase
//v1用来接收key对应的value,当ok是false时,v1是nil
v1,ok := mapTemp["xiaoming"]
fmt.Println(ok,v1)
//当key=xiaowang存在时打印value
if v2,ok := mapTemp["xiaowang"]; ok{
    fmt.Println(v2)
}
//遍历map,打印key和value
for k,v := range mapTemp{
    fmt.Println(k,v)
}
//删除map中的key
delete(mapTemp,"xiaoming")
//获取map的大小
l := len(mapTemp)
fmt.Println(l)

看了上面的map创建,初始化,增删改查等操作,我们发现go的api其实挺简单易学的

Go中Map的实现原理

知其然,更得知其所以然,会使用map了,多问问为什么,go底层map到底怎么存储呢?接下来我们一探究竟。map的源码位于 src/runtime/map.go中 笔者go的版本是1.12在go中,map同样也是数组存储的的,每个数组下标处存储的是一个bucket,这个bucket的类型见下面代码,每个bucket中可以存储8个kv键值对,当每个bucket存储的kv对到达8个之后,会通过overflow指针指向一个新的bucket,从而形成一个链表,看bmap的结构,我想大家应该很纳闷,没看见kv的结构和overflow指针啊,事实上,这两个结构体并没有显示定义,是通过指针运算进行访问的。

//bucket结构体定义 b就是bucket
type bmap{
    // tophash generally contains the top byte of the hash value
    // for each key  in this bucket. If tophash[0] < minTopHash,
    // tophash[0] is a bucket               evacuation state instead.
    //翻译:top hash通常包含该bucket中每个键的hash值的高八位。
    如果tophash[0]小于mintophash,则tophash[0]为桶疏散状态    //bucketCnt 的初始值是8
    tophash [bucketCnt]uint8
    // Followed by bucketCnt keys and then bucketCnt values.
    // NOTE: packing all the keys together and then all the values together makes the    // code a bit more complicated than alternating key/value/key/value/... but it allows    // us to eliminate padding which would be needed for, e.g., map[int64]int8.// Followed by an overflow pointer.    //翻译:接下来是bucketcnt键,然后是bucketcnt值。
    注意:将所有键打包在一起,然后将所有值打包在一起,    使得代码比交替键/值/键/值/更复杂。但它允许//我们消除可能需要的填充,    例如map[int64]int8./后面跟一个溢出指针}

看上面代码以及注释,我们能得到bucket中存储的kv是这样的,tophash用来快速查找key值是否在该bucket中,而不同每次都通过真值进行比较;还有kv的存放,为什么不是k1v1,k2v2..... 而是k1k2...v1v2...,我们看上面的注释说的 map[int64]int8,key是int64(8个字节),value是int8(一个字节),kv的长度不同,如果按照kv格式存放,则考虑内存对齐v也会占用int64,而按照后者存储时,8个v刚好占用一个int64,从这个就可以看出go的map设计之巧妙。

最后我们分析一下go的整体内存结构,阅读一下map存储的源码,如下图所示,当往map中存储一个kv对时,通过k获取hash值,hash值的低八位和bucket数组长度取余,定位到在数组中的那个下标,hash值的高八位存储在bucket中的tophash中,用来快速判断key是否存在,key和value的具体值则通过指针运算存储,当一个bucket满时,通过overfolw指针链接到下一个bucket。

go的map存储源码如下,省略了一些无关紧要的代码

func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
    //获取hash算法
    alg := t.key.alg
    //计算hash值
    hash := alg.hash(key, uintptr(h.hash0))
    //如果bucket数组一开始为空,则初始化
    if h.buckets == nil {
        h.buckets = newobject(t.bucket) // newarray(t.bucket, 1)
    }
again:
    // 定位存储在哪一个bucket中
    bucket := hash & bucketMask(h.B)
    //得到bucket的结构体
    b := (*bmap)(unsafe.Pointer(uintptr(h.buckets) +bucket*uintptr(t.bucketsize)))
    //获取高八位hash值
    top := tophash(hash)
    var inserti *uint8
    var insertk unsafe.Pointer
    var val unsafe.Pointer
bucketloop:
    //死循环
    for {
        //循环bucket中的tophash数组
        for i := uintptr(0); i < bucketCnt; i++ {
            //如果hash不相等
            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))
                    val = add( unsafe.Pointer(b), 
                    dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize) )
                }
              //插入成功,终止最外层循环
                if b.tophash[i] == emptyRest {
                    break bucketloop
                }
                continue
            }
            //到这里说明高八位hash一样,获取已存在的key
            k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
            if t.indirectkey() {
                k = *((*unsafe.Pointer)(k))
            }
            //判断两个key是否相等,不相等就循环下一个
            if !alg.equal(key, k) {
                continue
            }
            // 如果相等则更新
            if t.needkeyupdate() {
                typedmemmove(t.key, k, key)
            }
            //获取已存在的value
            val = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))
            goto done
        }
        //如果上一个bucket没能插入,则通过overflow获取链表上的下一个bucket
        ovf := b.overflow(t)
        if ovf == nil {
            break
        }
        b = ovf
    }

    if inserti == nil {
        // all current buckets are full, allocate a new one.
        newb := h.newoverflow(t, b)
        inserti = &newb.tophash[0]
        insertk = add(unsafe.Pointer(newb), dataOffset)
        val = add(insertk, bucketCnt*uintptr(t.keysize))
    }

    // store new key/value at insert position
    if t.indirectkey() {
        kmem := newobject(t.key)
        *(*unsafe.Pointer)(insertk) = kmem
        insertk = kmem
    }
    if t.indirectvalue() {
        vmem := newobject(t.elem)
        *(*unsafe.Pointer)(val) = vmem
    }
    typedmemmove(t.key, insertk, key)
    //将高八位hash值存储
    *inserti = top
    h.count++
    return val
}

关于go的map就分享到这里了,有收获的帮忙转发,点赞,感谢

本文分享自微信公众号 - GoLang那点事(aweiaichitudou),作者:那小子阿伟

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-07-19

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 由浅到深,入门Go语言Map实现原理

    把自己学习知识进行一个总结。同时把一些可能困难、复杂难以理解的东西自我消化吸收后,简单化输出,降低他人的学习成本,提高他人的学习效率,主要为如下两点:

    用户1093396
  • 深入 Go 语言 defer 实现原理

    在上面的例子中,使用 for 循环将字符串 Naveen进行遍历后调用 defer,这些 defer调用仿佛就像被压栈一样,最后被推入堆栈的defer调用将被拉...

    luozhiyun
  • 深入详解Go的channel底层实现原理【图解】

    源码位于/runtime/chan.go中(目前版本:1.11)。结构体为hchan。

    sunsky
  • 深入理解Threadlocal的实现原理

    文章开头我想说,这是一篇面向不怎么懂  Threadlocal 的朋友的博客,所以有的人会觉得有点啰嗦,但不论您水平高低,相信耐着性子看完也一定会有收获。

    矿泉水
  • <一>深入理解Threadlocal的实现原理

    文章开头我想说,这是一篇面向不怎么懂  Threadlocal 的朋友的博客,所以有的人会觉得有点啰嗦,但不论您水平高低,相信耐着性子看完也一定会有收获。

    用户2141593
  • 深入理解JDK中的Reference原理和源码实现

    这篇文章主要基于JDK11的源码和最近翻看的《深入理解Java虚拟机-2nd》一书的部分内容,对JDK11中的Reference(引用)做一些总结。值得注意的是...

    Throwable
  • 深入分析Volatile的实现原理

    在多线程并发编程中synchronized和Volatile都扮演着重要的角色,Volatile是轻量级的synchronized,它在多处理器开发中保证了共享...

    heasy3
  • 深入理解join方法的实现原理

    有几个方法都可以做到,这里主要是套路最简单的使用join方法,如何解决。 首先看join方法的API 这是随手百度的 : join()等待线程结束。

    矿泉水
  • 深入理解join方法的实现原理

    用户2141593
  • GDB实现原理和使用范例

    这篇文章为了让你深入了解gdb的工作原理,以及如何在linux环境下使用强大的gdb调试程序功能。

    mariolu
  • setTimeout实现原理和使用注意

    浏览器渲染进程中所有运行在主线程上的任务都需要先添加到消息队列,然后事件循环系统再按照顺序执行消息队列中的任务。

    winty
  • 深入解析 volatile 、CAS 的实现原理

    tomas家的小拨浪鼓
  • Go 语言并发编程系列(二)—— Go 协程实现原理和使用示例

    Go 语言的协程实现被称之为 goroutine,由 Go 运行时管理,在 Go 语言中通过协程实现并发编程非常简单:我们可以在一个处理进程中通过关键字 go ...

    学院君
  • 深入Go的错误处理机制(一)使用

    程序运行过程中不可避免的发生各种错误,要想让自己的程序保持较高的健壮性,那么异常,错误处理是需要考虑周全的,每个编程语言提供了一套自己的异常错误处理机制,在Go...

    阿伟
  • Go高阶11,手摸手带你深入了解 Mutex 实现原理

    互斥锁是对于并发程序的共享资源进行访问控制的主要手段,之前在介绍并发的时候已经对互斥锁的使用进行过介绍:并发控制,同步原语 sync 包

    微客鸟窝
  • Go高阶12,手摸手带你深入了解 RWMutex 实现原理

    之前我们介绍了互斥锁 Mutex,今天再来介绍下 RWMutex,即读写锁。读写锁是对 Mutex 的改进,在程序中,如果存在读操作多,写操作少的场景,使用 R...

    微客鸟窝
  • Go 并发编程 — 深入浅出 sync.Pool ,最全的使用姿势,最深刻的原理

    Go 并发相关库 sync 里面有一个有趣的 package Pool,sync.Pool 是个有趣的库,用很少的代码实现了很巧的功能。第一眼看到 Pool 这...

    KevinYan
  • go的websocket实现原理与用法详解

    本文实例讲述了go的websocket实现原理与用法。分享给大家供大家参考,具体如下: websocket分为握手和数据传输阶段,即进行了HTTP握手 + 双工...

    李海彬
  • go的websocket实现原理与用法详解

    本文实例讲述了go的websocket实现原理与用法。分享给大家供大家参考,具体如下: websocket分为握手和数据传输阶段,即进行了HTTP握手 + 双工...

    李海彬

扫码关注云+社区

领取腾讯云代金券