纠正<存储 dict 的元素前是计算 key 的 hash 值？>

luqiuwen 发布于2019-07-30 17:52 / 2616人阅读

摘要：前几天发了一篇名为存储的元素前是计算的值的文章，因缺乏相关的背景知识，导致得出了不正确的推论。反正存储的元素前还是计算的值，但这只是散列函数中的其中一个过程或步骤。

前几天发了一篇名为存储 dict 的元素前是计算 key 的 hash 值？的文章，因缺乏相关的背景知识，导致得出了不正确的推论。
那篇文章的推论是

在不考虑 hash 冲突的情况下， "a" 所在内存地址的 hash 值与 "b" 所在内存地址的 hash 值之间的差值 和 "a" 的内存地址与 "b" 的内存地址之间的差值 相等，也就是说以下的等式成立才对

hash(id("a")) - hash(id("b")) == id("a") - id("b")

简单说是：存储 dict 的元素前计算的是 key 所在内存地址的 hash 值
上面的等式是成立的

>>> hash(id("a")) - hash(id("b")) == id("a") - id("b")
True
>>> id("a") - id("b")
1680
>>> hash(id("a")) - hash(id("b"))
1680

但是需要纠正说明的是，我上面的那个推论是错的！

等式成立的原因

这里先说上面的等式为什么成立，因为整数的 hash 值是其本身

>>> a
1234567
>>> hash(a)
1234567

又因为内存地址是个整数，所以内存地址的 hash 值也是其本身，即和内存地址一样的值

>>> my_dict = {"a": "apple", "b": "banana"}
>>> hash(id("a")) == id("a")
True
>>> id("a")
2673717403464
>>> hash(id("a"))
2673717403464

这就是为什么这个等式成立

hash(id("a")) - hash(id("b")) == id("a") - id("b")

推论错误的原因

如果两个值不同，那么它们的内存地址也不同，这是正确的，但我错误的认为如果值相同，那么内存地址也相同。下面是一个具有相同值不同内存地址的例子

>>> c = "a-c"
>>> d = "a-c"
>>> id(c) == id(d)
False
>>> id(c)
2673720167592
>>> id(d)
2673720167704

注：上面的 c 和 d 虽然值是相同的，但它们不是同一个对象，所以内存地址不一样

回到那个错误的推论：

存储 dict 的元素前计算的是 key 所在内存地址的 hash 值

该推论成立的前提之一是：相同的 key 值的内存地址必须相同，但事实是像上面的例子一样，相同的 key 值可以拥有不同的内存地址

假设该推论成立的话，就会导致 dict 中出现两个相同的 key 值，但事实不是这样的，即便内存地址不同，只要值相同就不可以同时作为 dict 的 key，后者会覆盖前者。

>>> c
"a-c"
>>> d
"a-c"
>>> {c: 0, d: 1}
{"a-c": 1}

因为相同的 key 具有相同的 hash 值

>>> hash(c) == hash(d)
True
>>> hash(c)
-8124728931706162487
>>> hash(d)
-8124728931706162487

存储 dict 的元素前是计算 key 的 hash 值

首先了解下关于 key 与其 hash 值之间的几点事实：

相同的 key 肯定具有相同的 hash 值；

应该不用解释，这是 hash 算法决定的；

不同的 key 也可能具有相同的 hash 值；

因为 hash 算法会将任何长度的数据转换成一个固定长度的字符串（int 对象除外），所以可能生成的 hash 值的数量是有限的，而可用来计算 hash 值的数据量理论上是无穷的，这就造成两个数据的 hash 值可能相同

具有相同 hash 值的 key 不一定相同；

原因正是因为不同的 key 可以具有相同的 hash 值

具有不同 hash 值的 key 肯定不同

原因正是因为相同的 key 具有相同的 hash 值；

dict 是基于哈希表的数据结构，哈希表是一块连续的内存空间（数组），因为所存储的 key-value 散落在不同的位置上，key-value 之间存在大量的空白空间是很常见的，所以哈希表又称散列表。
dict 本质就是一个能利用散列函数将 key 转化为索引的数组（散列函数+数组），散列函数的功能之一是将 key 值转换为数组索引（dict 的 key 具有唯一性的本质是数组索引的唯一性）。在转换的过程中，需要对 key 进行 hash 值计算，计算 hash 值的目的是为了确定 key 应该存储在数组中的哪个位置（索引），即定位，而不是判断两个 key 是否相同。因为通过比较 hash 值是无法判断两个 key 是否相同的（参考前面的第 3 点事实），所以当 hash 值相同时，会定位到相同的表元（索引对应的元素），该表元里的 key 是否与计算的 key 相等还需要进一步判断。

反正存储 dict 的元素前还是计算 key 的 hash 值，但这只是散列函数中的其中一个过程或步骤。

阅读更多

手动汉化 PyCharm 的过程

模拟登陆Github

字符图像识别——数字字母混合

爬取猫眼实时票房数据

GPU云服务器云服务器 asp中&lt&gt的意思 python &lt&gt java &lt=&gt java&lt &gt

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/42473.html

存储 dict 的元素前是计算 key 的 hash 值？

摘要：大多数情况下，相比计算这些不同对象类型的值，直接计算对象所在内存地址整数的值性能更高，这也就是为什么不是计算的值，而是计算所在内存地址的值阅读更多手动汉化的过程模拟登陆字符图像识别数字字母混合爬取猫眼实时票房数据 dict 的高性能与其存储方式是分不开的，我们知道 dict 的存储是基于哈希表（又称散列表），需要计算 hash 值，那么是计算谁的 hash 值呢？是像别人说的：存储 d...

dkzwm 2019-07-30 17:49 评论0 收藏0
Python基础知识解答：字典详细使用教程

　　字典作为python中一个内置的数据机构，它其实和列表是一样的，但是它又是没有顺序的，以键值的方式，用来存储数据，那么，它的使用教程是什么呢？下文给大家做个解答。　　一.什么是字典　　字典作为Python的一个内置数据结构，和列表一样都是可变序列的，但是它是无序的，以键值对的方式存储数据。　　二.创建字典　　创建字典的两种方式，一种使用{}另一种使用内置函数dict()　#author:爪哇斗...

89542767 2022-09-16 17:01 评论0 收藏0
[零基础学Python]字典，你还记得吗？

摘要：字典，这个东西你现在还用吗随着网络的发展，用的人越来越少了。最早的名字叫伍记小字典，但未能编纂完成。新华字典由商务印书馆出版。成为迄今为止世界出版史上最高发行量的字典。也被称为关联数组或哈希表。字典，这个东西你现在还用吗？随着网络的发展，用的人越来越少了。不少人习惯于在网上搜索，不仅有web版，乃至于已经有手机版的各种字典了。我曾经用过一本小小的《新华字典》。《新华字典》是...

galaxy_robot 2019-07-31 11:32 评论0 收藏0
共享13个非常有利的Python代码片段

　　小伙伴们好，此篇文章主要是跟大家分享13个Python中非常有利的代码片段，有兴趣的同学们赶紧来看一下吧，对大家有所帮助得话不要忘记保存以下　　ListsSnippets　　大家从最常见的算法设计目录刚开始　　1.把两个目录合拼成词典　　假定大家在Python中有两种目录，我希望把它们合并为词典方式，其中的一个目录的项做为词典的键，另外做为值。这就是在用Python编写代码时经常碰到的一个很常...

89542767 2022-12-29 11:15 评论0 收藏0