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: packing all the keys together and then all the values together makes the // code a bit more complicated than alternating key/value/key/value/... but it allows // us to eliminate padding which would be needed for, e.g., map[int64]int8. // Followed by an overflow pointer. } |
- tophash用于记录8个key哈希值的高8位,这样在寻找对应key的时候可以更快,不必每次都对key做全等判断。
- 注意后面几行注释,hmap并非只有一个tophash,而是后面紧跟8组kv对和一个overflow的指针,这样才能使overflow成为一个链表的结构。但是这两个结构体并不是显示定义的,而是直接通过指针运算进行访问的。
- kv的存储形式为”key0key1key2key3…key7val1val2val3…val7″,这样做的好处是:在key和value的长度不同的时候,节省padding空间。如上面的例子,在map[int64]int8中,4个相邻的int8可以存储在同一个内存单元中。如果使用kv交错存储的话,每个int8都会被padding占用单独的内存单元(为了提高寻址速度)。
hmap的结构差不多如图
map的访问
以mapaccess1为例,部分无关代码被修改。
1 2 3 4 5 6 7 8 9 10 11 12 |