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


二 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的实现原理


go底层map到底怎么存储呢?接下来我们一探究竟。map的源码位于 src/runtime/map.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设计之巧妙。


27.png


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


28.png


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
}


相关文章
|
10月前
|
Go
go语言中遍历映射(map)
go语言中遍历映射(map)
214 8
|
2月前
|
存储 人工智能 安全
深入理解 go sync.Map - 基本原理
本文介绍了 Go 语言中 `map` 在并发使用时的常见问题及其解决方案,重点对比了 `sync.Mutex`、`sync.RWMutex` 和 `sync.Map` 的性能差异及适用场景。文章指出,普通 `map` 不支持并发读写,容易引发错误;而 `sync.Map` 通过原子操作和优化设计,在某些场景下能显著提升性能。同时详细讲解了 `sync.Map` 的基本用法及其适合的应用环境,如读多写少或不同 goroutine 操作不同键的场景。
117 1
|
4月前
|
存储 安全 Go
Map的遍历与判断键是否存在-《Go语言实战指南》
本文介绍了 Go 语言中对 `map` 的常见操作,包括遍历所有项和判断键是否存在。通过 `for range` 可以遍历 `map` 的键值对、仅键或仅值(需忽略键)。注意,`map` 遍历顺序是随机的。判断键是否存在时,使用双赋值语法 `value, ok := map[key]`,其中 `ok` 表示键是否存在。直接访问不存在的键会返回类型的零值,可能导致逻辑错误。掌握这些机制可更安全高效地处理键值对数据。
|
4月前
|
人工智能 安全 Go
Go语言中 Mutex 的实现原理
本文深入解析了 Go 中 `sync.Mutex` 的实现原理及其工作机制。`Mutex`(互斥锁)是并发编程中的基础同步机制,用于保护共享资源不被多个 Goroutine 同时访问。Go 的 `sync.Mutex` 通过轻量级的结构体实现,包含 `state` 和 `sema` 两个字段,分别用于表示锁状态和管理 Goroutine 的阻塞与唤醒。 文章详细分析了锁的获取(`Lock()`)和释放(`Unlock()`)过程,包括快速路径和慢速路径的实现逻辑。在慢速路径中,介绍了自旋锁优化、饥饿模式以及信号量机制的应用,确保高效且公平地管理锁竞争。
|
7月前
|
存储 缓存 安全
Go 语言中的 Sync.Map 详解:并发安全的 Map 实现
`sync.Map` 是 Go 语言中用于并发安全操作的 Map 实现,适用于读多写少的场景。它通过两个底层 Map(`read` 和 `dirty`)实现读写分离,提供高效的读性能。主要方法包括 `Store`、`Load`、`Delete` 等。在大量写入时性能可能下降,需谨慎选择使用场景。
|
8月前
|
存储 安全 Go
Go语言中的map数据结构是如何实现的?
Go 语言中的 `map` 是基于哈希表实现的键值对数据结构,支持快速查找、插入和删除操作。其原理涉及哈希函数、桶(Bucket)、动态扩容和哈希冲突处理等关键机制,平均时间复杂度为 O(1)。为了确保线程安全,Go 提供了 `sync.Map` 类型,通过分段锁实现并发访问的安全性。示例代码展示了如何使用自定义结构体和切片模拟 `map` 功能,以及如何使用 `sync.Map` 进行线程安全的操作。
209 9
|
9月前
|
Go
go语言for遍历映射(map)
go语言for遍历映射(map)
281 12
|
10月前
|
存储 Go
go语言 遍历映射(map)
go语言 遍历映射(map)
158 2
|
12月前
|
Go 定位技术 索引
Go 语言Map(集合) | 19
Go 语言Map(集合) | 19
|
Go
Go 语言学习之map
Go 语言学习之map
105 0