golang-学习笔记-Map

2022-12-11 1903 words 4 minutes

Contents

在写过很多go代码之后，感觉自己并没有完全掌握go语言，还有很多知识盲区，所以有了这个go学习笔记系列，本系列是作者跟着电子书重新复习go语言相关内容的笔记

声明、初始化和 make

概念

1
2


var map1 map[keytype]valuetype
var map1 map[string]int

未初始化的 map 的值是 nil。

key 可以是任意可以用 == 或者 != 操作符比较的类型，比如 string、int、float。数组、切片不能作为 key。含有数组切片的结构体不能作为 key，只包含内建类型的 struct 是可以作为 key 的。指针和接口类型可以。如果要用自定义结构体作为 key 需要提供 Key() 和 Hash() 方法，这样可以通过结构体的域计算出唯一的数字或者字符串的 key。

value 可以是任意类型的；通过使用空接口类型，我们可以存储任意值，但是使用这种类型作为值时需要先做一次类型断言

map 传递给函数是引用传递：在 32 位机器上占 4 个字节，64 位机器上占 8 个字节，无论实际上存储了多少数据。通过 key 在 map 中寻找值是很快的，比线性查找快得多，但是仍然比从数组和切片的索引中直接读取要慢 100 倍；所以如果你很在乎性能的话还是建议用切片来解决问题。

map 也可以用函数作为自己的值，这样就可以用来做分支结构

map 是引用类型的：内存用 make 方法来分配。

map 的初始化：

1
2
3


var map1 = make(map[keytype]valuetype)

map1 := make(map[keytype]valuetype)

不要使用 new，永远用 make 来构造 map。如果你错误的使用 new() 分配了一个引用对象，你会获得一个空引用的指针，相当于声明了一个未初始化的变量并且取了它的地址。

map 容量

make(map[keytype]valuetype, cap)

用切片作为 map 的值

1
2


mp1 := make(map[int][]int)
mp2 := make(map[int]*[]int)

测试键值对是否存在及删除元素

1
2
3
4
5
6
7
8



val1, isPresent = map1[key1]

_, ok := map1[key1] // 如果key1存在则ok == true，否则ok为false

if _, ok := map1[key1]; ok {
    // ...
}

删除 key1：delete(map1, key1)

如果 key1 不存在，该操作不会产生错误。

for-range 的配套用法

1
2
3
4
5
6
7


for key := range map1 {
    ...
}

for key, value := range map1 {
    ...
}

map 类型的切片

想获取一个 map 类型的切片，我们必须使用两次 make() 函数，第一次分配切片，第二次分配切片中每个 map 元素

1
2
3
4
5


items := make([]map[int]int, 5)
for i:= range items {
    items[i] = make(map[int]int, 1)
    items[i][1] = 2
}

map 的排序

map 默认是无序的

想为 map 排序，需要将 key（或者 value）拷贝到一个切片，再对切片排序（使用 sort 包），然后可以使用切片的 for-range 方法打印出所有的 key 和 value。

将 map 的键值对调

1
2
3
4


invMap := make(map[int]string, len(barVal))
for k, v := range barVal {
    invMap[v] = k
}

map有容量限制吗

map没有容量限制，在达到容量上限后会自动扩容

map底层实现

https://static.sitestack.cn/projects/GoExpertProgramming/chapter01/images/map-02-struct_sketch.png

type hmap struct

属性

count int：当前保存的元素个数
B uint8：表示buckets数组大小，每个bucket的索引占的位数，数组大小为2^B
buckets unsafe.Pointer：buckets数组的指针

buckets内存块

一块连续的内存，类似数组，索引为hash值的低地址，对应B位

type bmap struct（bucket）

bucket也称桶，哈希桶

属性

tophash [8]unint8：存储哈希值的高8位
data byte[1]：键值对数据
overflow *bmap：溢出的bucket地址，链地址处理哈希冲突

哈希冲突

https://static.sitestack.cn/projects/GoExpertProgramming/chapter01/images/map-03-struct_sketch.png

负载因子

负载因子 = 键数量/bucket数量

渐进式扩容

https://static.sitestack.cn/projects/GoExpertProgramming/chapter01/images/map-05-struct_sketch.png

触发条件

负载因子 > 6.5时
overflow数量 > 2^15

渐进式rehash都使用了hmap的oldbuckets字段

增量扩容

当负载因子过大时，就新建一个buckets数组，新的buckets长度是原来的2倍，然后旧buckets数据搬迁到新的buckets

等量扩容

buckets不变，重新做一遍类似增量扩容的搬迁动作，把松散的键值对重新排列一次，因为map在删除时会导致某些bucket里面有空值，等量扩容就是为了把这些空值处理掉

查找过程

算出查询key的hash值
取低位找到bucket位置
取高位在tophash中找存储key对应的位置
比较存储key和查询key，如果不相等到下一个overflow bucket中找
搬迁过程从oldbuckets找

插入过程

算出插入key的hash值
查询是否有该值，有就修改value，没有就插入新的kv对

对不存在的key查询

当map的key不存在的时候，它的返回值为这个类型的默认返回值。

由此可以引申出，对于查询kv对后在原来的基础上进行修改的map，可以不判断是否存在直接赋值

比如统计一串数字中每种数字的个数

1
2
3


m:=map[int]int

for _,v := range nums{m[v]++}

map不能直接等号比较

map不能直接等号比较，但是可以使用reflect.DeepEqual函数进行逐个元素比较

获取所有的key

1
2
3
4
5


keys := make([]int,0, len(m))
for k := range m {
  keys = a
  j++
}

不要把结构体作为值

不要把结构体作为map的值，因为结构体是值类型，当结构体进行赋值运算时会将每个字段进行拷贝，而且无法对结构体的值进行修改，因为你调用map[i]时会进行赋值运算，且结果是右值，即只读

可以把结构体指针作为map的值

另外将结构体或者数组作为键可以快速比对是否具有该键