专栏首页从流域到海域Go Map(集合)和sync.Map

Go Map(集合)和sync.Map

Go中的Map对应的数据结构即为哈希表,但它的中文翻译却是集合,这点需要注意。我个人觉得翻译成集合错的很离谱,应该直译成映射。

Go语言中的Map是一种无序的键值对集合。Map可以通过key在O(1)的时间复杂度内进行查询、更改、删除操作,key到value间的映射由哈希函数实现。Go的Map相当于C++的Map,Java的HashMap,Python的Dict

使用方式类Python的Dict,可以直接map[key]的形式访问元素,直接使用map[key] = vaule赋值形式添加新的元素或对已有的key对应的value进行修改。

声明和初始化语法:

// 标准声明方法 cap可选
var map_variable map[key_data_type]value_data_type
map_variable = make([key_data_type]value_data_type, [cap])
// 或者使用make函数 声明时直接初始化 cap可选
map_variable := make([key_data_type]value_data_type [cap])

实例:

package main

import (
	"fmt"
)

func main() {

	// var personIdMap = map[string][int64]
	// personIdMap = make(map[string]int64)
	// 未经make函数初始化的map默认为nil 是不能插入元素的
	// 因此推荐大家使用下面的写法

	personIdMap := make(map[string]int64)

	personIdMap["Steve"] = 51184623145
	personIdMap["Jason"] = 52374651251
	personIdMap["Mike"]  = 51326545454

	for name, id := range personIdMap {
		fmt.Printf("%s对应的id是%d\n", name, id)
	}

	personIdMap["Steve"] = 51184504562
	fmt.Printf("%s对应的id是%d\n", "Steve", personIdMap["Steve"])

	fmt.Printf("%s对应的id是%d\n", "Tim", personIdMap["Tim"])
}

// Steve对应的id是51184623145
// Jason对应的id是52374651251
// Mike对应的id是51326545454
// Steve对应的id是51184504562
// Tim对应的id是0

如果Map中没有存储某键值对,那么得到的是nil对应的零值,上面的例子也有体现。

delete()

Go语言中内置了delete()函数用于删除集合中的元素,使用上需要以map和要删除的key作为参数。

实例:

package main

import (
	"fmt"
)

func main() {

	// var personIdMap = map[string][int64]
	// personIdMap = make(map[string]int64)
	// 未经make函数初始化的map默认为nil 是不能插入元素的
	// 因此推荐大家使用下面的写法

	personIdMap := make(map[string]int64)

	personIdMap["Steve"] = 51184623145
	personIdMap["Jason"] = 52374651251
	personIdMap["Mike"]  = 51326545454

	for name, id := range personIdMap {
		fmt.Printf("%s对应的id是%d\n", name, id)
	}

	fmt.Println()
	delete(personIdMap, "Mike")

	for name, id := range personIdMap {
		fmt.Printf("%s对应的id是%d\n", name, id)
	}
}

// Steve对应的id是51184623145
// Jason对应的id是52374651251
// Mike对应的id是51326545454
// 
// Steve对应的id是51184623145
// Jason对应的id是52374651251

源码

map定义的源码如下:

type bmap struct {
	tophash  [8]uint8
	data     byte[1]
	overflow *bmap 
}
type mapextra struct {
	overflow    *[]*bmap
	oldoverflow *[]*bmap
	nextOverflow *bmap
}

type hmap struct {
	count     int
 	flags     uint8  
 	B         uint8
 	noverflow uint16
 	hash0     uint32
 	buckets    unsafe.Pointer
 	oldbuckets unsafe.Pointer
 	nevacuate  uintptr
 	extra *mapextra
}

通过源码可以看出,它Java的HashMap的实现,还是有很大差别的。

Map哈希冲突解决

当两个或者两个以上的元素被放在同一个bucket中,表示已经发生了哈希冲突。由于一个bucket最多储存8个键值对,bucket已满时会创建新的bucket,然后将旧的bucket和新的bucket使用链表连接起来,overflow存的即为新的bucket的地址。

Map扩容机制

Go语言的Map与Java的HashMap一样,支持定义时设定初始容量,支持动态扩容。

map_variable := make([key_data_type]value_data_type, cap)

