07-字典

map中存储的不是单一值的集合,而是键值对的集合。

一个键和一个值,分别代表了一个从属于某一类型的独立值,把它们两个捆绑在一起就是一个键值对。

0.1. 键类型约束

Go语言的字典类型其实是一个哈希表的特定实现,在这个实现中,键的类型是受限的,值可以是任意类型。

把键理解为元素的一个索引,在哈希表中通过键查找与它成对的那个元素。键与值的对应关系称为映射,哈希表的映射过程就存在于对键值对的增删改查操作中。

映射过程的第一步就是键值转换为哈希值:Go中的每个键都是有它的哈希值代表,字典不会独立存储任何键值,但会独立存储它们的哈希值。

Go语言字典的键类型不支持函数类型、字典类型和切片类型

Go语言规范规定,在键类型的值之间,必须可以使用操作符==!=,也就是必须支持判等操作,上述三种类型的值不支持判等操作,所以字典的键类型不能是这些类型。

如果键的类型是接口类型,那么键值的实际类型也不能是上述三种类型,否则程序运行中会引发panic

如果键的类型是数组类型,那么确保该类型的元素类型不是上述三种类型

如果键的类型是结构体,那么保证其中字段类型的合法性

因为”哈希碰撞“的存在,Go语言首先用键的哈希值去进行比对,如果键的哈希值相同,在用键本身去比对,如果键类型的值之间无法判等,那么这个映射过程就无法继续进行。

0.2. 键类型的优先选择

在映射的过程中,有两个重要且耗时的操作:

  1. 把键值转换为哈希值
  2. 把要查找的键值与哈希桶中的键值做对比

但从性能的角度,求哈希和判等操作的速度越快,对应的类型就越适合作为键类型。

Go语言中所有的基本类型、指针类型、数组类型、结构体类型和接口类型都要一套各自的算法,其中包含哈希和判等。

0.2.1. 哈希算法

基本类型:

类型的宽度越小的类型求哈希的速度越快。

类型的宽度是指它的单个值需要占用的字节数。

在基本类型中,有限选择数值类型和指针类型,通常情况下类型的宽度越小越好。

高级类型:

  1. 对数组类型值的求哈希实际上是依次求得它的每个元素的哈希值并进行合并,所以速度取决于它的元素类型以及它的长度。
  2. 对于结构体类型的值求哈希实际上就是它的所有字段求哈希并进行合并,关键在于各个字段的类型以及字段的数量。
  3. 对于接口类型,具体的哈希算法由值的实际类型决定。

不建议使用高级类型作为字典的键,不仅因为求哈希和判等速度慢,而且它们中的值存在变数。

除了添加键值对,在一个值为nil的字典上做任何操作都不会引起错误

上次修改: 25 November 2019