Go map的底层原理

参考解析

题目来源：腾讯

答案：

这道题需要从两个维度来回答

  1. map的实现原理

    1. go map是基于hash table（哈希表）来实现的，冲突的解决采用拉链法

  2. map的底层结构

    1. hmap（哈希表）：每个hmap内含有多个bmap（buckets（桶）、lodbuckets（旧桶）、overflow（溢出桶））可以这样理解，每个哈希表都是由多个桶组成的
  1. type hmap struct {
  2.     count     int    //元素的个数
  3.     flags     uint8  //状态标志
  4.     B         uint8  //可以最多容纳 6.5 * 2 ^ B 个元素，6.5为装载因子
  5.     noverflow uint16 //溢出的个数
  6.     hash0     uint32 //哈希种子
  8.     buckets    unsafe.Pointer //指向一个桶数组
  9.     oldbuckets unsafe.Pointer //指向一个旧桶数组，用于扩容
  10.     nevacuate  uintptr        //搬迁进度，小于nevacuate的已经搬迁
  11.     overflow *[2]*[]*bmap     //指向溢出桶的指针
  12. }
  1.     *   buckets：一个指针，指向一个bmap数组、存储多个桶。
  2.     *   oldbuckets： 是一个指针，指向一个bmap数组，存储多个旧桶，用于扩容。
  3.     *   overflow：overflow是一个指针，指向一个元素个数为2的数组，数组的类型是一个指针，指向一个slice，slice的元素是桶(bmap)的地址，这些桶都是溢出桶。为什么有两个？因为Go map在哈希冲突过多时，会发生扩容操作。\[0\]表示当前使用的溢出桶集合，\[1\]是在发生扩容时，保存了旧的溢出桶集合。overflow存在的意义在于防止溢出桶被gc。
  4. 2.  bmap（哈希桶）： bmap是一个隶属于hmap的结构体，一个桶（bmap）可以存储8个键值对。如果有第9个键值对被分配到该桶，那就需要再创建一个桶，通过overflow指针将两个桶连接起来。在hmap中，多个bmap桶通过overflow指针相连，组成一个链表。
  1. type bmap struct {
  2.     //元素hash值的高8位代表它在桶中的位置，如果tophash[0] < minTopHash，表示这个桶的搬迁状态
  3.     tophash [bucketCnt]uint8
  4.     //接下来是8个key、8个value，但是我们不能直接看到；为了优化对齐，go采用了key放在一起，value放在一起的存储方式，
  5.     keys     [8]keytype   //key单独存储
  6.     values   [8]valuetype //value单独存储
  7.     pad      uintptr
  8.     overflow uintptr      //指向溢出桶的指针
  9. }