第9篇：引用数据类型之字典

基础数据类型

• 整型，用于表示整数
• 浮点型，用于表示小数
• 复数，用来表示复数
• 布尔型，用于表示真/假
• 字符串，用于表示文本信息

复合数据类型

• 数组，用于表示多个数据（数据集合）
• 结构体，用于自定义一些数据集合和方法

引用数据类型

• 指针，用于表示内存地址的类型
• 切片，用于表示多个数据（数据集合）
• 字典，用于表示键值对集合
• 函数，用于将一个语句序列打包为一个单元，然后可以从程序中其它地方多次调用
• 通道，channel，是goroutine中的通信机制

接口数据类型

• 接口，用于约束和泛指数据类型

哈希表是一种巧妙并且实用的数据结构。它是一个无序的key/value对的集合，其中所有的key都是不同的，然后通过给定的key可以在常数时间复杂度内检索、更新或删除对应的value。

在Go语言中，一个map就是一个哈希表的引用，map类型可以写为map[K]V，其中K和V分别对应key和value。map中所有的key都有相同的类型，所有的value也有着相同的类型，但是key和value之间可以是不同的数据类型。其中K对应的key必须是支持==比较运算符的数据类型，所以map可以通过测试key是否相等来判断是否已经存在。虽然浮点数类型也是支持相等运算符比较的，但是将浮点数用做key类型则是一个坏的想法，最坏的情况是可能出现的NaN和任何浮点数都不相等。对于V对应的value数据类型则没有任何的限制。

map是一种无序的基于key-value的数据结构，Go语言中的map是引用类型，必须初始化才能使用。

这种类型最大的特点就是查找速度非常快，因为他的底层存储是基于哈希表存储的（不同语言还会有一些差异）。

以取模+拉链法来快速了解下哈希表存储原理，如下图：

这种结构之所以快，是因为根据key可以直接找到数据存放的位置；而其他的数据类型是需要从前到后去逐一比对，相对来说比较耗时。

以上只是基本的存储模型，而各个编程语言中的字典都会在此基础上进行相应的修改和优化（后续会深入讲解Golang中的map实现机制）。

Map的特点：

• 键不能重复
• 键必须可哈希（目前我们已学的数据类型中，可哈希的有：int/bool/float/string/array）
• 无序

接下来关于map我会从两个维度来进行讲解：

• 常见使用
• 底层原理剖析（面试常问）

一、map定义

Go语言中 map的定义语法如下

map[KeyType]ValueType

其中，

KeyType:表示键的类型。
ValueType:表示键对应的值的类型。

map类型的变量默认初始值为nil，需要使用make()函数来分配内存。语法为：

make(map[KeyType]ValueType, [cap])

其中cap表示map的容量，该参数虽然不是必须的，但是我们应该在初始化map的时候就为其指定一个合适的容量。

二、map初始化

map中的数据都是成对出现的，map的基本使用示例代码如下：

func main() {
    scoreMap := make(map[string]int, 8)
    scoreMap["张三"] = 90
    scoreMap["小明"] = 100
    fmt.Println(scoreMap)
    fmt.Println(scoreMap["小明"])
    fmt.Printf("type of a:%T\n", scoreMap)
}

输出：

map[小明:100 张三:90]
100
type of a:map[string]int

map也支持在声明的时候填充元素，例如：

func main() {
    userInfo := map[string]string{
        "username": "pprof.cn",
        "password": "123456",
    }
    fmt.Println(userInfo) //
}

其他示例

// userInfo := map[string]string{}
userInfo := map[string]string{"name":"张亚飞","age":"18"}

userInfo["name"]  // 张亚飞
userInfo["age"] = "20"
userInfo["email"] = "zhangyafei@qq.com"
// data := make(map[int]int, 10)
data := make(map[int]int)
data[100] = 998
data[200] = 999
data := make(map[string]int)
data["100"] = 998
data["200"] = 999

// 声明，nil
var row map[string]int
row = data
data := make(map[string]int)
data["100"] = 998
data["200"] = 999

// 声明，nil
value := new(map[string]int)
// value["k1"] = 123  # 报错
value = &data
// 注意：键不重复 & 键必须可哈希（int/bool/float/string/array）

v1 := make(map[[2]int]float32)
v1[[2]int{1,1}] = 1.6
v1[[2]int{1,2}] = 3.4