负载因子load factor,用途是评估哈希表当前的时间复杂度,其与哈希表当前包含的键值对数、桶数量等相关。如果负载因子越大,则说明空间使用率越高,但产生哈希冲突的可能性更高。而负载因子越小,说明空间使用率低,产生哈希冲突的可能性更低

G语言Map的负载因子计算公式如下:

loadfactor = key_num / bucket_num

默认的负载因子设置为6.5

除了负载因子,Go语言还有溢出桶的概念。结合源码我们发现,每个桶最多可以存储8个元素,如果超过8个,会使用定义相同的溢出桶来存储或者扩容。溢出桶overflow buckets过多的判定有一个固定值的阈值2^15 = 32768

Map的扩容原理

扩容的触发条件包括两个:

  • 触发loadfactor的最大值,负载因子已达到当前界限。 这种情况表示容量不足,直接扩容为原来大小的二倍
  • 溢出桶overflow buckets过多 这种情况指的是桶分配了很多,但实际用到的桶的数量很少,即key过于分散,这时扩容指的是内存整理,把相近的key集中到一个桶,给另外的桶腾出空间。

扩容伴随着数据迁移,Go语言的map采用的是渐进式迁移的策略,不是一次性迁移所有的数据,每次最多移动两个桶,每次调用增删改都会查看是否迁移完毕,如果没有迁移完毕就尝试继续搬迁。渐进式迁移能使得数据迁移的均摊时间复杂度降低到O(1)。

切片作为map的值

特别注明,Go语言中可以使用切片作为map的值,这种情况下一个key对应多个value。

sync.Map

Go语言中的Map同样不是线程安全的。Go所提供的线程安全的版本是位于sync包下的Map。

如果并发地读写普通的Map,会报错误fatal error: concurrent map read and map write,map内部会对并发操作进行检查并提前发现。

你可以在Map上加锁,但这样性能不高。Go语言在1.9版本提供了效率较高的sync.Map

sync.Map有以下特性:

  • 无需初始化,直接声明即可使用
  • sync.Map不能像map那样读写,而是使用sync.Map提供的方法,Store(key, value)用于存储,Load(key)用于取值,Delete(key)表示删除。
  • 遍历操作需要使用Range()函数配合一个回调函数,通过回调函数返回内部遍历出来的值。range参数中回调函数的返回值在需要继续迭代遍历时,返回true,终止迭代遍历时,返回false。

如果成功读取Load()函数返回两个值,key对应的value以及ture表示成功读取;如果map中没有这个key,则返回nil表示失败的false

实例如下:

package main

import (
	"fmt"
	"sync"
)

func main() {
	var capId sync.Map

	capId.Store("Beijing", 88)
	capId.Store("London", 80)
	capId.Store("Tokyo", "89") // 注意value是字符串

	fmt.Println(capId.Load("Beijing"))
	fmt.Println(capId.Load("Tokyo"))

	fmt.Println()

	value, _ := capId.Load("Beijing")
	fmt.Println(value)

	fmt.Println()

	capId.Delete("Tokyo")
	capId.Range(func(k, v interface{}) bool {
		fmt.Printf("%s对应的id是%d\n", k, v)
		return true
	})
}

// 88 true
// 89 true
// <nil> false
// 
// 88
// 
// Beijing对应的id是88
// London对应的id是80

从该例可以看出,sync.Map因为没有初始化过程,无法指定key和value的数据类型,所以干脆就支持了所有的数据类型。它不限制一个map内所有的key和value都必须是相同的类型。

参考文献

深入理解 Go map:赋值和扩容迁移

Go map实现原理

Go语言sync.Map(在并发环境中使用的map)

本文参与 腾讯云自媒体分享计划 ,欢迎热爱写作的你一起参与!
本文分享自作者个人站点/博客:http://blog.csdn.net/solo95复制
如有侵权,请联系 cloudcommunity@tencent.com 删除。
登录 后参与评论
0 条评论

