go语言map笔记
map是Go语言提供的一种抽象数据类型，它表示一组无序的键值对。
map对应数据结构里的哈希表
map底层的数据结构
哈希方法，怎么根据key定位到value
哈希冲突后怎么解决，
常见的坑
性能问题
并发问题
(1) map类型介绍
map 类型对 value 的类型没有限制，但是对 key 的类型却有严格要求，因为 map 类型要保证 key 的唯一性。Go 语言中要求，key 的类型必须支持”==”和”!=”两种比较操作符。
注意：函数类型、map 类型自身，以及切片类型是不能作为 map 的 key 类型的。
(2.1) map的基本操作
定义map
// 声明map
var map1 map[string]string
// 初始化map 分配内存
map1 = make(map[string]string, 16)// 初始化一个空的map
m := map[string]int{} // 声明并初始化map
// 分配内存并赋值
var m map[string]int = map[string]int{"河北":1,"天津":2}// 声明并初始化map
m1 := map[int][]string{
1: []string{"val1_1", "val1_2"},
3: []string{"val3_1", "val3_2", "val3_3"},
7: []string{"val7_1"},
}m1 := make(map[int]string) // 未指定初始容量
m2 := make(map[int]string, 8) // 指定初始容量为8新增/更新map
var map1 map[string]string
map1 = make(map[string]string, 16)
// 设置值
map1["河北"] = "石家庄"
map1["山西"] = "太原"
map1["山东"] = "济南"
map1["测试"] = string(100)删除值
delete(map1, "测试")遍历
for k, v := range map1 {
fmt.Println(k, " ", v)
}map遍历时返回结果是无序的，而且每次执行结果都是不一样的
() map特殊设计点
() 声明但未初始化的map读取不报错
像在Java里，声明了map没初始化，使用会报空指针。
但是go里却不会。
import java.util.Map;
public class MapTest {
public static void main(String[] args) {
// Map<String, String> map; // java: variable map might not have been initialized
Map<String, String> map = null; // 声明map
// 测试空map读取
String val = map.get("k");
// Exception in thread "main" java.lang.NullPointerException: Cannot invoke "java.util.Map.get(Object)" because "map" is null
System.out.println("val=" + val);
}
} Java里如果只声明 Map<String, String> map，不设置初始值，编译器会提示 java: variable map might not have been initialized
[weikeqin@computer test ]$javac MapTest.java
MapTest.java:8: error: variable map might not have been initialized
String val = map.get("k");
^
1 error
[weikeqin@computer test ]$在go里空map是可以读取的
package main
import "fmt"
func main() {
var emptyMap map[string]string
// 测试空map读取
v := emptyMap["k"]
fmt.Println("v=", v) // 不报错，v=空
} 当我们尝试去获取一个键对应的值的时候，如果这个键在 map 中并不存在，我们也会得到一个值，这个值是 value 元素类型的零值。
我们无法通过value值判断出，究竟是因为key不存在返回的零值，还是因为key本身对应的value就是零值。
查看值是否存在
package main
import "fmt"
func main() {
var emptyMap map[string]string
// 测试空map读取
v, ok := emptyMap["k"]
fmt.Println("ok=", ok, " v=", v) // ok=false v=空
}
但是声明未初始化的空map写入是会报错的 panic: assignment to entry in nil map
package main
import "fmt"
func main() {
var emptyMap map[string]string
// 测试空map写入
emptyMap["k"] = "v" // panic: assignment to entry in nil map
}
(2) map源码分析
源码位置: src/runtime/map.go
src/runtime/map.go
hmap 即 hash map的缩写
// A header for a Go map.
type hmap struct {
// Note: the format of the hmap is also encoded in cmd/compile/internal/reflectdata/reflect.go.
// Make sure this stays in sync with the compiler's definition.
count int // # live cells == size of map. Must be first (used by len() builtin)
flags uint8
B uint8 // log_2 of # of buckets (can hold up to loadFactor * 2^B items)
noverflow uint16 // approximate number of overflow buckets; see incrnoverflow for details
hash0 uint32 // hash seed
buckets unsafe.Pointer // array of 2^B Buckets. may be nil if count==0.
oldbuckets unsafe.Pointer // previous bucket array of half the size, non-nil only when growing
nevacuate uintptr // progress counter for evacuation (buckets less than this have been evacuated)
extra *mapextra // optional fields
}count 指的是当前map的大小，即当前存放的元素个数，必须放在第一个位置，因为通过len()函数时，会通过unsafe.Poiner从这里读取此值并返回
flags 可以理解为一个标记位
B 是一个对数，表示当前map持有的 buckets 数量(2^B)。但需要考虑一个重要因素装载因子，所以真正可以使用的桶只有loadFactor * 2^B 个，如果超出此值将触发扩容，默认装载因子是6.5
noverflow 溢出buckets数量
hash0 hash种子，在操作键值的时候，需要引入此值加入随机性
buckets 底层数组指针，指向当前map的底层数组指针
oldbuckets 同是底层数组指针，一般在进行map迁移的时候，用来指向原来旧数组。
nevacuate 进度计算器，表示扩容进度，小于此地址的 buckets 迁移完成
extra 可选字段，溢出桶专用，只要有桶装满就会使用
// mapextra holds fields that are not present on all maps.
type mapextra struct {
// If both key and elem do not contain pointers and are inline, then we mark bucket
// type as containing no pointers. This avoids scanning such maps.
// However, bmap.overflow is a pointer. In order to keep overflow buckets
// alive, we store pointers to all overflow buckets in hmap.extra.overflow and hmap.extra.oldoverflow.
// overflow and oldoverflow are only used if key and elem do not contain pointers.
// overflow contains overflow buckets for hmap.buckets.
// oldoverflow contains overflow buckets for hmap.oldbuckets.
// The indirection allows to store a pointer to the slice in hiter.
overflow *[]*bmap
oldoverflow *[]*bmap
// nextOverflow holds a pointer to a free overflow bucket.
nextOverflow *bmap
}参考资料
[1] src/runtime/map.go
[2] Go语言第一课 - 16｜复合数据类型：原生map类型的实现机制是怎样的？
[2] Runtime:源码解析Golang 的map实现原理
[3] 结构体转map[string]interface{}的若干方法