Go 语言的字典类型其实是一个哈希表（hash table）的特定实现，它能存储的不是单一值的集合，而是键-元素对的集合。在这个实现中，键和元素的最大不同在于，前者的类型是受限的，而后者却可以是任意类型的。

带着问题

• golang中map是指针还是引用？
• map的底层结构是什么样的？
• map的键值映射过程？
• 键不能是哪些类型？为什么？
• map是什么情况下扩容？
• for range map为什么是无序的？

map是指针

package main

import (
	"fmt"
	"unsafe"
)

func fn(m map[int]int) {
	fmt.Printf("in fn function, m.address is:%p\n", m)
	m = make(map[int]int)
	fmt.Printf("in fn function, realloc mem %p\n", make(map[int]int))
	m[2] = 2
	fmt.Println()
}

func main() {
	var m map[int]int
	//调用函数前map信息
	fmt.Println("before, m.size:", unsafe.Sizeof(m))
	fmt.Printf("before, m.address is:%p\n", m)
	fmt.Printf("before, &m.address is:%p\n", &m)
	fmt.Println()

	fn(m)
	fmt.Println("m is nil ? ", m == nil)

	//调用函数后map信息
	fmt.Println("after, m.size:", unsafe.Sizeof(m))
	fmt.Printf("after, m.address is:%p\n", m)
	fmt.Printf("after, &m.address is:%p\n", &m)
	fmt.Println()

	//调用函数后访问map元素
	fmt.Println("after, access element:", m[2])
}

//分析：
//map是go里边的一个指针
//函数调用map后，值传递了一个指针副本
//make(map[int]int)后，生成了一个新的map，再赋值给了副本
//后续操作都是针对副本的操作，不会传递出函数

//总结：
//函数调用map时，不要在函数内部重新构造map，否则所做操作不会传递出函数

map基础数据结构

map底层源码位置：$GOROOT/src/runtime/hashmap.go

