Go面试题(三)：map的实现原理

大家好，我是小道哥。

今天为大家讲解的面试专题是: 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倍容量扩容

这种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数据进行 *** 作时不可取地址。常见的错误用例如下：

type Student struct {
	Name string
	Age  int
}

func f1() {
	m := map[int]Student{
		1: Student{Age: 15, Name: "jack"},
		2: Student{Age: 16, Name: "danny"},
		3: Student{Age: 17, Name: "andy"},
	}
	m[1].Name = "JACK"
}

这种情况会发生编译错误，因为map元素是无法取址的，也就是说，你可以得到m[1]，但是无法对它的值作出任何修改。如果你想修改value，可以使用带指针的value，如下：

func f2() {
	m := map[int]*Student{
		1: &Student{Age: 15, Name: "jack"},
		2: &Student{Age: 16, Name: "danny"},
		3: &Student{Age: 17, Name: "andy"},
	}
	m[1].Name = "JACK"
}

不知道各位道友有没有疑惑，为什么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锁

type Resource struct {
	sync.RWMutex
	m map[string]int
}

func main() {
	r := Resource{m: make(map[string]int)}

	go func() { //开一个goroutine写map
		for j := 0; j < 100; j++ {
			r.Lock()
			r.m[fmt.Sprintf("resource_%d", j)] = j
			r.Unlock()
		}
	}()
	go func() { //开一个goroutine读map
		for j := 0; j < 100; j++ {
			r.RLock()
			fmt.Println(r.m[fmt.Sprintf("resource_%d", j)])
			r.RUnlock()
		}
	}()
}

面试点总结

map的底层数据结构

map的GET *** 作和PUT *** 作过程

map的扩容条件

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

后语

如果大家对本文提到的面试技术点有任何问题，都可以在评论区进行回复哈，我们共同学习，一起进步！

关注公众号[简道编程]，每天一个后端技术面试点