阅读 20

Go:Map设计(1)

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

桶(buckets)

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


map的buckets列表

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

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

hash

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


value在桶中的分配

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


桶中的top hash table

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

Map扩容

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


溢出桶

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

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

文章分类
后端
文章标签
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容, 请发送邮件至 gxwowoo@163.com 举报,一经查实,本站将立刻删除。
相关推荐