map在go面试中几乎成了必问题了,哈哈,这里可以要把‘几乎’去掉。而且问题集中在map的底层实现,无序遍历等问题上,那么就结合map引申出一些常见的知识点汇总,当然这些都可以在网上找到一大把答案。
func main() {
var m map[string]string
m["nice"]="boy"
}
输出:
panic: assignment to entry in nil map
map只进行声明的话是个nil map,不能直接赋值
func main() {
var m map[string]string
value := m["nice"]
fmt.Println(value)
}
如果获取一个不存在的 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是非线程安全性的,并发读写(都是写或者读写一起)会报错,但是只读是线程安全的,这里我们可以使用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扩容(自动扩容和重新hash所有的key以便存储更多的数据)后,可能会将部分key移至新内存,即使没有扩容,map在遍历时加上随机的元素,将遍历 map 的顺序随机化。
写数据时,并没有单独维护键值对的顺序,成倍扩容迫使元素顺序变化,等量扩容并没有改变元素顺序。
其实就是Go的设计者们就对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是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 的实现原理可概括为:
因此,sync.map中冗余的数据结构就是dirty和read,二者存放的都是key-entry,entry其实是一个指针,指向value,read和dirty各自维护一套key,key指向的都是同一个value,也就是说,只要修改了这个entry,对read和dirty都是可见的。
map的底层实现是一个散列表,因此实现map的过程实际上就是实现散表的过程。在这个散列表中,主要出现的结构体有两个,一个叫hmap(a header for a go map),一个叫bucket,使用链地址法解决哈希冲突。
编辑切换为居中
map结构图(出自孙同学)
如果延展开来的话,说map的底层实现,如何实现扩容,值的存储等是一个很大的知识内容点,需要单独拿开来讲会更好,这里用图把结构先简单标记一下。
参考文档:
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。