Golang源码分析系列之Map底层实现
映射也被称为哈希表(hash table)、字典。它是一种由key-value组成的抽象数据结构。大多数情况下，它都能在O(1)的时间复杂度下实现增删改查功能。若在极端情况下出现所有key都发生哈希碰撞时则退回成链表形式，此时复杂度为O(N)。
映射底层一般都是由数组组成，该数组每个元素称为桶，它使用hash函数将key分配到不同桶中，若出现碰撞冲突时候，则采用链地址法（也称为拉链法）或者开放寻址法解决冲突。下图就是一个由姓名-号码构成的哈希表的结构图：
Go语言中映射中key若出现冲突碰撞时候，则采用链地址法解决，Go语言中映射具有以下特点：
- 引用类型变量
- 读写并发不安全
- 遍历结果是随机的
数据结构
Go语言中映射的数据结构是runtime.hmap(runtime/map.go):
// A header for a Go map.
type hmap struct {
count int // 元素个数，用于len函数返回map元素数量
flags uint8 // 标志位，标志当前map正在写等状态
B uint8 // buckets个数的对数，即桶数量 = 2 ^ B
noverflow uint16 // overflow桶数量的近似值，overflow桶即溢出桶，即链表法中存在链表上的桶的个数
hash0 uint32 // 随机数种子，用于计算key的哈希值
buckets unsafe.Pointer // 指向buckets数组，如果元素个数为0时，该值为nil
oldbuckets unsafe.Pointer // 扩容时指向旧的buckets
nevacuate uintptr // 用于指示迁移进度，小于此值的桶已经迁移完成
extra *mapextra // 额外记录overflow桶信息
}