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

dkzwm 发布于2019-07-30 17:49 / 1561人阅读

摘要：大多数情况下，相比计算这些不同对象类型的值，直接计算对象所在内存地址整数的值性能更高，这也就是为什么不是计算的值，而是计算所在内存地址的值阅读更多手动汉化的过程模拟登陆字符图像识别数字字母混合爬取猫眼实时票房数据

dict 的高性能与其存储方式是分不开的，我们知道 dict 的存储是基于哈希表（又称散列表），需要计算 hash 值，那么是计算谁的 hash 值呢？是像别人说的：存储 dict 元素前计算 key 的 hash 值？

验证

这里先创建个字典

>>> my_dict = {"a": "apple", "b": "banana"}

由于哈希表是一块连续的内存空间（数组），在不考虑 hash 值冲突的情况下，如果计算的是 key 的 hash 值，那么："a" 的 hash 值与 "b" 的 hash 值之间的差值与 "a" 的内存地址与 "b" 的内存地址之间的差值（可理解为内存地址里的距离）相等才对，也就是说以下的等式成立才对

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

但事实上面等式返回的是 False

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

先看看其中各项的具体值是多少

>>> hash("a")
-7336862871683211644
>>> hash("b")
3607308758832868774
>>> id("a")
1290454097736
>>> id("b")
1290454096056

>>> id("a") - id("b")
1680
>>> hash("a") - hash("b")
-10944171630516080418

可以很明显得看到差距还是挺大的
这说明计算的不是 key 的 hash 值（这种说法不够严谨），那计算的是什么呢？

计算的是 key 所在内存地址的 hash 值

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

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

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

下面再多验证几个

>>> my_dict["c"] = "cherry"
>>> hash(id("b")) - hash(id("c")) == id("b") - id("c")
True
>>> id("b") - id("c")
791760
>>> hash(id("b")) - hash(id("c"))
791760

>>> a["d"] = "date"
>>> hash(id("d")) - hash(id("c")) == id("d") - id("c")
True
>>> id("d") - id("c")
1400
>>> hash(id("d")) - hash(id("c"))
1400

到这里就可以证明上面的结论

为何计算的是 key 所在的内存地址的 hash 值？

比如上面的"a"（1 个字符）明显比其所在的内存地址 1290454097736（13 个字符）要短。短的计算不是更快吗？
记住一句话：Python 中一切皆对象，"a"是个 str 对象，1290454097736 是个 int 对象

>>> type("a")

>>> type(id("a"))

一个对象里不是仅仅存储对应值，它还有很多属性（含方法），来看看谁的属性多

>>> len(dir("a"))
77
>>> len(dir(id("a")))
70

str 对象比 int 对象多 7 个属性

它们都有个叫 __sizeof__() 的魔法方法，用于获取当前对象所占用的内存空间大小（字节）

>>> id("a").__sizeof__()
32
>>> "a".__sizeof__()
50

从上面可以发现：虽然 "a" 看起来只有 1 个字符，但其占用的内存空间要大于其内存地址 id("a") 所占用的空间

当然这不是主要原因，Python 解释器会将其转换为适当的数据类型再进行 hash 计算

不过，dict 的 key 不仅仅可以是 str 对象，也可以是 int、bytes、fromzenset 等这些可哈希(hashable)对象，可哈希对象都是不可变(immutable)对象（注意：反之不一定成立，如 tuple），不可变对象内存地址不变。大多数情况下，相比计算这些不同对象类型的 hash 值，直接计算对象所在内存地址（整数）的 hash 值性能更高，这也就是为什么不是计算 key 的 hash 值，而是计算 key 所在内存地址的 hash 值

阅读更多

手动汉化 PyCharm 的过程

模拟登陆Github

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

爬取猫眼实时票房数据

专线服务混合云获取字符串hash值最快的hash表算法 python的key linux的key

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

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

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

摘要：前几天发了一篇名为存储的元素前是计算的值的文章，因缺乏相关的背景知识，导致得出了不正确的推论。反正存储的元素前还是计算的值，但这只是散列函数中的其中一个过程或步骤。前几天发了一篇名为存储 dict 的元素前是计算 key 的 hash 值？的文章，因缺乏相关的背景知识，导致得出了不正确的推论。那篇文章的推论是在不考虑 hash 冲突的情况下， a 所在内存地址的 hash 值与...

luqiuwen 2019-07-30 17:52 评论0 收藏0
Python中的字典和集合

摘要：若对于关键字集合中的任一个关键字，经散列函数映象到地址集合中任何一个地址的概率是相等的，则称此类散列函数为均匀散列函数，这就是使关键字经过散列函数得到一个随机的地址，从而减少冲突。导语：本文章记录了本人在学习Python基础之数据结构篇的重点知识及个人心得，打算入门Python的朋友们可以来一起学习并交流。本文重点： 1、掌握常见的字典创建，查询，判别方法；2、了解字典中的defa...

hqman 2019-07-30 16:05 评论0 收藏0
五个步骤教你理清Redis与Memcached的区别

摘要：它们都使用来做事件循环，不过是单线程的服务器也是多线程的，只不过除了主线程以外，其他线程没有，只是会进行一些后台存储工作，而是多线程的。支持设置过期时间，即，但是内部并不定期检查数据是否过期，而是客户进程使用该数据的时候，会欢迎大家前往腾讯云+社区，获取更多腾讯海量技术实践干货哦~ 本文由Super发表于云+社区专栏 memcached和redis，作为近些年最常用的缓存服务器，相...

waterc 2019-08-06 13:36 评论0 收藏0
手动汉化 PyCharm 的过程

摘要：默认是英文界面，如果想汉化它，网上有很多相关的汉化丁可以下载。 showImg(https://segmentfault.com/img/remote/1460000016400154); PyCharm 默认是英文界面，如果想汉化它，网上有很多相关的汉化䃼丁可以下载。我的 Pycharm 版本是 pycharm-professional-2018.2.2，这里仅简单展示手动汉化的原...

RayKr 2019-07-30 17:51 评论0 收藏0