Golang中的map实现
总所周知，大多数语言中，字典的底层是哈希表，而且其算法也是十分清晰的。无论采用链表法还是开放寻址法，我们都能实现一个简单的哈希表结构。对于Go来说，它是具体如何实现哈希表的呢？以及，采取了哪些优化策略呢？ 内存模型 map在内存的总体结构如下图所示。 头部结构体hmap type hmap struct { count int // 键值对个数 flags uint8 B uint8 // 2^B = 桶数量 noverflow uint16 // 溢出桶的个数 hash0 uint32 // hash seed buckets unsafe.Pointer // 哈希桶 oldbuckets unsafe.Pointer // 原哈希桶，扩容时为非空 nevacuate uintptr // 扩容进度，地址小于它的桶已被迁移了 extra *mapextra // optional fields } hmap即为map编译后的内存表示，这里需要注意的有两点。 B的值是根据负载因子(LoadFactor)以及存储的键值对数量，在创建或扩容时动态改变 buckets是一个指针，它指向一个bmap结构 桶结构体bmap type bmap struct { // tophash数组可以看做键值对的索引 tophash [bucketCnt]uint8 // 实际上编译器会动态添加下述属性 // keys [8]keytype // values [8]valuetype // padding uinptr // overflow uinptr } 虽然bmap结构体中只有一个tophash数组，但实际上，其后跟着8个key的槽位、8个value的槽位、padding以及一个overflow指针。如下图所示...