map的底层结构是hmap（即hashmap的缩写），核心元素是一个由若干个桶(bucket，结构为bmap）组成的数组，每个bucket可以存放若干元素（通常是8个），key通过哈希算法被归入不同的bucket中。当超过8个元素需要存入某个bucket时，hmap会使用extra中的overflow来拓展该bucket（链地址法）。

• hmap结构

type hmap struct {
    count     int    // map元素的个数
    flags     uint8  
    B         uint8  // 可以最多容纳 6.5 * 2 ^ B 个元素，6.5为装载因子，B可以理解为已扩容的次数
    noverflow uint16 // 溢出的bucket个数
    hash0     uint32 // 哈希种子

    buckets    unsafe.Pointer // buckets数组地址
    oldbuckets unsafe.Pointer // 旧桶的地址，用于扩容，只有扩容的时候才不为nil
    nevacuate  uintptr        // 搬迁进度，小于nevacuate的已经搬迁
}

• 哈希桶(bucket)结构

// A bucket for a Go map.
type bmap struct {
    // 每个key的hash值的高8位，如果tophash[0] < minTopHash，表示这个桶的搬迁状态，不懂？
    tophash [bucketCnt]uint8  //bucketCnt是常量，值为8
    // 接下来，将所有键打包在一起，然后将所有值打包在一起；为了优化对齐，go采用了key放在一起，value放在一起的存储方式，
    //kv的存储形式为”key0key1key2key3…key7val1val2val3…val7″，这样做的好处是：在key和value 
    //的长度不同的时候，节省padding空间。
    //源码给的一个例子，在map[int64]int8中，4个相邻的int8可以储在同一个内存单元中。如果使用kv
    //交错存储的话，由于字节对齐，每个int8都会被padding占用单独的内存单元（为了提高寻址速度）
    // 再接下来是hash冲突发生时，下一个溢出桶的地址
}

• 整体结构
  

映射过程

1. 先把键值作为参数传给这个哈希表。哈希表会先用哈希函数把键值转换为哈希值，通常是一个无符号整数。
2. 一个哈希表会持有一定数量的桶（bucket），也可称之为哈希桶，这些哈希桶会均匀地储存其所属哈希表收纳的那些键 - 元素对。
3. 利用哈希值的低位寻找当前key属于hmap中的哪个bucket。
4. 利用哈希值的高位，遍历bucket中所有key对应的高位哈希值，看是否相等，若找不到，表示没有要查找的值
5. 若有相等的，再用键值本身去对比一次。为什么还要对比？原因是，不同值的哈希值是可能相同的(哈希碰撞)
6. 最后，只有键的哈希值和键值都相等，才能说明查找到了匹配的键 - 元素对。

键类型受限

Go 语言字典的键类型不可以是函数类型、字典类型和切片类型。

• Go 语言规范规定，键类型的值必须要支持判等操作。
• 函数类型、字典类型和切片类型的值并不支持判等操作。

package main

import "fmt"

func main() {
	//切片类型
	//var badMap1 = map[interface{}]int{
	//	"1": 1,
	//	[]int{2}: 2, // 这里会引发panic：runtime error: hash of unhashable type func()
	//	3: 3,
	//}
	//fmt.Println(len(badMap1))

	//函数类型
	//var badMap2 = map[interface{}]int{
	//	"1":1,
	//	func(){}:2, //这里会引发panic
	//}
	//fmt.Println(len(badMap2))

	//字典类型
	var badMap3 = map[interface{}]int{
		"1":1,
		map[int]int{1:2,}:3, //这里会引发panic
	}
	fmt.Println(len(badMap3))
}

• 更深层原因，在上边map映射过程讲解中，由于哈希碰撞的存在，哈希值一样，键值也不一定一样。如果键类型的值之间无法判断相等，那么此时这个映射的过程就没办法继续下去了。
• 从映射过程得出，求哈希和判等操作的速度越快，对应的类型就越适合作为键类型
• 优先选用数值类型和指针类型，通常情况下类型的宽度越小越好。若非要选择字符串类型，最好对键值的长度进行额外的约束

map扩容

随着元素的增加，在一个bucket链中寻找特定的key会变得效率低下，所以在插入的元素个数/bucket个数达到某个阈值（加载因子）时，map会进行扩容，代码中详见 hashGrow函数。

• 加载因子越小，说明空间空置率高，空间使用率小，但是加载因子越大，说明空间利用率上去了，但是“产生冲突机会”高了
• Golang的map的加载因子的公式是：map长度 / 2^B阈值是6.5。其中B可以理解为已扩容的次数
• 首先创建bucket数组，长度为原长度的两倍
• 扩容完成后，每个key的hash对应到两个bucket（一个新的一个旧的）。oldbucket不会立即被转移到新的bucket下，只有当访问到具体的某个bucket的时候，会把bucket中的数据转移到新的bucket中。
• 在下一次扩容前，会不断进行迁移，直到完成
• 扩容时机理解：在没有溢出时hashmap总共可以存储8(2^B)
  个KV对，当hashmap已经存储到6.5(2^B)个KV对时表示hashmap已经趋于溢出，即很有可能在存值时用到overflow链表，这样会增加hitprobe和missprobe。为了使hashmap保持读取和查找的高性能，在hashmap快满时需要在新分配的bucket中重新hash元素并拷贝，源码中称之为evacuate。
• hitprobe是指找到一个存在的key平均需要找多少次。missprobe是指找到一个不存在的key平均需要找多少次。

值为nil的map

• 添加键 - 元素对，会引发panic
• 其余任何操作，都不会引起错误
• 可以用v,ok:=aMap[key]判断key是否存在

package main

import "fmt"

func main()  {
	var aMap map[string]int
	//添加键-元素对
	//aMap["1"] = 1 //会引发panic: assignment to entry in nil map

	//访问
	fmt.Println(aMap["1"]) //0
	//
	//删除
	delete(aMap,"1") //成功

	//访问长度
	fmt.Println(len(aMap)) //0
}

map无序

• map输出顺序与插入顺序不一致
  map是根据key的hash值来定位buckets数组的索引位置，具体为bucket := hash & (uintptr(1)<<h.B - 1)，即 hash % 2^B，是key的hash值与buckets数组长度，作与运算后得到，buckets中存储顺序本就和插入顺序不同

package main

import "fmt"

func main() {
	aMap := map[string]int{
		"one":   1,
		"two":   2,
		"three": 3,
		"four":  4,
		"five":  5,
		"six":   6,
		"seven": 7,
		"eight": 8,
		"nine":  9,
		"ten":   10,
	}

	for k, v := range aMap {
		fmt.Println(k, v)
	}
}
输出顺序与插入顺序就是不一致

• for range map无序
  go-in-action中有说明，翻译过来就是：当使用range循环迭代map时，迭代顺序不是特定的，也不保证与下一个迭代顺序相同；自从Go 1.0发布以来，运行时已经将map迭代顺序随机化；设计者意识到程序员开始依赖Go早期版本的稳定迭代顺序，但这会由于实现之间的差异，导致可移植性bug；可用如下方式实现顺序输出：

import "sort"

var m map[int]string
var keys []int
for k := range m {
    keys = append(keys, k)
}
sort.Ints(keys)
for _, k := range keys {
    fmt.Println("Key:", k, "Value:", m[k])
}

其它

• 删除掉map中的元素是否会释放内存？
  不会，删除操作仅仅将对应的tophash[i]设置为empty，并非释放内存。若要释放内存只能等待指针无引用后被系统gc。

• 为什么bucket中不存储key的全部hash值，而只存储高8位？
  在查找/删除/插入一个 key 的时候，先判断两个 key hash 的高8位是否相等，如果不等，则不必比较 key 的内容。故保存hash 值的高8位可以作为第一步的粗略过滤，很多时候可以省掉比较两个 key 的内容，因为比较两个 key 是否相等的代价远比两个 uint8 的代价高。而不存储整个 hash 值，是考虑内存的占用会多很多。

• 创建map时，可以适当预估map的容量。
  若不指定大小，bucket 数组默认为1，随着插入的元素增多，会增长成2，4，8，16等。这中间要经历很多次的map扩容、元素拷贝。

package tests

import (
	"testing"
)

func test(m map[int]int) {
	for i := 0; i < 10000; i++ {
		m[i] = i
	}
}

func BenchmarkMap(b *testing.B) {
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		m := make(map[int]int) //没有指定容量
		test(m)
	}
}

