【新人系列】Golang 入门（五）：集合类型 - 下

✍ 个人博客：https://blog.csdn.net/Newin2020?type=blog
📝 专栏地址：https://blog.csdn.net/newin2020/category_12898955.html
📣 专栏定位：为 0 基础刚入门 Golang 的小伙伴提供详细的讲解，也欢迎大佬们一起交流~
📚 专栏简介：在这个专栏，我将带着大家从 0 开始入门 Golang 的学习。在这个 Golang 的新人系列专栏下，将会总结 Golang 入门基础的一些知识点，并由浅入深的学习这些知识点，方便大家快速入门学习~
❤️ 如果有收获的话，欢迎点赞 👍 收藏 📁 关注，您的支持就是我创作的最大动力 💪

本章节会重点介绍 map 数组，由浅入深带大家看看 map 底层是如何实现的。

1. map

1.1 定义与初始化

定义：

type class struct {
     Content string
     Name    string
 }
 //定义一个map存储class结构体
 var course map[string]*class

初始化：

//方法1
var courseMap = map[string]string {
    "go":"go工程师",
    "grpc":"grpc入门",
    "gin":"gin深入理解"
}

//方法2
var courseMap = map[string]string{}    //初始化为空
courseMap["mysql"] = "mysql原理"

//方法3
var courseMap = make(map[string]string, 3)
courseMap["mysql"] = "mysql原理"

//注意
var courseMap = map[string]string    //没有初始化
courseMap["mysql"] = "mysql原理"    //但放值了
fmt.Println(courseMap)    //会报错！！！

注意：
如果只声明没有初始化，放值后打印会报错。
map 必须初始化才能使用，但是 slice 可以不初始化使用。

1.2 常用操作

遍历：

//方法1
for key, value := range courseMap {
    fmt.Println(value)
}

//方法2
for key := range courseMap {
    fmt.Println(key, courseMap[key])
}

注意：
map 是无序的，而且不保证每次打印都是相同的顺序。这种设计是有意为之的，因为能防止程序依赖特定遍历顺序，而这是无法保证的。

判断是否存在：

//方法1
d, ok := courseMap["java"]
if !ok {
    fmt.Println("not int")
}

//方法2
if _, ok := courseMap["java"]; !ok {
    fmt.Println("not int")
}

删除元素：

delete(courseMap, "grpc")

注意：
如果删除不存在的元素，不会报错。
另外，map 不是线程安全的，需要用 sync.Map。

1.3 哈希表

说到键值对的存储，我们自然会想到哈希表，至于怎么将键值对存储到哈希桶中，主要有以下几个步骤：

1. 通过哈希函数 Hash() 把 “键 k1” 处理一下，得到一个哈希值 hash
2. 现在需要通过哈希值 hash 从所有桶中选择一个，桶编号范围为 [0, m-1]
3. 选择方法有两种比较常用：
4. 取模法：hash % m
5. 与运算：hash & (m-1)

需要注意的是，与运算方法如果想确保运算结果落在区间 [0, m-1] 而不会出现空桶，就要限制桶的个数 m 必须是 2 的整数次幂。这样 m 的二进制表示一定只有一位为 1，并且 m-1 的二进制表示一定是低于这一位的所有位均为 1。

注意：
如果桶的数目不是 2 的整数次幂，就有可能出现有些桶绝对不会被选中的情况。

1.4 哈希冲突

知道如何选桶后还要考虑一个问题，如果出现选择的桶冲突了怎么办，下面我们同样来介绍两种常用的方法;

1.4.1 开放地址法

如果 {k2, v2} 选择的桶和 {k1, v1} 选择的一样即发生了冲突，则沿着 {k1, v1} 的桶往后找到第一个没有被占用的桶进行占用。

当要查找 {k2, v2} 时，会从 {k1, v1} 的桶开始比较，如果发现 key 值不相等，则会沿着该桶往后进行比较，直到找到 key = k2 的桶为止。

1.4.2 拉链法

还有一种方法不用沿着桶进行寻找，而是直接在冲突的桶后面链一个新桶存储这个键值对即可。
当要查找 {k2, v2} 时，同样会从 {k1, v1} 的桶开始比较，如果发现 key 值不相等，这次会沿着该桶后面的链表进行比较，直到找到 key = k2 的桶为止。

1.5 哈希扩容

上面的哈希冲突会影响到我们哈希表的读写效率，因此选择散列均匀的哈希函数可以减少哈希冲突的发生，另外适时的对哈希表进行扩容也是保障读写效率的有效手段。

通常我们会把存储键值对的数目与桶的数目的比值作为是否需要扩容的判断依据，这个比值被称为 “负载因子”。

