Golang map原理分析(一)

众所周知，Golang自带的map是非并发安全的，其实现原理也是面试中常被提及到的，因此作者带着好奇心尝试阅读了下其源码，并总结成文章分享给大家，希望对大家有所帮助。此外，若文章中有写错的地方，欢迎大家指正！

map的源码大家可以在$GOROOT/src/runtime/map.go看到，其最核心的数据结构是hmap和bmap，其具体申明如下：

type hmap struct {
  //map中的kv键值对数
  count     int 
  //标记map当前的状态
  flags     uint8
  //哈希桶的基数，bucket数量等于2^B
  B         uint8
  //溢出桶的近似数
  noverflow uint16
  //哈希种子
  hash0     uint32
  //哈希桶的首地址，哈希桶对应的数据结构是bmap
  buckets    unsafe.Pointer
  //如果map需要扩容的话，就会将buckets赋值给该字段，扩容有等量扩容和双倍扩容
  oldbuckets unsafe.Pointer
  //指示扩容进度，小于此地址的 buckets 迁移完成
  nevacuate  uintptr
  extra *mapextra // optional fields
}

bmap是保存key和value的实体，其结构为：

// A bucket for a Go map.
type bmap struct {
  tophash [bucketCnt]uint8
}

(根据网上的教程)这里的bmap只是一个表象，在编译期间会动态地创建一个新的bmap结构用来保存数据实体：

type bmap struct {
    topbits  [8]uint8
    keys     [8]keytype
    values   [8]valuetype
    pad      uintptr
    overflow uintptr
}

bmap为了避免key和value类型占用内存字节数相差大，导致在存储过程中字节对齐机制会使内存出现大量内存碎片，所以将key和value分开存储。hmap对应一组哈希桶，一个桶中包含一组bmap，组内bmap通过链表方式存储，默认一个bmap可以存储8个键值对，当超过8个时会新建一个bmap并链接至该桶链表的末尾。bmap的存储模型细节如下：

下一篇文章我将分享有关map相关操作的源码，如果你有疑问，欢迎你在评论区中指出。如果你觉得作者写得不错，欢迎你关注我的微信公众号“灵均的编程之旅”！