func BenchmarkMapCap(b *testing.B) {
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		m := make(map[int]int, 10000)   //带容量的初始化
		test(m)
	}
}
运行1：
//-bench表示是基准测试
//-benchtime设置运行时间，默认是1秒
//-run=none用于不运行单元测试代码
//BenchmarkMap-4其中的4表示运行时对应的GOMAXPROCS值
F:\Development\Go\src\otherPractice\go36\tests>go test -v -bench=. -benchtime=3s -run=none
goos: windows
goarch: amd64
pkg: otherPractice/go36/tests
BenchmarkMap-4              3000           1350897 ns/op
BenchmarkMapCap-4          10000            613401 ns/op    
PASS
ok      otherPractice/go36/tests        10.869s

运行2：找出不指定map容量时间慢的原因
//-benchmem可以提供每次操作分配内存的次数，以及每次操作分配的字节数。从结果我们可以看到,
//指定容量的函数，每次操作进行11次内存分配，而不指定容量的函数的那个要分配275次；性能高的
//每次操作分配322236个字节内存，而慢的每次需要分配1347727 字节的内存。
F:\Development\Go\src\otherPractice\go36\tests>go test -v -bench=. -benchtime=3s -benchmem -run=none
goos: windows
goarch: amd64
pkg: otherPractice/go36/tests
BenchmarkMap-4              3000           1347727 ns/op          687122 B/op        275 allocs/op
BenchmarkMapCap-4          10000            641282 ns/op          322236 B/op         11 allocs/op
PASS
ok      otherPractice/go36/tests        11.283s