v2 := make(map[[2]int][3]string )
v2[[2]int{1,1}] = [3]string{"乔丹","科比","詹姆斯"}

三、常用操作

1. 长度和容量

data := map[string]string{"n1":"张亚飞","n2":"王小二"}
value := len(data)  // 2
// 根据参数值（10），计算出合适的容量。
// 一个map 中会包含很多桶，每个桶中可以存放8个键值对。
info := make(map[string]string, 10)

info["n1"] = "张亚飞"
info["n2"] = "王小二"

v1 := len(info)  // 2
// v2 := cap(info)  // 报错

2. 添加

data := map[string]string{"n1":"张亚飞","n2":"王小二"}
data["n3"] = "赵老三"

3. 修改

data := map[string]string{"n1":"张亚飞","n2":"王小二"}
data["n1"] = "王老五"

4. 删除

使用delete()内建函数从map中删除一组键值对，delete()函数的格式如下：

delete(map, key)

其中，

map:表示要删除键值对的map
key:表示要删除的键值对的键

示例代码如下：

data := map[string]string{"n1":"张亚飞","n2":"王小二"}
delete(data, 'n2')

5. 查看

data := map[string]string{"n1":"张亚飞","n2":"王小二"}
data["n1"]

6. 嵌套

v1 := make(map[string]int)
v2 := make(map[string]string)
v3 := make(map[string]...)
v4 := make(map[string][2]int)
v5 := make(map[string][]int)
v6 := make(map[string]map[int]int)
v7 := make(map[string][2]map[string]string)
v7["n1"] = [2]map[string]string{ map[string]string{"name":"张亚飞","age":"18"},map[string]string{"name":"基里连科","age":"78"}}
v7["n2"] = [2]map[string]string{ map[string]string{"name":"德隆","age":"18"},map[string]string{"name":"张伯伦","age":"78"}}

// 伪代码
v7 = {
    n1:[
        {"name":"张亚飞","age":"18"},
        {"name":"基里连科","age":"78"}
    ],
    n2:[
        {"name":"德隆","age":"18"},
        {"name":"张伯伦","age":"78"}
    ]
}

前提：键不重复 & 键必须可哈希

v8 := make(map[int]int)
v9 := make(map[string]int)
v10 := make(map[float32]int)
v11 := make(map[bool]int)
v12 := make(map[ [2]int ]int)
v13 := make(map[ []int ]int) // 错误,不可哈希
v14 := make(map[ map[int]int ]int) // 错误，不可哈希
v15 := make(map[ [2][]int ]int) // 报错
v16 := make(map[ [2]map[string]string ]int) // 报错

7. 变量赋值

v1 := map[string]string{"n1":"张亚飞","n2":"基里连科"}
v2 := v1

v1["n1"] = "zhangyafei"

ftm.Println(v1) // {"n1":"zhangyafei","n2":"基里连科"}
ftm.Println(v2) // {"n1":"zhangyafei","n2":"基里连科"}

特别提醒：无论是否存在扩容都指向同一个地址。

8. 判断某个键是否存在

Go语言中有个判断map中键是否存在的特殊写法，格式如下:

value, ok := map[key]

举个例子：

func main() {
    scoreMap := make(map[string]int)
    scoreMap["张三"] = 90
    scoreMap["小明"] = 100
    // 如果key存在ok为true,v为对应的值；不存在ok为false,v为值类型的零值
    v, ok := scoreMap["张三"]
    if ok {
        fmt.Println(v)
    } else {
        fmt.Println("查无此人")
    }
}

9. map的遍历

Go语言中使用for range遍历map。

func main() {
    scoreMap := make(map[string]int)
    scoreMap["张三"] = 90
    scoreMap["小明"] = 100
    scoreMap["王五"] = 60
    for k, v := range scoreMap {
        fmt.Println(k, v)
    }
}

但我们只想遍历key的时候，可以按下面的写法：

func main() {
    scoreMap := make(map[string]int)
    scoreMap["张三"] = 90
    scoreMap["小明"] = 100
    scoreMap["王五"] = 60
    for k := range scoreMap {
        fmt.Println(k)
    }
}

只想遍历value的时候

func main() {
    scoreMap := make(map[string]int)
    scoreMap["张三"] = 90
    scoreMap["小明"] = 100
    scoreMap["王五"] = 60
    for _, value := range scoreMap {
        fmt.Println(value)
    }
}

