欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

go语言学习笔记(九)——map

程序员文章站 2024-02-17 10:10:52
...
  • 前言

        map是键值对的集合,在Go语言规范中,我们也可以将其称为“键-元素对”。Go语言中map是一个哈希表(hash table)实现的。在这个实现中,键的类型是受限的,而元素却可以是任意类型的。键和元素对映射过程的第一步就是把键值转换为hash值

  • 问题:map的键类型不能是哪些类型

       在Go语言规范中,规定Map键类型不可以是函数类型,map类型和切片类型

  • 问题解析:

       Go语言规范规定,在键类型的值之间必须可以施加操作符==和!= 。换句话说,键类型必须要支持判等操作。由于函数类型,map类型和切片类型的值不支持判等操作,所以map的键不能是这些类型

       另外,如果键的类型如果是接口类型的,那么键值的实际类型也不能是上述的三种类型,否则在程序运行过程会引发panic。举个例子:

    var badMap2=map[interface{}]int{
        "1":1,
        []int{2}:2, //这里会引发panic
        3:3
    }

这里的变量badMap2的类型是键类型为interface{},值类型为int的map类型。这样声明并不会引起什么错误。或者说,我通过这样的声明躲过了Go语言编译器的检查。

但是,在运行的时候,Go语言的运行时系统(runtime库)就会抛出panic错误,所以最好不要把字典类的键类型设定为任何接口类型。

如果键的类型是数组类型,那么还要确保该类型的元素类型不是函数类型、字典类型或切片类型。

比如,由于类型[1][]string的元素类型是[string],所以它也不能作为字典类型的键类型。另外,如果键类型是结构体类型(struct),那么还要保证其中字段的类型的合法性。

为什么键类型必须支持判等操作?因为只有哈希值和键值都相等,说明查找到了匹配的键 - 元素对。

  • 知识拓展

1.哈希桶

哈希值是一个无符号的整数,一个哈希表会持有一定数量的桶(bucket)。上述的map键值映射就是哈希表先用这个键的哈希值的低几位去定位到一个哈希桶(bucket,均匀地存储所属哈希表中的键-元素对),然后再去这个哈希桶中查找这个键,而一旦找到了这个键,就能找到对应的元素值。

判等操作过程也需要哈希桶。Go 语言一旦定位到了某一个哈希桶,那么就会试图在这个桶中查找键值。具体是怎么找的呢?

首先,每个哈希桶都会把自己包含的所有键的哈希值存起来。Go 语言会用被查找键的哈希值与这些哈希值逐个对比,看看是否有相等的。如果一个相等的都没有,那么就说明这个桶中没有要查找的键值,这时 Go 语言就会立刻返回如果有相等的,那就再用键值本身去对比一次。

为什么还要对比?原因是,不同值的哈希值是可能相同的。这有个术语,叫做“哈希碰撞”。 所以,即使哈希值一样,键值也不一定一样。如果键类型的值之间无法判断相等,那么此时这个映射的过程就没办法继续下去了。最后,只有键的哈希值和键值都相等,才能说明查找到了匹配的键 - 元素对。

哈希桶里的结构是,“键的哈希值-内部结构”对的集合,这个内部结构的结构是“键1元素1键2元素2键3元素3”,是一块连续的内存。在通过键的哈希值定位找到哈希桶和那个“键的哈希值-内部结构”对之后,就开始在这个内部结构里找有没有这个键。

2.应该优先考虑哪些类型作为map的键类型

求哈希和判等操作的速度越快,对应的类型就越适合作为键类型

求哈希为例,宽度越小的类型速度越快,如bool,整数类型、浮点数类型、复数类型和指针类型。

对于字符串类型,由于它的宽度是不定的,所以要看它的值的具体长度,长度越短求哈希越快。

类型的宽度是指它的单个值需要占用的字节数,如bool、int8和uint8类型的值需要占用的字节数都是1,宽度就是1.

高级类型中,数组类型的值求哈希实际上是依次求得它每个元素的哈希值并键合并,所以速度就取决于元素类型以及长度。

结构体类型的值求哈希,实际上是对它的所有字段求哈希并进行合并,所以关键在于它的各个字段的类型以及字段的数量。

对于接口类型,具体的哈希算法由值的实际类型决定。

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

比如,对于一个数组,我们可以任意改变元素值,在变化前后,它代表了两个不同的键值。

把接口类型作为字段的键类型最危险,会导致panic错误,甚至程序崩溃。

在基本类型中,优先选用数值类型和指针类型作为键值,因为其宽度最小。

3.在值为nil的map上执行读操作会成功吗?写操作呢?

当我们仅声明而不初始化一个字典类型的变量的时候,它的值会是nil。

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

而如果我们要在这个值为nil的字典中添加键元素对时,Go的runtime系统会抛出一个panic。

  • 思考题

在同一时间段内但在不同的 goroutine(或者说 go 程)中对同一个值进行操作是否是安全的?

具体就是map类型的值是并发安全的吗?如果不是,那么在我们只在map上添加或者删除键—元素对的情况下,依然不安全吗?

答:非原子操作需要加锁, map并发读写需要加锁,map操作不是并发安全的,判断一个操作是否是原子的可以使用 go run race 命令做数据的竞争检测