Go语言的map详细总结（第一篇）

map是一种几乎每一门编程语言都有的数据结构，他是一组key–value组成的数据结构。Go语言的map和python中的dict的作用类似，它是一种数据结构用来维护一个集合的数据，并且可以对这个集合进行增删查改的操作。Go语言的map采用的数据结构：
哈希表（hash table）。在很多场景下哈希表性能很高，哈希查找表最坏的时间复杂度是O（n），平均查找效率是O（1），如果哈希函数设置得合理最坏得情况不会出现。

1.map的底层数据结构及查询机制

1.1 底层结果

map的底层是一个hmap结构体，该结构体包含的字段如下图所示：

该结构体中一些关键的字段为，count为现在map中装入的键值对数量，buckets是一个指向桶数组的指针，B表示桶的数量的对数，例如B=3，则普通桶的数量则有8个，但是在对map进行初始化的时候会设几个溢出桶。

每个桶是一个bamp结构体。 bamap中含有hash值的高8位（tophash），含有key和value的数组，还有一个overflow指针，指向的是溢出桶。每个桶中可以存储8个k–v的数据，如果桶装满了，则超出的数据装入溢出桶中。

key和value分开存储的原因，主要是出于内存对齐的考虑，分开存储可以节省内存空间。
例如：map[int64]int8，这样的map如果采用的是key/value/key/value这样的结构存储的话，则每对key/value后面都要额外的填充7个字节，为了进行内存对齐，这样无疑是对内存空间的巨大浪费。如果采用的是key和value分开存储的话，则不用考虑内存对齐的问题。

1.2map的创建和key的删除

1. 创建方法1

var m map[int]bool    // 此时的m == nil
fmt.Println(m == nil) // true

注意，这样方式创建的map是nil，如果往这个map中添加元素会panic

var m map[int]bool    // 此时的m == nil
fmt.Println(m == nil) // true
m[1] = true // panic

var m map[int]bool    // 此时的m == nil
fmt.Println(m == nil) // true
//m[1] = true            // panic
m = map[int]bool{1: true} // 不会panic

2. 创建方法2

通过make创建map。通过make创建的map可以往其中添加元素。

m2 := make(map[int]bool)  // 创建一个长度为0的空map
fmt.Println(m2 == nil) // false

m3 := make(map[int]bool, 10) // 创建一个长度为10的空map
fmt.Println(m3 == nil)       // false

3. 创建一个hashset，只有key没有value，在有一些应用场景中我们只需要获取key而不需要知道value，这时候可以采用空结构体创建一个hashset，节省内存空间，因为空结构体是不占用内存空间的。

hashSet := make(map[string]struct{}, 2) // 创建一个长度为2的hashset

4. 删除某个键值采用delete函

myMap := make(map[string]int, 5)
myMap["a"] = 1
myMap["b"] = 2
fmt.Println(myMap["a"]) // 1
// 删除掉key = a这个键值
delete(myMap,"a") // 传入两个参数，第一个参数是，指定删除的map，第二个是map中的key

1.3 map底层如何定位到某个key值

查找某个键值：

1. 首先计算Key的哈希值，如果是64位机器则得到的哈希值则是64位，如果是32位则哈希值则是32位。
2. 然后通过计算出来的哈希值，通过哈希值的后B位（B hmap结构体中的字段）计算出key要落在哪个bucket中。
3. 找到key落在哪个桶后，再通过哈希值的高八位找到key在bucket中槽位。如果槽位中的key是我们需要的key则说明定位了到了key的位置，如果不是则遍历所有的槽位（包括溢出桶）找到和key高八位相对应的槽位，找到我们所需要的key。

插入或修改键值：
4. 在进行插入操作的时候，如果先计算哈希值的后B位，取到该key要去的桶号。
5. 然后取key的哈希值的高八位，如果key是第一个元素则将该元素的tophash放在第一个槽位。
6. 如果不是第一个key，从前往后遍历查找是否有和key高八位一样的tophash槽位已经被占据，如果找到了key高八位的槽位，对比槽中的元素的key是否是我们要插入的key，如果是，则修改value。如果不是，则往后继续寻找。
7. 如果遍历完所有的槽位都没找到key，说明当前要插入的key在map中不存在，则找到一个空闲的槽位，插入tophash、key和value

