golang map实现原理

矫情吗；* 2022-09-12 04:51 187阅读 0赞

> 尽管map经常用，但是对它底层原理了解的不是很深刻，面试官喜欢问，就写个笔记，都是地鼠文档上摘抄过来的。

### 什么是Map ###

#### key，value存储 ####

最通俗的话说Map是一种通过key来获取value的一个数据结构，其底层存储方式为数组，在存储时key不能重复，当key重复时，value进行覆盖，我们通过key进行hash运算（可以简单理解为把key转化为一个整形数字）然后对数组的长度取余，得到key存储在数组的哪个下标位置，最后将key和value组装为一个结构体，放入数组下标处。

### Go中Map的使用 ###

直接用代码描述，直观，简单，易理解

//直接创建初始化一个mao
    var mapInit = map[string]string {"xiaoli":"湖南", "xiaoliu":"天津"}
    //声明一个map类型变量,
    //map的key的类型是string，value的类型是string
    var mapTemp map[string]string
    //使用make函数初始化这个变量,并指定大小(也可以不指定)
    mapTemp = make(map[string]string,10)
    //存储key ，value
    mapTemp["xiaoming"] = "北京"
    mapTemp["xiaowang"]= "河北"
    //根据key获取value,
    //如果key存在，则ok是true，否则是flase
    //v1用来接收key对应的value,当ok是false时，v1是nil
    v1,ok := mapTemp["xiaoming"]
    fmt.Println(ok,v1)
    //当key=xiaowang存在时打印value
    if v2,ok := mapTemp["xiaowang"]; ok{
        fmt.Println(v2)
    }
    //遍历map,打印key和value
    for k,v := range mapTemp{
        fmt.Println(k,v)
    }
    //删除map中的key
    delete(mapTemp,"xiaoming")
    //获取map的大小
    l := len(mapTemp)
    fmt.Println(l)

### Go中Map的实现原理 ###

知其然，知其所以然。map的源码位于 src/runtime/map.go中 ，map同样也是数组存储的的，每个数组下标处存储的是一个bucket,这个bucket的类型见下面代码，每个bucket中可以存储8个kv键值对，当每个bucket存储的kv对到达8个之后，会通过overflow指针指向一个新的bucket，从而形成一个链表,看bmap的结构，我想大家应该很纳闷，没看见kv的结构和overflow指针啊，事实上，这两个结构体并没有显示定义，是通过指针运算进行访问的。

//bucket结构体定义 b就是bucket
    type bmap{
        // 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.
        //翻译：top hash通常包含该bucket中每个键的hash值的高八位。
        如果tophash[0]小于mintophash，则tophash[0]为桶疏散状态    //bucketCnt 的初始值是8
        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.    //翻译：接下来是bucketcnt键，然后是bucketcnt值。
        注意：将所有键打包在一起，然后将所有值打包在一起，    使得代码比交替键/值/键/值/更复杂。但它允许//我们消除可能需要的填充，    例如map[int64]int8./后面跟一个溢出指针}

> 每个map的底层结构是hmap，是有若干个结构为bmap的bucket组成的数组。每个bucket底层都采用链表结构。

type hmap struct {
        count     int    // 元素个数
        flags     uint8  // 用来标记状态
        B         uint8  // 扩容常量相关字段B是buckets数组的长度的对数 2^B
        noverflow uint16 // noverflow是溢出桶的数量，当B<16时，为精确值,当B>=16时，为估计值                       
        hash0     uint32 // 是哈希的种子，它能为哈希函数的结果引入随机性，这个值在创建哈希表时确定，并在调用哈希函数时作为参数传入
    
        buckets    unsafe.Pointer // 桶的地址 
        oldbuckets unsafe.Pointer // 旧桶的地址，用于扩容 
        nevacuate  uintptr        // 搬迁进度，扩容需要将旧数据搬迁至新数据，这里是利用指针来比较判断有没有迁移 
    
        extra *mapextra // 用于扩容的指针
    }
    
    type mapextra struct {
        overflow    *[]*bmap
        oldoverflow *[]*bmap
        // nextOverflow holds a pointer to a free overflow bucket.
        nextOverflow *bmap
    }