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

前几天发了一篇名为存储 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 值之间的几点事实：

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

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

等式成立的原因

推论错误的原因

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

阅读更多