Golang-map、sync.map知识点汇总
map在go面试中几乎成了必问题了,哈哈,这里可以要把‘几乎’去掉。而且问题集中在map的底层实现,无序遍历等问题上,那么就结合map引申出一些常见的知识点汇总,当然这些都可以在网上找到一大把答案。
关于map的一些知识点
- map 是一种无序的键值对的集合。
- map最重要的一点是通过key来快速检索数据,key类似于索引,指向数据的值。
- map是一种集合,因此我们可以像迭代数组和切片那样迭代它。不过,map是无序的,我们无法决定它的返回顺序
- map是引用类型
- map 初始化方式 make 或者短变量方式声明初始化一起
map常见的几个问题
map未初始化,赋值会panic
func main() {
var m map[string]string
m["nice"]="boy"
}
输出:
panic: assignment to entry in nil map
map只进行声明的话是个nil map,不能直接赋值
nil map可以取值,得到的是零值
func main() {
var m map[string]string
value := m["nice"]
fmt.Println(value)
}
map取值结果可以是一个值,也可以是两个值
如果获取一个不存在的 key 对应的值时,会返回零值。为了区分真正的零值和 key 不存在这两种情况,可以根据第二个返回值来区分键值是否存在,而且第二个返回值通常用 'ok' 来表示。
func main() {
var m = make(map[string]int)
m["a"] = 0
fmt.Printf("a=%d;b=%d\n",m["a"],m["b"])
a,oka:=m["a"]
b,okb:=m["b"]
fmt.Printf("a=%d,oka=%t;b=%d,okb:%t\n",a,oka,b,okb)
}
输出:
a=0;b=0
a=0,oka=true;b=0,okb:false
Map非线程安全,并发读写会报错
map是非线程安全性的,并发读写(都是写或者读写一起)会报错,但是只读是线程安全的,这里我们可以使用sync.map,利用了空间换时间的方式,后面我们会讲讲为什么sync.map支持并发读写。
func main() {
c := make(map[string]int)
go func() { //开一个goroutine写map
for j := 0; j < 1000000; j++ {
c[fmt.Sprintf("%d", j)] = j
}
}()
go func() { //开一个goroutine读map
for j := 0; j < 1000000; j++ {
fmt.Println(c[fmt.Sprintf("%d", j)])
}
}()
time.Sleep(time.Second * 20)
}
fatal error: concurrent map read and map write
goroutine 19 [running]:
runtime.throw(0x10d6ea4, 0x21)
/usr/local/go/src/runtime/panic.go:774 +0x72 fp=0xc00009aef0 sp=0xc00009aec0 pc=0x10299c2
runtime.mapaccess1_faststr(0x10b41e0, 0xc000066180, 0x116ae71, 0x1, 0x1)
/usr/local/go/src/runtime/map_faststr.go:21 +0x44f fp=0xc00009af60 sp=0xc00009aef0 pc=0x100ffff
main.main.func2(0xc000066180)
map遍历为啥是无序的
当我们对map进行遍历时,每次遍历的输出的值顺序都可能不一样,顺序不固定。主要是因为map扩容(自动扩容和重新hash所有的key以便存储更多的数据)后,可能会将部分key移至新内存,即使没有扩容,map在遍历时加上随机的元素,将遍历 map 的顺序随机化。
写数据时,并没有单独维护键值对的顺序,成倍扩容迫使元素顺序变化,等量扩容并没有改变元素顺序。
其实就是Go的设计者们就对map增加了一种随机性,以确保开发者在使用map时不依赖于有序的这个特性。
如何让map顺序读取
我们知道map遍历时无序的,我们可以先把map中的key,通过sort包对slice排序,通过sort中的排序包进行对map中的key进行排序。
package main
import (
"fmt"
"sort"
)
func main() {
var m = map[string]int{
"hello": 0,
"nice": 1,
"boy": 2,
}
var keys []string
for k := range m {
keys = append(keys, k)
}
sort.Strings(keys)
for _, k := range keys {
fmt.Println("Key:", k, "Value:", m[k])
}
}
sync.map为啥支持并发读写,咋实现的
sync.map是Go1.9发布的一个新特性,它是原生支持并发安全的map,不过使用和map完全不同,因为实现的底层数据结构都不同。
sync.map主要有以下方法
//通过提供一个键key,查找对应的值value,
//如果不存在,则返回nil。ok的结果表示是否在map中找到值
func (m Map) Load(key interface{}) (value interface{}, ok bool)
//写map(更新或新增),第一个参数是key,第二个参数是value
func (m Map) Store(key, value interface{})
//遍历读取sync.map中的值
func (m Map) Range(f func(key, value interface{}) bool)
好现在重点来了,我们知道了sync.map的特性和使用方式,那么到底是怎么实现并发读写的呢,先看sync.map的结构
// Map 并发安全的map结构体
type Map struct {
mu sync.Mutex // 锁,保护read和dirty字段
// 存仅读数据,原子操作,并发读安全,实际存储readOnly类型的数据
read atomic.Value
// 存最新写入的数据
dirty map[interface{}]*entry
// 计数器,每次在read字段中没找所需数据时,+1
// 当此值到达一定阈值时,将dirty字段赋值给read
misses int
}
// readOnly 存储mao中仅读数据的结构体
type readOnly struct {
// 其底层依然是个最简单的map
m map[interface{}]*entry
// 标志位,标识m.dirty中存储的数据是否和m.read中的不一样,flase 相同,true不相同
amended bool
}
sync.Map 的实现原理可概括为:
- 1、过 read 和 dirty 两个字段将读写分离,读的数据存在只读字段 read 上,将最新写入的数据则存在 dirty 字段上
- 2、读取时会先查询 read,不存在再查询 dirty,写入时则只写入 dirty
- 3、读取 read 并不需要加锁,而读或写 dirty 都需要加锁
- 4、另外有 misses 字段来统计 read 被穿透的次数(被穿透指需要读 dirty 的情况),超过一定次数则将 dirty 数据同步到 read 上
- 5、对于删除数据则直接通过标记来延迟删除
因此,sync.map中冗余的数据结构就是dirty和read,二者存放的都是key-entry,entry其实是一个指针,指向value,read和dirty各自维护一套key,key指向的都是同一个value,也就是说,只要修改了这个entry,对read和dirty都是可见的。
map的实现
map的底层实现是一个散列表,因此实现map的过程实际上就是实现散表的过程。在这个散列表中,主要出现的结构体有两个,一个叫hmap(a header for a go map),一个叫bucket,使用链地址法解决哈希冲突。
编辑切换为居中
map结构图(出自孙同学)
如果延展开来的话,说map的底层实现,如何实现扩容,值的存储等是一个很大的知识内容点,需要单独拿开来讲会更好,这里用图把结构先简单标记一下。
参考文档:
相关文章
- java 把对象转成map_Java对象转换成Map[通俗易懂]
- list对象转map[通俗易懂]
- java map 二维数组_Java二维数组实现简单Map
- java map循环遍历_遍历循环中的遍历结构可以是
- 推荐系统常用指标(续):MRR、MAP、HR、F-score
- MAP遍历_map容器遍历
- Map和Set的区别「建议收藏」
- es6 set和map_数据结构什么叫度
- 一文了解source-map
- map遍历方式及效率_java遍历map集合
- go的数据类型-复合数据类型-map(一)
- MySQL Error number: MY-013759; Symbol: ER_GRP_RPL_ADD_VIEW_CHANGE_UUID_TO_GRP_SID_MAP_ERROR; SQLSTATE: HY000 报错 故障修复 远程处理
- Oracle 视图 RESOURCE_MAP 官方解释,作用,如何使用详细说明
- Redis精准读取Map数据的窍门(redis获取map)
- 深入浅出Redis查看Map(redis查看map)
- 从Redis中取出Map一步搞定(从redis中取map)
- 科学上网如何使用Oracle MAP(oracle map使用)
- 学会调整Redis中Map容量的设置(redis设置map大小)