一.map介绍和使用
map是一种无序的基于key-value的数据结构,Go语言的map是引用类型,必须初始化才可以使用。
1. 定义
Go语言中,map类型语法如下:
map[KeyType]ValueType
- KeyType表示键类型
- ValueType表示值类型
map类型的变量默认初始值为nil,需要使用make函数来分配内存。语法为:
make(map[KeyType]ValueType, [cap])
map[KeyType]ValueType{} //底层也是使用的make
map[KeyType]Value{ //底层也是使用的make
key:value,
key:value,
...
}
其中cap表示map的容量,该参数虽然不是必须的,但是我们应该在初始化map的时候就为其指定一个合适的容量。
可以使用len()内置函数来获取map键值对的个数。
注意:map保存的键值对中,键不能被修改,只能修改值。
2.基本使用
package main
import "fmt"
func main() {
scoreMap := make(map[string]int, 8)
scoreMap["张三"] = 100
scoreMap["小明"] = 90
fmt.Println(scoreMap)
fmt.Printf("key num is %d\n", len(scoreMap))
fmt.Println(scoreMap["小明"])
fmt.Printf("type(scoreMap)=%T\n", scoreMap)
}
map也支持在声明时填充元素:
package main
import "fmt"
func main() {
userInfo := map[string]string{
"username": "zhansan",
"password": "123456",
}
fmt.Println(userInfo)
}
3. 判断某个键是否存在
Go语言中有个判断map中的键是否存在的特殊写法:
value, ok := map[key]
例子:
package main
import "fmt"
func main() {
userInfo := map[string]string{
"username": "zhansan",
"passward": "123456",
}
value, ok := userInfo["passward"]
if ok {
fmt.Println(value)
} else {
fmt.Println("passward is not exit")
}
value, ok = userInfo["sex"]
if ok {
fmt.Println(value)
} else {
fmt.Println("sex is not exit")
}
}
4. map的遍历
遍历key和value:
package main
import "fmt"
func main() {
scoreMap := make(map[string]int, 8)
scoreMap["小明"] = 100
scoreMap["张三"] = 80
scoreMap["李四"] = 60
for key, value := range scoreMap {
fmt.Printf("scoreMap[%s] = %d\n", key, value)
}
}
只遍历key:
注意:遍历map时的元素顺序与添加键值对的顺序无关。
5. 删除键值对
使用delete()内置函数从map中删除一组键值对,格式如下:
delete(map, key)
//map:为需要删除键值对的map
//key:表示要删除键值对的键
package main
import "fmt"
func main() {
scoreMap := make(map[string]int, 8)
scoreMap["小明"] = 100
scoreMap["张三"] = 80
scoreMap["李四"] = 60
value, ok := scoreMap["李四"]
if ok {
fmt.Println(value)
} else {
fmt.Println("李四 is not exit")
}
//删除键值对
delete(scoreMap, "李四")
value, ok = scoreMap["李四"]
if ok {
fmt.Println(value)
} else {
fmt.Println("李四 is not exit")
}
}
6. 按照指定顺序遍历map
实际时先获取到所有的键,将键设置成指定顺序,再通过键来遍历map。
package main
import (
"fmt"
"math/rand"
"sort"
"time"
)
func main() {
rand.Seed(time.Now().UnixNano()) //初始化随机种子
scoreMap := make(map[string]int, 200)
for i := 0; i < 100; i++ {
key := fmt.Sprintf("stu%02d", i)
scoreMap[key] = rand.Intn(100) //获取0-100的随机数
//fmt.Println(key, scoreMap[key])
}
keys := make([]string, 0, 200)//保存key
//按照排序后的key遍历scoreMap
for key := range scoreMap {
keys = append(keys, key)
}
//fmt.Println(keys)
sort.Strings(keys) //对keys进行排序
for _, key := range keys {
fmt.Printf("scoreMap[%s] = %d\n", key, scoreMap[key])
}
}
7. 元素为map类型的切片
package main
import "fmt"
func main() {
mapSlice := make([]map[string]string, 3, 10) //并没有为map分配地址空间
for index, val := range mapSlice {
fmt.Printf("mapSlice[%d] = %v\n", index, val)
}
//分配地址空间
for index, _ := range mapSlice {
mapSlice[index] = make(map[string]string, 10)
}
fmt.Println("---------插入键值对后---------")
//插入键值对
mapSlice[0]["name"] = "张三"
mapSlice[0]["passwd"] = "123123"
mapSlice[1]["name"] = "李四"
mapSlice[1]["passwd"] = "321321"
mm := map[string]string{
"name": "小明",
"passwd": "123465",
}
mapSlice = append(mapSlice, mm)
for index, val := range mapSlice {
fmt.Printf("mapSlice[%d] = %v\n", index, val)
}
}
8. 值为切片类型的map
package main
import "fmt"
func main() {
sliceMap := make(map[string][]string, 10) //没有为slice分配空间
sliceMap["中国"] = make([]string, 0, 10)
sliceMap["中国"] = append(sliceMap["中国"], "北京", "上海", "长沙")
key := "美国"
value, ok := sliceMap[key]
if !ok {
value = make([]string, 0)
}
value = append(value, "芝加哥", "华盛顿")
sliceMap[key] = value
for key, val := range sliceMap {
fmt.Printf("sliceMap[%s] = %v\n", key, val)
}
}
二.map底层原理
Go语言的map有两个重要的数据结构 hmap和bmap。
2.1 map头部数据结构——hmap
hmap中有几个重要的属性:
- count:记录了map中实际元素的个数
- B:控制哈希桶的个数为2^B个
- buckets:是一个指向长度为2^B大小的类型为bmap的数组
- oldbuckets:与buckets一样也是指向一个多桶的数组,不同的是oldbuckets指向的是旧桶的地址,当oldbuckets不为空时,表示map正处于扩容阶段。
type hmap struct {
// map中元素的个数,使用len返回就是该值
count int
// 状态标记
// 1: 迭代器正在操作buckets
// 2: 迭代器正在操作oldbuckets
// 4: go协程正在像map中写操作
// 8: 当前的map正在增长,并且增长的大小和原来一样
flags uint8
// buckets桶的个数为2^B
B uint8
// 溢出桶的个数
noverflow uint16
// key计算hash时的hash种子
hash0 uint32
// 指向的是桶的地址
buckets unsafe.Pointer
// 旧桶的地址,当map处于扩容时旧桶才不为nil
oldbuckets unsafe.Pointer
//扩容之后数据迁移的计数器,记录下次迁移的位置,当nevacuate>旧桶元素个数,数据迁移完
nevacuate uintptr
// 额外的map字段,存储溢出桶信息
extra *mapextra
}
创建一个map实际是创建一个指针,指向hmap结构。
2.2 bmap
bmap是每一个桶的数据结构,每一个bmap包含8个key和value。
type bmap struct {
tophash [bucketCnt]uint8
// len为8的数组,用来快速定位key是否在这个bmap中
// 一个桶最多8个槽位,如果key所在的tophash值在tophash中,则代表该key在这个桶中
}
上面是bmap的静态结构,在编译过程中runtime.bmap会扩展成以下结构:
- topbits :用来快速定位桶中键值对的位置。
- keys:键值对的键
- values:键值对的值
- overflow:当8个key满的时候,需要新创建一个桶,overflow保存下一个桶的地址。
细节:
这里将键和键保存到了一起,值和值保存在了一起,为什么不讲键和值保存在一起?
因为键和值的类型可能不同,结构体内存对齐会浪费空间。
type bmap struct{
topbits [8]uint8
keys [8]keytype
values [8]valuetype
pad uintptr // 内存对齐使用,可能不需要
overflow uintptr // 当bucket 的8个key 存满了之后
// overflow 指向下一个溢出桶 bmap,
// overflow是uintptr而不是*bmap类型,保证bmap完全不含指针,是为了减少gc,溢出桶存储到extra字段中
}