Golang语言map底层实现原理解析.pdfVIP

Golang语⾔map底层实现原理解析 在开发过程中，map是必不可少的数据结构，在Golang中，使⽤map或多或少会遇到与其他语⾔不⼀样的体验，⽐如访问不 存在的元素会返回其类型的空值、map的⼤⼩究竟是多少，为什么会报cannot take the address of错误，遍历map的随机性 等等。 本⽂希望通过研究map的底层实现，以解答这些疑惑。 基于Golang 1.8.3 1.数据结构及内存管理 hashmap的定义位于 src/runtime/hashmap.go中，⾸先我们看下hashmap和bucket的定义： type hmap struct { count int //元素的个数 flags uint8 //状态标志 B uint8 //可以最多容纳 6.5 * 2 ^ B个元素，6.5为装载因⼦ noverflow uint16 //溢出的个数 hash0 uint32 //哈希种⼦ buckets unsafe.Pointer //桶的地址 oldbuckets unsafe.Pointer //旧桶的地址，⽤于扩容 nevacuate uintptr搬迁进度，⼩于// nevacuate的已经搬迁 overflow *[2]*[]*bmap } 其中，overflow是⼀个指针，指向⼀个元素个数为2的数组，数组的类型是⼀个指针，指向⼀个slice，slice的元素是桶(bmap) 的地址，这些桶都是溢出桶；为什么有两个？因为Go map在hash冲突过多时，会发⽣扩容操作，为了不全量搬迁数据，使⽤ 了增量搬迁，[0]表⽰当前使⽤的溢出桶集合，[1]是在发⽣扩容时，保存了旧的溢出桶集合；overflow存在的意义在于防⽌溢出 桶被gc。 // A bucket for a Go map. type bmap struct { //每个元素hash值的⾼8位，如果tophash[0] minTopHash，表⽰这个桶的搬迁状态 tophash [bucketCnt]uint8 //接下来是8个key、8个value，但是我们不能直接看到；为了优化对齐，go采⽤了key放在⼀起，value放在⼀起的存储⽅式， //再接下来是hash冲突发⽣时，下⼀个溢出桶的地址 } tophash的存在是为了快速试错，毕竟只有8位，⽐较起来会快⼀点。 从定义可以看出，不同于STL中map以红⿊树实现的⽅式，Golang采⽤了HashTable的实现，解决冲突采⽤的是链地址法。也 就是说，使⽤数组+链表来实现map。特别的，对于⼀个key，⼏个⽐较重要的计算公式为: key hash hashtop bucket index hash := alg.hash(key, top := uint8(hash (sys.PtrSize*8bucket := hash (uintptr(1)h.B - 1)，即 hash key uintptr(h.hash0)) - 8)) % 2^B 例如，对于B = 3，当hash(key) = 4时， hashtop = 0， bucket = 4，当hash(key) = 20时，hashtop = 0， bucket = 4；这个例 ⼦我们在搬迁过程还会⽤到。 内存布局类似于这样： hashmap-buckets 2.创建 - makemap map的创建⽐较简单，在参数校验之后，需要找到合适的B来申请桶的内存空间，接着便是穿件hmap这个结构，以及对它的 初始化。 makemap 3.访问 - mapaccess 对于给定的⼀个key，可以通过下⾯的操作找到它是否存在 image.png ⽅法定义为 // returns key, if not find, returns nil func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer // returns key and exist. if not find, returns nil, false func mapaccess2(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, bool) //