当我们需要扩容时，就要分配更多的桶，它们就是 “新桶”，需要把 “旧桶” 里存储的键值对都迁移到新桶里。

如果哈希表存户的键值对较多，一次性迁移所有桶花费的时间就比较显著。所以通常会在哈希表扩容时，先分配足够多的新桶，然后用一个字段记录 “旧桶” 的位置 oldbuckets，再增加一个字段记录 “旧桶” 的迁移进度，例如记录下一个要迁移的 “旧桶” 编号 nevacuate。

在哈希表每次读写操作时，如果检测到当前处于扩容阶段，就完成一部分键值对的迁移任务，直到所有的 “旧桶” 迁移完成，“旧桶” 不再使用才算真正完成了一次哈希表的扩容。

像这样把键值对迁移的时间分摊到多次哈希表操作中的方式，就是 “渐进式扩容” 了，可以避免一次性扩容带来的性能瞬时抖动。

注意：
Go map 的扩容就采用的这种方式，原有的 key 并不会一次性搬迁完毕，每次最多只会搬迁 2 个 bucket。

1.6 底层存储原理

在 Go 语言中，map 类型的底层实现就是哈希表，map 类型的变量 a := map[string]string{} 本质上是一个指针 *hmap，指向 hmap 结构体。

type hmap struct {
    count        int            //键值对数目
    flags        uint8          //状态标志（是否处于正在写入的状态等）
    B            uint8          //记录桶的数目是2的多少次幂，因为这里选择桶时用的是与运算的方法
    noverflow    uint16         //记录使用溢出桶的数量
    hash0        uint32         //生成hash的随机数种子
    
    buckets      unsafe.Pointer //记录桶在哪里
    oldbuckets   unsafe.Pointer //用于在扩容阶段保存旧桶在哪儿
    nevacuate    uintptr        //记录渐进式扩容阶段下一个要迁移的旧桶编号
    
    extra        *mapextra      //存储溢出桶
}

map 的桶是用 bmap 结构进行存储，一个桶里可以放 8 个键值对，但是为了让内存排列更加紧凑，所以让 8 个 key 放一起，8 个 value 放一起。

在 8 个 key 的前面则是 8 个 tophash，每个 tophash 都是对应哈希值的高 8 位。

// A bucket for a Go map.
type bmap struct {
    tophash [bucketCnt]uint8        
    // len为8的数组
    // 用来快速定位key是否在这个bmap中
    // 一个桶最多8个槽位，如果key所在的tophash值在tophash中，则代表该key在这个桶中
}

上面 bmap 结构是静态结构，在编译过程中 runtime.bmap 会拓展成以下结构体：

type bmap struct{
    tophash [8]uint8
    keys [8]keytype 
    // keytype 由编译器编译时候确定
    values [8]elemtype 
    // elemtype 由编译器编译时候确定
    overflow uintptr 
    // overflow指向下一个bmap，overflow是uintptr而不是*bmap类型，保证bmap完全不含指针，是为了减少gc，溢出桶存储到extra字段中
}

放在最后的是一个 bmap 型指针，指向一个溢出桶，溢出桶的内存布局与常规桶相同，是为了减少扩容次数而引入的。当一个桶存满了，还有可用的溢出桶时，就会在桶后面链一个溢出桶，继续往溢出桶里面存。

但实际上如果哈希表要分配的桶的数目大于 2^4，就认为使用到溢出桶的几率较大，就会预分配 2^(B-4) 个溢出桶备用，这些溢出桶与常规桶在内存中是连续的，只是前 2^B 个用作常规桶，后面的用作溢出桶。

举个例子，假设 B = 5，那么一共有 2^5 个桶，又因为 2^5 > 2^4，所以就会预分配 2^(5-4) = 2^1 个溢出桶。

也就是说，当 B = 5 时，前 2^5 个会被作为常规桶，而剩下的 2^1 个桶会当做溢出桶使用。

另外，hmap 结构体最后有一个 extra 字段，它会指向一个 mapextra 结构体，里面记录的都是溢出桶相关的信息。其中 nextoverflow 指向下一个空闲溢出桶，overflow 是一个 slice，记录目前已经被使用的溢出桶的地址，而 oldoverflow 则是用于。

type mapextra struct {
    overflow    *[]*bmap //包含已经使用的溢出桶
    oldoverflow *[]*bma  //包含扩容阶段旧桶使用的溢出桶
    nextOverflow *bmap   //指向下一个溢出桶
}

假如现在 2 号桶存满了，它就会在后面链一个溢出桶，而 nextoverflow 就会指向下一个空闲溢出桶，并且此时 noverflow 会记录使用溢出桶的数量即记录此时用了 1 个溢出桶。

