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

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