1.4遍历的无序性

Go语言中对map的遍历是无序的，遍历map的时候并不是固定从00好桶开始遍历的，而是每次都从一个随机的桶开始，并且从这个桶中随机的一个cell开始遍历。

2.Go语言解决哈希碰撞的方法

因为根据后B个bit位决定key落入的桶编号，因此肯定会存在冲突。当两个不同的key落在同一个桶中，也就是发生了哈希冲突。Go语言中解决冲突的办法是采用链表法：再桶中从前往后找到第一个空位，放入新加入的有冲突的key。之后再查找某个key的时候，先找到对应的桶，再去遍历桶中的所有key。

3.map的扩容机制

3.1. map跨容的条件

在map.go中的mapassign函数（插入数据的函数）中，会判断是否进行跨容。

1. key-value太多：装载因子超过6.5（平均每个槽装了6.5个k-v）
2. 桶的数量太多，但是k-v少：太多的溢出桶，桶多数据少，造成资源的浪费和查找开销大

3.2. map的扩容方式：

1. 容量扩大（翻倍扩容）：将B的值加一，将桶的数量变为原来的两倍。开辟一个两倍大小的新的空间，将旧桶的数据迁移到新桶。
2. 等量扩容（整理）：桶的数量多，只是数据分散，重新开辟相同大小的空间，将旧桶的数据迁移到新桶整理使得数据变得更加紧凑。

3.3 map的扩容机制：

翻倍扩容机制：
（1）hmap的结构体中的oldbuckets字段指向原来的旧桶，buckets字段指向新的桶。

（2）采用渐进式的迁移方案，不是一次性将所有旧桶的数据迁移到新桶中，而是每次最多只搬迁两个桶。每次操作旧桶的时候就将旧桶中的数据迁移到新桶，也即在进行插入、删除、修改操作的时候会检查旧桶并对数据进行搬迁。只进行读取操作的时候不会对旧桶的数据进行搬迁。

（3）hashGrow的函数只是申请了新的桶的空间，并没有对数据进行搬迁，对数据进行搬迁的动作是在growWork函数中，在进行插入、修改、删除的操作的时候会先检查是否搬迁完。

（4）将旧桶中的数据计算哈希值，取哈希值得后B位，新map得B比老得map得B要多一位，增加了一位高位，所以新的key要么桶号是原来的，要么是新的桶号。比如原来B = 2，某个key的后B位为10，指向2号桶，现在扩容后B = 3，同样的key如果后B位为110，则表示该k-v落在6号桶，如果后B位为010则仍然落在2号桶中。**可以将老桶的数据一分为二分配到新的桶中，可以将同一个桶中的数据分散的迁移到不同的桶中。**如果只是等量扩容，则对桶中的数据进行整理即可。

（5）所有旧桶的数据迁移完后，回收旧桶。

4.Go语言的map是线程安全的嘛？

map不是线程安全的，在查找、赋值、遍历、删除的过程中都会先检查写标志，一旦发现写标志位等于1，则直接panic。赋值和删除函数在检查完写标志位是复位状态（等于0）之后，先将写标志位置位（置为1）才会进行赋值和删除的操作。

解决map的并发安全问题：
解决并发读写map的思路是加锁，或者把一个map切分成若干个小map(采用分段map)，对key进行哈希。
使用最多并发模式是：

1. map+互斥锁或者读写锁
2. 使用标准库sync.Map

Go语言的自带的并发安全sync.Map将在下一篇中进行详细分析！

5.如何比较两个map是否相等

只能是遍历map中的每个元素，比较元素是否都是深度相等。

map深度相等的条件：

（1）都为nil

（2）非空，长度相等，指向同一个map实体对象

（3）相应的key指向的value“深度”相等

6.为什么map数据结构的查询效率高

因为map在存储数据的时候给数据加上了一个索引。在查找某个key-value的时候，先计算key的hash值，然后根据哈希值得后B位定位到key所在得桶。后B位定位桶得过程就类似于查找索引得过程。然后再在桶内寻找我们需要得key，每个桶能存储8个key-value。在hashmap得hash函数设置得好得情况下，key的冲突较少，数据在每个桶中的分布较为均匀，所以在桶内的查询效率也很高。

代码007普通

打赏 收藏 海报 链接