抱歉,您的瀏覽器無法訪問本站
本頁面需要瀏覽器支持(啟用)JavaScript
了解詳情 >

前言

map是Golang内置的一个键值对容器,在开发中经常用到同时API简单易用,那么它和其他语言的关于map的实现有什么不同吗?下面就来学习一下~

简单使用

初始化
1
2
3
4
5
6
7
8
9
10
11
// 声明一个map,为引用类型的零值nil
var m map[Key]Value
// 创建map的字面量
m := map[Key]Value{}
// 使用多个值对map进行初始化
m := map[string]int {
"Jerry": 1,
"Tom": 2,
}
// 使用make创建
m := make(map[Key]Value)
CRUD
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
m := map[string]int{}
// 赋值
m["Tom"] = 123
// 修改
m["Tom"] = 456
// 删除
delete(m, "Tom")
// 获得对应键的值
num:=m["Tom"]
// 判断对应键是否存在
if _, ok := m["Tom"]; ok {
// TODO
}
// 遍历map
for key, value := range m {
// TODO
}

需要注意Key需要是可比较类型,即能够使用==操作符进行比对的类型,像mapslicefunction等都是不行的。 同时map类型也是线程不安全的,如果有多线程同时进行操作的话,可以使用RWMutex或者sync.map来保证线程安全。

原理

Golang主要使用bmaphmap两个结构体来实现map类型,同时不像Java只使用链表/红黑树来解决hash冲突,而是主要使用数组来解决。

hmap结构

1
2
3
4
5
6
7
8
9
10
11
12
// A header for a Go map.
type hmap struct {
count int // 键值对的数量
flags uint8
B uint8 // 2^B=len(buckets)
noverflow uint16 // 溢出桶里bmap大致的数量
hash0 uint32 // 哈希种子
buckets unsafe.Pointer // 指向一个数组类型为[]bmap的指针,即指向真正存放数据的桶
oldbuckets unsafe.Pointer // 扩容时,存放之前的buckets(Map扩容相关字段)
nevacuate uintptr // 分流次数,成倍扩容分流操作计数的字段(Map扩容相关字段)
extra *mapextra // 额外桶结构,主要负责解决hash冲突的问题
}

bmap主要结构

字段 解释
topbits 类型为[]uint8,存放key获取的hash的高8位,遍历时对比使用,为了提高性能
key 具体key的数组
elems 具体value得数组
overflow 指向的hmap.extra.overflow溢出桶里的bmap,上面的字段topbitskeyselems长度为8,最多存8组键值对,存满了就往指向的这个bmap里存

主要逻辑大致如图

图片

当bmap里存放满8位键值对,便会尝试使用overflow扩展[]bmap,来处理hash冲突的问题,当overflow对应的[]bmap也满的时候便会进行扩容。

学习资料