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

[XiiLii]

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

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

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

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

>>> hash(id('a')) - hash(id('b')) == hash(id('a')) - hash(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')) == hash(id('a')) - hash(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 值之间的几点事实：

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

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

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

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

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

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

4. 具有不同 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 值，但这只是散列函数中的其中一个过程或步骤。

阅读更多

• 存储 dict 的元素前是计算 key 的 hash 值？
• 手动汉化 PyCharm 的过程
• 模拟登陆 Github
• 字符图像识别——数字字母混合

上面的 hash(id('a')) - hash(id('b')) == hash(id('a')) - hash(id('b')) 改为 hash(id('a')) - hash(id('b')) == id('a') - id('b')

[simonliu2018]

一个有趣的现象：

In [149]: c = 'abc'

In [150]: d = 'abc'

In [151]: id(c)
Out[151]: 4401737656

In [152]: id(d)
Out[152]: 4401737656

[vipppppp]

=.= 看了一下 差点还以为我一直认识的 hash 是错的
不过何必又发一个文章，直接在之前的下午勘误就好了啦，不然只看到之前的文章的人不一样会被误导。。。

不明白的是 lz 为什么一直在写这个等式 hash(id('a')) - hash(id('b')) == hash(id('a')) - hash(id('b'))。。。
是我老眼昏花了吗

[XiiLii]

@simonliu2018 我之前就是被这个误导了，这是缓存被复用了

[oott123]

python 的字符串是不可变的。同一个 python 同一台机器，你怎么算 hash('a') 都是一样的，正着算反着算存 dict 不存 dict 重启 python 算它都是那个数，不会变的……所以你把它和 dict 联系起来就莫名其妙了。

[XiiLii]

@vipppppp 因为那篇文章底部有帮指出错误了，这里再总结下

不好意思，是我眼花了，应该是 `hash(id('a')) - hash(id('b')) == id('a') - id('b')`

[bwangel]

已加特别关注 。嗯，楼主值得关注

[XiiLii]

@oott123 我是拿其中的一个可哈希对象来作例子，纠正我之前说的错误推论

[XiiLii]

@bwangel 谢谢哈

[FiveDDD]

@simonliu2018 #1
@XiiLii #3

我记得之前在哪看到过，好像是 shell 执行类似的语句，会出现缓存复用。

[zhengxiaowai]

还有个问，怕是你没弄明白：

[ChristopherWu]

我以前学 C 语言也像你这样子，从现象去反推东西。
但是现在我觉得这是不太对的做法：

你要看，直接去看 python 的 dict 怎么做哈希的不是更直接了事吗？

比如 Elixir 的 map 为何前 32 个 key 是有序的，看现象就很让人迷惑了。

https://stackoverflow.com/questions/40392012/is-ordering-of-keys-and-values-preserved-in-elixir-when-you-operate-on-a-map/49313535#49313535

[zhengxiaowai]

1. 存在一个叫符号表的东西，这个东西在 Python 解释器启动时候就初始化完成了，里面存储一些简单的东西，比如 字符 'a'、'b' 这样的简单字符串，所以他们的内存地址在 Python 解释器启动时候就是确定的

2. 关于散列表，hash 计算是 散列表必须的过程，所你说 key 必须要 hash 是正确的。散列输入也就是这个 key，不同的 key 是有几率散列到同一个地址，这个有个专有名字，哈希冲突。解决这个冲突有两种方式，一种是链式 hash，还有一种是开地址 hash，这两种形式几乎完全不一样。

[XiiLii]

@zhengxiaowai 是的，你说的第 2 点我有了解过，这里没讲这么详细是因为我这篇文章主要是纠正我之前的错误认识，hash 是对 key，不是对 key 内存地址，关于你说的第 1 点我没了解过，感谢分享哈

[jmc891205]

不如直接把 cpython 里相关的 code 拉出来

[XiiLii]

@ChristopherWu 是的，我也觉得直接看源码会好很多，这样理解会更深

[thechosenone]

一直对字典的排序有一点疑惑，比如 A0 = dict(zip(('a','b','c','d','e'),(1,2,3,4,5)))输出一定是{'a': 1, 'c': 3, 'b': 2, 'e': 5, 'd': 4},先留下名，看看楼主的文有没有解释

[XiiLii]

@thechosenone

字典本身是属于“无序序列”，这里的无序不是说每次的排列顺序都是随机排列，不是说这次输出 c, a, b，下次可能输出 b, c, a，不是这个意思

首先需要知道 dict 是基于哈希表的数据结构，哈希表是一块连续的内存空间（数组），这个数组里的元素叫做表元，表无存储的是 key-value 对，而 key-value 对具体是在这个数组里的那个位置（索引），需要使用散列函数对 key 进行 hash 值等一系列的计算才知道（这些是 Python 解释器自动完成，不需要我们主动去做）。

打个比方：key 就像一个班级里的学生，他们排在一起看起来有高有矮看起来很乱，普通人眼中的有序就是他们应该按照从高到矮或从矮到高这样的顺序排列，但是他们实质上是按照身份证号码的大小来排的，相对身份证号来说它是有序的，只是相对身高来说他们是无序的。

字典的无序也是类似的道理（不考虑散列冲突等情况），

[wizardforcel]

没那个 id 就对了啊

肯定要计算 key 的 hash，你可以传进去一个不能散列的对象，肯定崩

[wizardforcel]

@XiiLii 同一个散列，用相同的算法遍历，顺序总是相同。但是随着你添加元素，里面的散列会 rehash 的。

[xuanbg]

如果说 dict 是一个方阵，那么哈希值就是第几排第几列这种编号。方阵的每一个位置都有这个编号，通过哈希算法，可以按人的名字计算出这个编号，所以你要找某个人，只要根据名字(key)计算一下编号(哈希值)，就可以直接找到这个人(value)而无需一个个去寻找。

[momocraft]

学习中重要的一课是区分哪些是实然 哪些是应然 哪些是巧合

[neoblackcap]

hash 表的实现各大算法书都有写，就算没写，也有 CPython 的源代码。
这个完全不需要讨论吧

[PythonAnswer]

看源码，不用猜。

不如研究现在字典是怎么变成有序的

[lance6716]

@XiiLii Python 并不是裸存 kv 对的，最新的字典也不是无序的…你还是看看源码别瞎猜了，cpython 的源码很易读