我们来看一个例子，变量 a 本质上是一个 hmap 的指针，目前存储了一个键值对，只拥有一个桶，也没有预分配的溢出桶。

下面我们把这个桶展开来看一下，首先是 8 个 tophash，每个占一字节，因为 key 和 value 都是 string 类型，所以 64 位下每个 key 和 value 都占用 16 字节。

目前只存储了一个键值对，取 k1 哈希值的高 8 位 h1 存到 tophash 第一位，而 k1 和 v1 则按照字符串的存储规则进行存储。

如果我们把这个桶存满，接下来继续存储新的键值对时，这个哈希表是会创建溢出桶还是会发生扩容呢？这就要看 map 的扩容规则了。

1.7 扩容规则

1.7.1 翻倍扩容

当负载因子大于 6.5，即 map 元素个数 / 桶个数 > 6.5 时，就会触发翻倍扩容。
来看源码，其中：

- bucketCnt = 8，一个桶可以装的最大元素个数
- loadFactor = 6.5，负载因子，平均每个桶的元素个数
- bucketShift(B)：桶的个数
func overLoadFactor(count int, B uint8) bool {
   return count > bucketCnt && uintptr(count) > loadFactor * bucketShift(B)
}

回到刚刚那个例子，当存储新的键值对时，我们就需要进行扩容。由于负载因子大于 6.5 了，所以会触发翻倍扩容，旧桶数量为 1，所以新桶数量为 1 * 2 = 2 个。

此时，buckets 就会指向刚分配出来的新桶，而 oldbuckets 则会指向旧桶，并且 nevacuate 为 0，标识接下来要迁移编号为 0 的旧桶，每个旧桶的键值对都会分流到新桶中。

例如，旧桶的数量为 4，那么翻倍扩容后新桶的数量就为 8。

如果一个哈希值选择 0 号旧桶，那么按照旧桶 m = 4 的情况来看，哈希值的二进制低两位一定为 0。

现在新桶 m = 8，那么 0 号旧桶可以迁移的新桶只有两种，取决于哈希值的第三位是 0 还是 1，如果为 0 则迁移到编号为 0 的新桶，反之为 1 则迁移到编号为 4 的新桶。

因为桶的数量一定是 2 的整数次幂，所以无论容量为多少，翻倍扩容后，每个旧桶都会按照这样的规律分流道两个新桶中。

1.7.2 等量扩容

如果负载因子没有超标，但是使用的溢出桶较多，也会触发扩容：

• 当常规桶数量不大于 2^15 时（B <= 15），此时如果溢出桶总数 >= 常规桶总数（noverflow >= 2^B），则认为溢出桶过多，就会触发等量扩容。
• 当常规桶数量大于 2^15 时（B > 15），此时直接与 2^15 比较，当溢出桶总数 >= 2^15 时（noverflow >= 2^15），即认为溢出桶太多了，也会触发等量扩容。

func tooManyOverflowBuckets(noverflow uint16, B uint8) bool {
    // If the threshold is too low, we do extraneous work.
    // If the threshold is too high, maps that grow and shrink can hold on to lots of unused memory.
    // "too many" means (approximately) as many overflow buckets as regular buckets.
    // See incrnoverflow for more details.
    if B > 15 {
        B = 15
    }
    // The compiler does not see here that B < 16; mask B to generate shorter shift code.
    return noverflow >= uint16(1)<<(B&15)
}

所谓等量扩容，就是创建和旧桶数量一样多的新桶，然后把原来的键值对迁移到新桶中。但是既然是等量，那迁移这些还有什么意义呢？

那当然是有个特殊情况需要我们关注，当有很多键值对被删除的时候，就有可能出现已经使用了很多溢出桶，但是负载因子仍没有超过上限值的情况。

就像下面这个例子，编号为 0 的桶中有很多键值对已经被删除了，此时如果触发了等量扩容，则会分配等量的新桶。而旧桶的每一个桶则会迁移到对应的新桶中，迁移完后可以使每个键值对排列的更加紧凑，从而减少溢出桶的使用。

2. List

使用：

package main

import (
    "container/list"
    "fmt"
)

func main() {
    var mylist list.List    //mylist := list.New()
    
    //尾部插入
    mylist.PushBack("go")
    mylist.PushBack("grpc")
    mylist.PushBack("mysql")
    
    //头部插入
    mylist.PushFront("gin")
    
    //遍历打印值，正序
    for i := mylist.Front(); i != nil; i = i.Next() {
        fmt.Println(i.Value)
    }
}