内容简介:当在哈希表中查找某个与键值对应的元素值时,我们需要先把键值作为参数传给这个哈希表。哈希表会先用哈希值通常是一个无符号的整数。一个哈希表会持有一定数量的因此,哈希表会先用这个键的哈希值的低几位去定位到一个哈希桶,然后再去这个哈希桶中,查找这个键。由于键-元素对总是被捆绑在一起存储的,所以一旦找到了键,就一定能找到对应的元素。
当在哈希表中查找某个与键值对应的元素值时,我们需要先把键值作为参数传给这个哈希表。哈希表会先用 哈希函数(hash function) 把键值转换为哈希值。
哈希值通常是一个无符号的整数。一个哈希表会持有一定数量的 桶(bucket) ,也可称之为 哈希桶 ,这些 哈希桶 会均匀地储存其所属哈希表收纳的那些键-元素对。
因此,哈希表会先用这个键的哈希值的低几位去定位到一个哈希桶,然后再去这个哈希桶中,查找这个键。由于键-元素对总是被捆绑在一起存储的,所以一旦找到了键,就一定能找到对应的元素。
随后,哈希表就会把对应的元素值作为结果返回。只要这个键-元素对存在于哈希表中就一定会被查找到,因为哈希表增、改、删键-元素对时候的映射过程,跟上面描述的一样。
也就是说, 字典map不会独立存储任何键的值,但会独立存储它们的哈希值。键值跟元素是捆绑一起存储的。
问题:字典的键类型不能是哪些类型?
回答:Go语言字典的键类型不可以是函数类型、字典类型和切片类型。
原因:Go语言规范规定,在键类型的值之间必须施加操作符==和!=。换句话说,键类型的值必须要支持判等操作。由于函数类型、字典类型和切片类型的值并不支持判等操作,所以字典的键类型不能是这些类型。
另外,如果键的类型是接口类型,那么键值的实际类型也不能是上述三种类型,否则在程序运行过程中会引发 panic(运行时恐慌)
demo:
var badMap2 = map[interface{}]int{ "1": 1, []int{2}: 2, //这里会引起panic 3:3 }
这里的变量bandMap2的类型是键类型为interface{}的字典类型。这样声明不会引起 Go 语言编译器的检查报错,但在运行时(runtime)系统就会发现这里的问题,抛出一个panic。
还要注意,如果键类型是数组类型,也要确保数组的元素类型不是函数类型、字典类型或切片类型。
为什么键类型的值要支持判等操作?
之前说过,Go语言一旦定位到了某一个哈希桶,那么就会试图在这个桶中查找键值。
首先,每个哈希桶都会把自己包含的所有键的哈希值存起来。Go语言会用被查找的键的哈希值与这些哈希值逐个对比,看看是否有相等的。如果没有,则直接返回结果。
如果有相等的,那么再用键值本身去对比一次。因为不同键值的哈希值可能相同。这个叫 哈希碰撞
只有当键的哈希值跟键值都相等时,才说明查找成功。
问题:应该优先考虑哪些类型作为字典的键类型?
回答:快速查找的键。(优先选用数值类型和指针类型。如果非要选择字符串的话,最好对键值的长度进行额外的约束)
分析:****“把键值转换为哈希值”以及 “把查找的键值与哈希桶中的键值对比” 这两个操作比较耗时。
也就是说:求哈希和判等操作的速度越快,对应的类型就越适合作为键类型。
对于所有的基本类型、指针类型,以及数组类型、结构体类型和接口类型。以哈希的操作来说,宽度越小的类型速度通常更快。对于布尔类型、整数类型、浮点类型、复数类型、和指针类型来说都是如此。对于字符串类型,看值具体长度,长度越短哈希越快。
对结构体类型的值求哈希实际上就是对它的所有字段值求哈希并进行合并,所以关键在于各个字段的类型以及字段的数量。而对于接口类型,具体的哈希算法,则有值的实际类型决定。
不建议用结构体、接口、数组等高级类型作为字典的键类型,不仅仅是因为对它们的值求哈希,以及判等的速度较慢,更因为它们的值存在变数。对一个数组来说,我可以任意改变其中的元素值,但在变化前后,它代表了两个不同的键值。
问题:在值为nil的字典上执行读操作会成功么,写操作呢?
当我们仅声明而并不是初始化一个字典类型的变量时,它的值会是nil。
回答:除了添加键值对,其他操作都不会引起错误。当我们试图在一个值为nil的字典添加键-元素对时,Go语言在运行时会立即抛出一个panic。
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。