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

[XiiLii]

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')) == hash(id('a')) - hash(id('b'))

>>> 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

下面再多验证几个

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

>>> a['d'] = 'date'
>>> hash(id('d')) - hash(id('c')) == hash(id('d')) - hash(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')
<class 'str'>
>>> type(id('a'))
<class 'int'>

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

>>> 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
• 字符图像识别——数字字母混合

[frostming]

hash 的根本作用是一个映射算法，把任意两个不同的对象映射到不同的值，这个数据结构里都有讲到的
hash(id('b')) - hash(id('c')) == id('b') - id('c') 这里你写错了

这个等式成立的原因是这个 hash 算法作用在一个 int 上是返回期本身的。而对于字符串则不是这样，所以 hash('a') - hash('b') == id('a') - id('b')这个验证思想就是错的，hash 只保证映射到的值不同，并不是线性（所谓线性，就是 hash(x) = ax+b 这种映射，而若要此等式成立，还必须 a = 1 才行，这显然不可能）

而字典的 key 是依赖其 hash 值来判断两个 key 是否相同，所以此 key 必须是可哈希的

[XiiLii]

@frostming 发了好几个地方，就你有能力指出的我的错误，非常感谢