Python是否会缓存原生不可变对象的哈希键？

问题描述 #

问题1 #

计算任意不可变对象（例如由整数和字符串元素组成的元组）的哈希键后，Python解释器会将该值保留在内存中，还是每次都重新计算？如果代码需要反复检查对象是否属于某个集合（如set），是否需要自行缓存这些哈希键，还是解释器会自动处理？

示例代码：

x = ("a", 1)
assert x in {("a", 1), ("b", 2)} # 首次计算hash(x)
assert x in {("c", 3), ("d", 4)} # Python解释器会再次计算hash(x)吗？

问题2 #

Python原生元组类型的hash方法时间复杂度为O(n)（n为元组元素数量）。若代码调用该方法m次，理论时间复杂度为O(n*m)，请问Python是否会通过内部缓存哈希值进行优化，将实际时间复杂度降至O(n)？

示例代码：

n = 999_999_999 # 大数
x = tuple(i for i in range(n)) # 超大元组，计算哈希耗时久
m = 999_999_999 # 另一个大数
for _ in range(m): # 大量迭代
    hash(x)

解答 #

• Python的**不可变对象（如元组、字符串、整数等）**会在首次计算哈希值后，将结果缓存到对象内部的隐藏属性中。后续调用hash()方法，或是像检查对象 in 集合这类需要用到哈希值的场景，都会直接复用缓存的结果，不会重新计算。
• 针对第一个示例：第二次执行assert x in {("c", 3), ("d", 4)}时，Python不会再次计算hash(x)，直接使用第一次缓存好的哈希值。
• 针对第二个示例：虽然理论上m次调用hash(x)的时间复杂度是O(n*m)，但由于Python内部缓存了元组的哈希值，实际只会在第一次调用时花费O(n)时间计算，剩下的m-1次调用都是直接返回缓存值，实际时间复杂度降至O(n)。
• 完全不需要自行缓存哈希键，Python解释器会自动处理不可变对象的哈希值缓存。而且因为不可变对象的状态无法修改，缓存的哈希值始终有效，不会出现过期问题。

内容的提问来源于stack exchange，提问作者Kasia