大家好,我是小道哥。
今天为大家讲解的面试专题是: map的实现原理

map定义

map是一种key-value键值对的存储结构,其中key是不能重复的,其底层实现采用的是hash表。

map的数据结构

首先我们先列出源码结构关键字段,实现在 src/runtime/map.go:

type hmap struct {
    count     int    // 元素的个数
    B         uint8  // buckets 数组的长度就是 2^B 个
    overflow uint16 // 溢出桶的数量

    buckets    unsafe.Pointer // 2^B个桶对应的数组指针
    oldbuckets unsafe.Pointer  // 发生扩容时,记录扩容前的buckets数组指针

    extra *mapextra //用于保存溢出桶的地址
}
type mapextra struct {
    overflow    *[]*bmap
    oldoverflow *[]*bmap

    nextOverflow *bmap
}
type bmap struct {
    tophash [bucketCnt]uint8
}

//在编译期间会产生新的结构体
type bmap struct {
    tophash [8]uint8 //存储哈希值的高8位
    data    byte[1]  //key value数据:key/key/key/.../value/value/value...
    overflow *bmap   //溢出bucket的地址
}

为了便于理解源码的结构,我们提炼关键字段并转换为图形模式:
描述

在go的map实现中,它的底层结构体是hmap,hmap里维护着若干个bucket数组 (即桶数组)。
Bucket数组中每个元素都是bmap结构,也即每个bucket(桶)都是bmap结构,【ps:后文为了语义一致,和方便理解,就不再提bmap了,统一叫作桶】 每个桶中保存了8个kv对,如果8个满了,又来了一个key落在了这个桶里,会使用overflow连接下一个桶(溢出桶)。

map中数据操作

了解了map的数据结构后,下面让我们学习一下在map中存取数据的过程:

GET获取数据

假设当前 B=4 即桶数量为2^B=16个,要从map中获取k4对应的value
描述

参考上图,k4的get流程可以归纳为如下几步:
计算k4的hash值。[由于当前主流机都是64位操作系统,所以计算结果有64个比特位]
通过最后的“B”位来确定在哪号桶,此时B为4,所以取k4对应哈希值的后4位,也就是0101,0101用十进制表示为5,所以在5号桶)
根据k4对应的hash值前8位快速确定是在这个桶的哪个位置(额外说明一下,在bmap中存放了每个key对应的tophash,是key的哈希值前8位),一旦发现前8位一致,则会执行下一步
对比key完整的hash是否匹配,如果匹配则获取对应value
如果都没有找到,就去连接的下一个溢出桶中找
有很多同学会问这里为什么要多维护一个tophash,即hash前8位?
这是因为tophash可以快速确定key是否正确,也可以把它理解成一种缓存措施,如果前8位都不对了,后面就没有必要比较了。

PUT存放数据

描述

map的赋值流程可总结位如下几步:
通过key的hash值后“B”位确定是哪一个桶,图中示例为4号桶。
② 遍历当前桶,通过key的tophash和hash值,防止key重复,然后找到第一个可以插入的位置,即空位置处存储数据。
③如果当前桶元素已满,会通过overflow链接创建一个新的桶,来存储数据。
关于hash冲突:当两个不同的 key 落在同一个桶中,就是发生了哈希冲突。冲突的解决手段是采用链表法:在 桶 中,从前往后找到第一个空位进行插入。如果8个kv满了,那么当前桶就会连接到下一个溢出桶(bmap)。

扩容

扩容的方式

  • 描述

由于map中不断的put和delete key,桶中可能会出现很多断断续续的空位,这些空位会导致连接的bmap溢出桶很长,导致扫描时间边长。这种扩容实际上是一种整理,把后置位的数据整理到前面。这种情况下,元素会发生重排,但不会换桶。

  • 描述

这种2倍扩容是由于当前桶数组确实不够用了,发生这种扩容时,元素会重排,可能会发生桶迁移
如图中所示,扩容前B=2,扩容后B=3,假设一元素key的hash值后三位为101,那么由上文的介绍可知,在扩容前,由hash值的后两位来决定几号桶,即 01 所以元素在1号桶。 在扩容发生后,由hash值得后三位来决定几号桶,即101所以元素会迁移到5号桶。

扩容的条件

首先我们了解下装载因子(loadFactor)的概念
loadFactor:=count / (2^B) 即 装载因子 = map中元素的个数 / map中当前桶的个数
通过计算公式我们可以得知,装载因子是指当前map中,每个桶中的平均元素个数。
扩容条件1装载因子 > 6.5 (源码中定义的)
这个也非常容易理解,正常情况下,如果没有溢出桶,那么一个桶中最多有8个元素,当平均每个桶中的数据超过了6.5个,那就意味着当前容量要不足了,发生扩容。
扩容条件2: 溢出桶的数量过多
当 B < 15 时,如果overflow的bucket数量超过 2^B。
当 B >= 15 时,overflow的bucket数量超过 2^15。
简单来讲,新加入key的hash值后B位都一样,使得个别桶一直在插入新数据,进而导致它的溢出桶链条越来越长。如此一来,当map在操作数据时,扫描速度就会变得很慢。及时的扩容,可以对这些元素进行重排,使元素在桶的位置更平均一些。
扩容时的细节

  • 在我们的hmap结构中有一个oldbuckets吗,扩容刚发生时,会先将老数据存到这个里面。

  • 每次对map进行删改操作时,会触发从oldbucket中迁移到bucket的操作【非一次性,分多次】

  • 在扩容没有完全迁移完成之前,每次get或者put遍历数据时,都会先遍历oldbuckets,然后再遍历buckets。

    注意事项

  • 对map数据进行操作时不可取地址。常见的错误用例如下:
    这种情况会发生编译错误,因为map元素是无法取址的,也就是说,你可以得到m[1],但是无法对它的值作出任何修改。如果你想修改value,可以使用带指针的value,如下:
    不知道各位道友有没有疑惑,为什么go中要禁止对map的元素进行取址呢?这是因为map 会随着元素数量的增长而重新分配更大的内存空间,会导致之前的地址无效。

  • map是线程不安全的
    在同一时间点,两个 goroutine 对同一个map进行读写操作是不安全的。举个栗子:
    某map桶数量为4,即B=2。此时 goroutine1来插入key1, goroutine2来读取 key2. 可能会发生如下过程:
    ① goroutine2 计算key2的hash值,B=2,并确定桶号为1。
    ② goroutine1添加key1,触发扩容条件。
    ③ B=B+1=3, buckets数据迁移到oldbuckets。
    ④ goroutine2从桶1中遍历,获取数据失败。
    在工作中,当我们涉及到对一个map进行并发读写时,一般采用的做法是采用golang中自带的mutex锁

  • map的底层数据结构

  • map的GET操作和PUT操作过程

  • map的扩容条件

  • map的注意事项:不可对元素取址、线程不安全

后语

如果大家对本文提到的面试技术点有任何问题,都可以在评论区进行回复哈,我们共同学习,一起进步!
关注公众号[简道编程],每天一个后端技术面试点
描述