map(映射)类型
通过切片，我们可以动态灵活存储管理学生姓名、年龄等信息，比如
names := []string{"张三","李四","王五"}
ages := []int{23,24,25}
fmt.Println(names)
fmt.Println(ages)
但 是如果我想获取张三的年龄，这是一个再简单不过的需求，但是却非常麻烦，我们需要先获取张三的切片索引，再去ages切片中对应索引取出，前提还得是姓名年龄按索引对应存储。
所以在编程语言中大都会存在一种映射(key-value)类型，在JS中叫json对象类型，在python中叫字典(dict)类型，而在Go语言中则叫Map类型。
- Map是一种通过key来获取value的一个数据结构，其底层存储方式为数组，在存储时key不能重复，当key重复时，value进行覆盖，我们通过key进行hash运算(可以简单理解为把key转化为一个整形数字)然后对数组的长度取余，得到key存储在数组的哪个下标位置，最后将key和value组装为一个结构体，放入数组下标处
- slice查询是遍历方式，时间复杂度是O(n), map查询是hash映射 ;当数据量小的时候切片查询比map快，但是数据量大的时候map的优势就体现出来了
4.1、map的声明和初始化
不同于切片根据索引查找值，map类型是根据key查找值。
map 是引用类型，声明语法：
var map_name map[key_type]value_type
其中：
map_name为 map 的变量名。
key_type为键类型。
value_type是键对应的值类型。
var info map[string]string
fmt.Println(info) // map[]
(1) 先声明再赋值
// var info map[string]string // 没有默认空间
info := make(map[string]string)
info["name"] = "yuan"
info["age"] = "23"
fmt.Println(info) // map[age:23 name:yuan]
- map的键是无序的
- map的键不能重复
(2) 直接声明赋值
info := map[string]string{"name": "yuan", "age": "23","gender":"male"}
fmt.Println(info) // map[age:18 gender:male name:yuan]
4.2、map的增删改查
(1) 查
- 通过key访问值
info := map[string]string{"name": "yuan", "age": "18","gender":"male"}
val:= info["name"]
val,is_exist:= info["name"] // 判断某个键是否存在map数据中
if is_exist{
fmt.Println(val)
fmt.Println(is_exist)
}else {
fmt.Println("键不存在！")
}
- 循环访问所有键值
for k,v :=range info{
fmt.Println(k,v)
}
noSortMap := map[int]int{
1: 1,
2: 2,
3: 3,
4: 4,
5: 5,
6: 6,
}
for k, v := range noSortMap { // for range顺序随机
fmt.Println(k, v)
}
(2)添加和更新
info := map[string]string{"name": "yuan", "age": "18","gender":"male"}
info["height"] = "180cm" // 键不存在，则是添加键值对
info["age"] = "22" // 键存在，则是更新键的值
fmt.Println(info) // map[age:22 gender:male height:180cm name:yuan]
(3)删除键值对
一个内置函数 delete()，用于删除容器内的元素
info := map[string]string{"name": "yuan", "age": "18","gender":"male"}
delete(info,"gender")
fmt.Println(info)
如果想清空一个map，最优方式即创建一个新的map！
4.3、map 容量
和数组不同，map 可以根据新增的 key-value 动态的伸缩，因此它不存在固定长度或者最大限制，但是也可以选择标明 map 的初始容量 capacity，格式如下：
make(map[keytype]valuetype, cap)
例如：
m := make(map[string]float, 100)
当 map 增长到容量上限的时候，如果再增加新的 key-value，map 的大小会自动加 1，所以出于性能的考虑，对于大的 map 或者会快速扩张的 map，即使只是大概知道容量，也最好先标明。
4.4、map的灵活运用
// 案例1
data := map[string][]string{"hebei": []string{"廊坊市", "石家庄", "邯郸"}, "beijing": []string{"朝阳", "丰台", "海淀"}}
// 打印河北的第二个城市
// 循环打印每个省份的名字和城市数量
// 添加一个新的省份和城市的key-value
// 删除北京的key-value
// 案例2
info := map[int]map[string]string{1001: {"name": "yuan", "age": "23"}, 1002: {"name": "alvin", "age": "33"}}
// 打印学号为1002的学生的年龄
// 循环打印每个学员的学号，姓名，年龄
// 添加一个新的学员
// 删除1001的学生
// 案例3
stus := []map[string]string{{"name": "yuan", "age": "23"}, {"name": "rain", "age": "22"}, {"age": "32", "name": "eric"}}
// 打印第二个学生的姓名
// 循环打印每一个学生的姓名和年龄
// 添加一个新的学生map
// 删除一个学生map
// 将姓名为rain的学生的年龄自加一岁
4.5、练习
// 根据age的大小重新排序
stus := []map[string]int{map[string]int{"age": 23}, map[string]int{"age": 33}, map[string]int{"age": 18}}
fmt.Println(stus)
4.6、map的底层原理
(1)摘要算法
“消息摘要”(Message Digest)是一种能产生特殊输出格式的算法，这种加密算法的特点是无论用户输入什么长度的原始数据，经过计算后输出的密文都是固定长度的，这种算法的原理是根据一定的运算规则对原数据进行某种形式的提取，这种提取就是“摘要”，被“摘要”的数据内容与原数据有密切联系，只要原数据稍有改变，输出的“摘要”便完全不同，因此基于这种原理的算法便能对数据完整性提供较为健全的保障。但是，由于输出的密文是提取原数据经过处理的定长值，所以它已经不能还原为原数据，即消息摘要算法是**“不可逆”**的，理论上无法通过反向运算取得原数据内容，因此它通常只能被用来做数据完整性验证，而不能作为原数据内容的加密方案使用，否则谁也无法还原。
package main
import (
"crypto/md5"
"crypto/sha1"
"crypto/sha256"
"fmt"
"os"
)
func main() {
//输⼊字符串测试开始.
input := "k4"
//MD5算法.
hash := md5.New()
_, err := hash.Write([]byte(input))
if err != nil {
fmt.Println(err)
os.Exit(-1)
}
result := hash.Sum(nil)
//或者result := hash.Sum([]byte(""))
fmt.Printf("md5 hash算法长度为%d,结果：%x\n", len(result), result)
//SHA1算法.
hash = sha1.New()
_, err = hash.Write([]byte(input))
if err != nil {
fmt.Println(err)
os.Exit(-1)
}
result = hash.Sum(nil)
//或者result = hash.Sum([]byte(""))
fmt.Printf("sha1 hash算法长度为%d,结果：%x\n", len(result), result)
//SHA256算法.
hash = sha256.New()
_, err = hash.Write([]byte(input))
if err != nil {
fmt.Println(err)
os.Exit(-1)
}
result = hash.Sum(nil)
//或者result = hash.Sum([]byte(""))
fmt.Printf("sha256 hash算法长度为%d,结果：%x\n", len(result), result)
}
(2)map底层存储
哈希表属于编程中比较常见的数据结构之一，基本上所有的语言都会实现数组和哈希表这两种结构。
slice查询是遍历⽅式，时间复杂度是O(n)
map查询是hash映射，时间复杂度是O(1)
在go的map实现中，它的底层结构体是hmap，hmap⾥维护着若⼲个bucket数组 (即桶数组)。
Bucket数组中每个元素都是bmap结构，也即每个bucket(桶)都是bmap结构，【ps：后⽂为了语义⼀致，和⽅便理解，就不再提bmap 了，统⼀叫作桶】 每个桶中保存了8个kv对，如果8个满了，⼜来了⼀个key落在了这个桶⾥，会使⽤overflow连接下⼀个桶(溢出桶)。
map 的源码位于 src/runtime/map.go 文件中，结构如下：
type hmap struct {
count int // 当前 map 中元素数量
flags uint8
B uint8 // 当前 buckets 数量，2^B 等于 buckets 个数
noverflow uint16 // approximate number of overflow buckets; see incrnoverflow for details
hash0 uint32 // 哈希种子
buckets unsafe.Pointer // buckets 数组指针
oldbuckets unsafe.Pointer // 扩容时保存之前 buckets 数据。
nevacuate uintptr // progress counter for evacuation (buckets less than this have been evacuated)
extra *mapextra // optional fields
}
| count | 键值对的数量 |
| ---------- | ------------------------------------------------------------ |
| B | 2^B=len(buckets) |
| hash0 | hash因子 |
| buckets | 指向一个数组(连续内存空间)，数组的类型为[]bmap，bmap类型就是存在键值对的结构下面会详细介绍，这个字段我们可以称之为正常桶。如下图所示 |
| oldbuckets | 扩容时，存放之前的buckets(Map扩容相关字段) |
| extra | 溢出桶结构，正常桶里面某个bmap存满了，会使用这里面的内存空间存放键值对 |
| noverflow | 溢出桶里bmap大致的数量 |
| nevacuate | 分流次数，成倍扩容分流操作计数的字段(Map扩容相关字段) |
| flags | 状态标识，比如正在被写、buckets和oldbuckets在被遍历、等量扩容(Map扩容相关字段) |
// 每一个 bucket 的结构，即 hmap 中 buckets 指向的数据。
type bmap struct {
tophash [bucketCnt]uint8
}
// 编译期间重构此结构
type bmap struct {
topbits [8]uint8
keys [8]keytype
values [8]valuetype
pad uintptr
overflow uintptr
}
| topbits | 长度为8的数组，[]uint8，元素为：key获取的hash的高8位，遍历时对比使用，提高性能。如下图 所示 |
| -------- | ------------------------------------------------------------ |
| keys | 长度为8的数组，[]keytype，元素为：具体的key值。每个bucket可以存储8个键值对 |
| elems | 长度为8的数组，[]elemtype，元素为：键值对的key对应的值。 |
| overflow | 指向的hmap.extra.overflow溢出桶里的bmap，上面的字段topbits、keys、elems长度为8，最多存8组键值对，存满了就往指向的这个bmap里存 |
| pad | 对齐内存使用的，不是每个bmap都有会这个字段，需要满足一定条件 |
(1)插入key-value
map的赋值流程可总结位如下几步：
map的赋值流程可总结位如下⼏步：
<1> 通过key的hash值后“B”位确定是哪⼀个桶，图中⽰例为5号桶。
<2> 遍历当前桶，通过key的tophash和hash值，防⽌key重复。如果key已存在则直接更新值。如果没找到将key，将key插入到第⼀个可以插⼊的位置，即空位置处存储数据。
<3> 如果当前桶元素已满，会通过overflow链接创建⼀个新的桶，来存储数据。
(2)查询key-value
参考上图，k4的get流程可以归纳为如下⼏步：
<1> 计算k4的hash值。[由于当前主流机都是64位操作系统，所以计算结果有64个⽐特位]
<2> 通过最后的“B”位来确定在哪号桶，此时B为4，所以取k4对应哈希值的后4位，也就是0101，0101⽤⼗进制表⽰为5，所以在5号桶)
<3> 根据k4对应的hash值前8位快速确定是在这个桶的哪个位置(额外说明⼀下，在bmap中存放了每个key对应的tophash，是key的哈希值前8位),⼀旦发现前8位⼀致，则会执⾏下⼀步
<4> 对⽐key完整的hash是否匹配，如果匹配则获取对应value
<5> 如果都没有找到，就去连接的下⼀个溢出桶中找
有很多同学会问这⾥为什么要多维护⼀个tophash，即hash前8位？
这是因为tophash可以快速确定key是否正确，也可以把它理解成⼀种缓存措施，如果前8位都不对了，后⾯就没有必要⽐较了。