IT后端技术 · 2021年9月4日 0

Go:Map设计(1)

文章来源于互联网,如果该内容侵犯了您的合法权益,请邮件联系我们。 我们将在第一时间删除该内容。原文链接:Go:Map设计(1)———

【译文】原文地址
本文是三篇系列文章的第一篇,每一篇将涵盖Go map的一部分,建议你按顺序阅读。
map类型是Go语言的一种内置类型,通过映射表(hash table)原理来实现。在本文当中将探索map的不同部分的具体实现,包括:桶(buckets)存储键值对的结构、散列(键值对的索引)和负载因子(定义map容量应该增长的度量值)。

桶(buckets)

Go将键值对存储在一个桶列表中,每个桶将保存8个键值对,当map耗尽容量时,散列桶将加倍扩容。下面一张图粗略的表示了四个桶:

Go:Map设计(1)插图
map的buckets列表

我们将在下一篇文章中介绍存储桶中的键值对是如何存放的。如果map容量增加,桶的数量将翻倍至8个、16个等等。

当一个key/value对存入map当中,将根据key的散列值分配到对于的桶里。

hash

当key/value对赋值到map时,Go将基于key值生成一个hash值。我们以插入”foo=1″键值对为例,生成的hash值可能为15491954468309821754,将该值用于一个位操作,其掩码等于桶的数量值减1。在下图中给出了桶数为4的例子,可以得到掩码3,然后执行按位与操作:

Go:Map设计(1)插图1
value在桶中的分配

散列值不仅用于分配桶的值,还会有其他的操作。根据散列值的高8位,可以确认一个桶内的数组存储value的位置。如下图:

Go:Map设计(1)插图2
桶中的top hash table

因为桶内存在这个表,Go能够快速访问和比较key对于的value值。
根据程序中map的使用,Go需要一种可扩容的机制来存放更多的key/value值。

Map扩容

如果桶需要存储一个key/value,将为存储在内部可用的8个桶对于的槽内。如果没有桶可用的话,一个溢出桶会被创建并链接到当前桶中,并链接到当前桶上。

Go:Map设计(1)插图3
溢出桶

这种溢出的特性概括了桶的内部结构。然而增加溢出桶会降低map的性能。为了解决性能问题,Go将分配新的桶(当前数量的两倍)将在旧的桶和新桶之间建立连接。

Go使用它的负载系数来知道何时应该开始分配新桶和这个疏散过程。