相关文章

  • 深入Go:sync.Map

    我们在使用Go的项目中需要有并发读写的map时,我们了解到Go提供sync.Map这一数据结构;通过对其简单了解,发现它正好适合我们需要的场景。随着了解的深入,...

    wenxing
  • Go 1.9 sync.Map揭秘

    目录 [−] 有并发问题的map Go 1.9之前的解决方案 sync.Map Load Store Delete Range sync.Map的性能 其它 在...

    李海彬
  • map和sync.map基准测试

    在基准测试中,在并发安全的情况下sync.Map会比我们常用的map+读写锁更加的快,快了五倍,这是得以于只读read设计,减低锁的粒度。但是利用读写锁的话,我...

    用户7962184
  • 灰子的Go笔记:sync.Map

    在golang中map不是并发安全的,所有才有了sync.Map的实现,尽管sync.Map的引入确实从性能上面解决了map的并发安全问题,不过sync.Map...

    灰子学技术
  • 深度解密Go语言之sync.map

    工作中,经常会碰到并发读写 map 而造成 panic 的情况,为什么在并发读写的时候,会 panic 呢?因为在并发读写的情况下,map 里的数据会被写乱,之...

    梦醒人间
  • Go 语言Map(集合)

    Map 是一种无序的键值对的集合。Map 最重要的一点是通过 key 来快速检索数据,key 类似于索引,指向数据的值。 Map 是一种集合,所以我们可以像迭代...

    李海彬
  • Go - 使用 sync.Map 来解决 map 的并发操作问题

    在 Golang 中 map 不是并发安全的,自 1.9 才引入了 sync.Map ,sync.Map 的引入确实解决了 map 的并发安全问题,不过 syn...

    新亮
  • 手摸手Go 深入浅出sync.Map

    日常开发过程中,map结构应该登场率是较为频繁的。但是Go的内建map类型并不是协程安全的。如下面这个栗子,如果业务开发过程中不注意很容易中招。

    用户3904122
  • 【Go 语言社区】Go 语言Map(集合)

    Go 语言Map(集合) Map 是一种无序的键值对的集合。Map 最重要的一点是通过 key 来快速检索数据,key 类似于索引,指向数据的值。 Map 是一...

    李海彬
  • 看过这篇剖析,你还不懂 Go sync.Map 吗?

    本篇文章会从使用方式和源码角度剖析 sync.Map。不过不管是日常开发还是开源项目中,好像 sync.Map 并没有得到很好的利用,大家还是习惯使用 Mute...

    haohongfan
  • go: 当我们在使用sync.Map时,发生了什么

    sync.Map是我比较喜欢的一个库,用了非常久,今天突发奇想瞧瞧它的实现。又一次被宇宙中第二NB的语言--go 折服了。 这里准备写一篇文章,讨论下当使用s...

    超级大猪
  • Go语言中的map(集合)操作

    1.map的声明和map的初始化非同一个概念。未初始化的map是nil,nil的map不允许往里面添加值,否则会出现(panic: assignment to ...

    似水流年o
  • 快速掌握 Go 语言中的集合(map)

    我本来下午打算对新系统,好好研究下模块划分,但因为上一个版本提测,于是我改了一个下午的bug。

    机智的程序员小熊
  • Go基础系列 | 9. 内置集合 - map

    map 是一种键(key)/值(value)对的无序集合,在其它语言中称为字典、关联数组、哈希表等。当给定了键可以快速定位到值,而且键必须唯一的,不能出现相同。

    潇洒哥和黑大帅
  • 集合详解(一)----Collection和Map接口

    在我们编程的时候,有时候需要集中存放多个数据,可以用数组来保存多个数据,但是数组的长度是不可变的,一旦数组的长度确定了之后就无法再改变,如果要保存可变长度的数...

    令仔很忙
  • Java的map和Go的map的区别

    我们先说Java 的HashMap 跟Go map的实现的共同点,1.都是利用 键值对的 key 得到一个 hashCode,算出桶的位置,什么是桶 其实就是一...

    人生海海山山而川
  • 集合下篇—Map和Set 源码分析

    这篇博客主要讲集合的,哈希表这样的数据结构就不说明了,后期会补充哈希表,红黑树这样的博文

    晚上没宵夜
  • go基础之--函数和map

    在整理函数之前先整理一下关于指针 指针 普通类型变量存的就是值,也叫值类型。指针类型存的是地址,即指针的值是一个变量的地址。 一个指针指示值所保存的位置,不是所...

    coders
  • go的map和range的使用

    package main import( "fmt" ) func main(){ //声明map,map其实就是hashmap的实...

    公众号-利志分享

扫码关注腾讯云开发者

领取腾讯云代金券