注意： 遍历map时的元素顺序与添加键值对的顺序无关。

10. 按照指定顺序遍历map

 func main() {
    rand.Seed(time.Now().UnixNano()) //初始化随机数种子

    var scoreMap = make(map[string]int, 200)

    for i := 0; i < 100; i++ {
        key := fmt.Sprintf("stu%02d", i) //生成stu开头的字符串
        value := rand.Intn(100)          //生成0~99的随机整数
        scoreMap[key] = value
    }
    //取出map中的所有key存入切片keys
    var keys = make([]string, 0, 200)
    for key := range scoreMap {
        keys = append(keys, key)
    }
    //对切片进行排序
    sort.Strings(keys)
    //按照排序后的key遍历map
    for _, key := range keys {
        fmt.Println(key, scoreMap[key])
    }
}

11. 元素为map类型的切片

下面的代码演示了切片中的元素为map类型时的操作：

func main() {
    var mapSlice = make([]map[string]string, 3)
    for index, value := range mapSlice {
        fmt.Printf("index:%d value:%v\n", index, value)
    }
    fmt.Println("after init")
    // 对切片中的map元素进行初始化
    mapSlice[0] = make(map[string]string, 10)
    mapSlice[0]["name"] = "王五"
    mapSlice[0]["password"] = "123456"
    mapSlice[0]["address"] = "红旗大街"
    for index, value := range mapSlice {
        fmt.Printf("index:%d value:%v\n", index, value)
    }
}

12. 值为切片类型的map

下面的代码演示了map中值为切片类型的操作：

func main() {
    var sliceMap = make(map[string][]string, 3)
    fmt.Println(sliceMap)
    fmt.Println("after init")
    key := "中国"
    value, ok := sliceMap[key]
    if !ok {
        value = make([]string, 0, 2)
    }
    value = append(value, "北京", "上海")
    sliceMap[key] = value
    fmt.Println(sliceMap)
}

四、Map底层原理剖析

Golang中的Map有自己的一套实现原理，其核心是由hmap和bmap两个结构体实现。

1. 初始化

// 初始化一个可容纳10个元素的map
info = make(map[string]string,10)

• 第一步：创建一个hmap结构体对象。

• 第二步：生成一个哈希因子hash0 并赋值到hmap对象中（用于后续为key创建哈希值）。

• 第三步：根据hint=10，并根据算法规则来创建 B，当前B应该为1。

  hint            B
  0~8                0
  9~13            1
  14~26           2
  ...

• 第四步：根据B去创建去创建桶（bmap对象）并存放在buckets数组中，当前bmap的数量应为2.

  • 当B<4时，根据B创建桶的个数的规则为：2B2B（标准桶）
  • 当B>=4时，根据B创建桶的个数的规则为：2B2B + 2B−42B−4（标准桶+溢出桶）

  注意：每个bmap中可以存储8个键值对，当不够存储时需要使用溢出桶，并将当前bmap中的overflow字段指向溢出桶的位置。

2. 写入数据

info["name"] = "张亚飞"

在map中写入数据时，内部的执行流程为：

• 第一步：结合哈希因子和键 name生成哈希值 011011100011111110111011011。

• 第二步：获取哈希值的后B位，并根据后B为的值来决定将此键值对存放到那个桶中（bmap）。

  将哈希值和桶掩码（B个为1的二进制）进行 & 运算，最终得到哈希值的后B位的值。假设当B为1时，其结果为 0 ：
  哈希值：011011100011111110111011010
  桶掩码：000000000000000000000000001
  结果：  000000000000000000000000000 = 0
  
  通过示例你会发现，找桶的原则实际上是根据后B为的位运算计算出 索引位置，然后再去buckets数组中根据索引找到目标桶（bmap)。

• 第三步：在上一步确定桶之后，接下来就在桶中写入数据。

  获取哈希值的tophash（即：哈希值的`高8位`），将tophash、key、value分别写入到桶中的三个数组中。
  如果桶已满，则通过overflow找到溢出桶，并在溢出桶中继续写入。
  
  注意：以后在桶中查找数据时，会基于tophash来找（tophash相同则再去比较key）。

• 第四步：hmap的个数count++（map中的元素个数+1）

3. 读取数据

value := info["name"]

在map中读取数据时，内部的执行流程为：

• 第一步：结合哈希引子和键 name生成哈希值。

