golang map源码详解
本文将主要分析一下golang中map的实现原理，并对使用中的常见问题进行讨论。进行分析的golang版本为1.9。
golang中的map是用hashmap作为底层实现的，在github的源码中相关的代码有两处：runtime/hashmap.go定义了map的基本结构和方法，runtime/hashmap_fast.go提供了一些快速操作map的函数。
map基本数据结构
map的底层结构是hmap（即hashmap的缩写），核心元素是一个由若干个桶（bucket，结构为bmap）组成的数组，每个bucket可以存放若干元素（通常是8个），key通过哈希算法被归入不同的bucket中。当超过8个元素需要存入某个bucket时，hmap会使用extra中的overflow来拓展该bucket。下面是hmap的结构体。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
type hmap struct { count int // # 元素个数 flags uint8 B uint8 // 说明包含2^B个bucket noverflow uint16 // 溢出的bucket的个数 hash0 uint32 // hash种子 buckets unsafe.Pointer // buckets的数组指针 oldbuckets unsafe.Pointer // 结构扩容的时候用于复制的buckets数组 nevacuate uintptr // 搬迁进度（已经搬迁的buckets数量） extra *mapextra } |
在extra中不仅有overflow，还有oldoverflow（用于扩容）和nextoverflow（prealloc的地址）。
bucket（bmap）的结构如下
|
1 2 3 4 5 6 7 8 9 10 11 |
type bmap struct { // tophash generally contains the top byte of the hash value // for each key in this bucket. If tophash[0] < minTopHash, // tophash[0] is a bucket evacuation state instead. tophash [bucketCnt]uint8 // Followed by bucketCnt keys and then bucketCnt values. // NOTE: |