• 第二步：获取哈希值的后B位，并根据后B为的值来决定将此键值对存放到那个桶中（bmap）。

• 第三步：确定桶之后，再根据key的哈希值计算出tophash（高8位），根据tophash和key去桶中查找数据。

  当前桶如果没找到，则根据overflow再去溢出桶中找，均未找到则表示key不存在。

4. 扩容

在向map中添加数据时，当达到某个条件，则会引发字典扩容。

扩容条件：

• map中数据总个数 / 桶个数 > 6.5 ，引发翻倍扩容。
• 使用了太多的溢出桶时（溢出桶使用的太多会导致map处理速度降低）。
  • B <=15，已使用的溢出桶个数 >= 2B2B 时，引发等量扩容。
  • B > 15，已使用的溢出桶个数 >= 215215 时，引发等量扩容。

func hashGrow(t *maptype, h *hmap) {
    // If we've hit the load factor, get bigger.
    // Otherwise, there are too many overflow buckets,
    // so keep the same number of buckets and "grow" laterally.
    bigger := uint8(1)
    if !overLoadFactor(h.count+1, h.B) {
        bigger = 0
        h.flags |= sameSizeGrow
    }
    oldbuckets := h.buckets
    newbuckets, nextOverflow := makeBucketArray(t, h.B+bigger, nil)
    ...
}

当扩容之后：

• 第一步：B会根据扩容后新桶的个数进行增加（翻倍扩容新B=旧B+1，等量扩容 新B=旧B）。
• 第二步：oldbuckets指向原来的桶（旧桶）。
• 第三步：buckets指向新创建的桶（新桶中暂时还没有数据）。
• 第四步：nevacuate设置为0，表示如果数据迁移的话，应该从原桶（旧桶）中的第0个位置开始迁移。
• 第五步：noverflow设置为0，扩容后新桶中已使用的溢出桶为0。
• 第六步：extra.oldoverflow设置为原桶（旧桶）已使用的所有溢出桶。即：h.extra.oldoverflow = h.extra.overflow
• 第七步：extra.overflow设置为nil，因为新桶中还未使用溢出桶。
• 第八步：extra.nextOverflow设置为新创建的桶中的第一个溢出桶的位置。

5. 迁移

扩容之后，必然要伴随着数据的迁移，即：将旧桶中的数据要迁移到新桶中。

翻倍扩容

如果是翻倍扩容，那么迁移规就是将旧桶中的数据分流至新的两个桶中（比例不定），并且桶编号的位置为：同编号位置 和 翻倍后对应编号位置。

那么问题来了，如何实现的这种迁移呢？

首先，我们要知道如果翻倍扩容（数据总个数 / 桶个数 > 6.5），则新桶个数是旧桶的2倍，即：map中的B的值要+1（因为桶的个数等于2B2B，而翻倍之后新桶的个数就是2B2B * 2 ，也就是2B+12B+1，所以 新桶的B的值=原桶B + 1 ）。

迁移时会遍历某个旧桶中所有的key（包括溢出桶），并根据key重新生成哈希值，根据哈希值的 底B位 来决定将此键值对分流道那个新桶中。

扩容后，B的值在原来的基础上已加1，也就意味着通过多1位来计算此键值对要分流到新桶位置，如上图：

• 当新增的位（红色）的值为 0，则数据会迁移到与旧桶编号一致的位置。
• 当新增的位（红色）的值为 1，则数据会迁移到翻倍后对应编号位置。

例如：

旧桶个数为32个，翻倍后新桶的个数为64。
在重新计算旧桶中的所有key哈希值时，红色位只能是0或1，所以桶中的所有数据的后B位只能是以下两种情况：
    - 000111【7】，意味着要迁移到与旧桶编号一致的位置。
    - 100111【39】，意味着会迁移到翻倍后对应编号位置。

特别提醒：同一个桶中key的哈希值的低B位一定是相同的，不然不会放在同一个桶中，所以同一个桶中黄色标记的位都是相同的。

等量扩容

如果是等量扩容（溢出桶太多引发的扩容），那么数据迁移机制就会比较简单，就是将旧桶（含溢出桶）中的值迁移到新桶中。

这种扩容和迁移的意义在于：当溢出桶比较多而每个桶中的数据又不多时，可以通过等量扩容和迁移让数据更紧凑，从而减少溢出桶。