能否实现O(N)空间的hashit(a,b,c)哈希函数？Python缓存为何可行？

给定整数a、b、c满足：

• -N ≤ a ≤ N
• 0 ≤ b ≤ N
• 0 ≤ c ≤ 10

请问能否编写哈希函数hashit(a, b, c)，使其地址空间不超过O(N)？

我最初的思路是写成a + 2N*b + 10*2N*N*c，但这需要O(20N²)空间，无法满足需求。

我的场景是将元组(a,b,c)作为哈希表的键，用于函数参数记忆化。当N为1e6时，Python的@lru_cache可正常工作，但自行编写哈希函数时出现内存溢出，请问Python是如何实现的？

可正常运行的代码 #

from functools import lru_cache

@lru_cache(maxsize=None)
def myfn(a,b,c):
    # some logic
    return 100

无法正常运行的自定义哈希函数代码 #

def hashit(a,b,c):
    return a + 2*N*b + 2*N*N*c

def myfn(a,b,c):
    if hashit(a,b,c) in myhashtable:
        return myhashtable[hashit(a,b,c)]
    # some logic
    myhashtable[hashit(a,b,c)] = 100
    return myhashtable[hashit(a,b,c)]

1. 能不能构造出O(N)空间的哈希函数？ #

不行。先算一下(a,b,c)的总可能组合数：

• a有2N+1种取值（从-N到N）
• b有N+1种取值
• c有11种取值
  总组合数是(2N+1)*(N+1)*11，量级为O(N²)。要让哈希函数能区分所有不同的键，要么做完美哈希（每个键对应唯一哈希值），要么允许冲突，但不管哪种方式，能容纳所有可能键的地址空间至少要和总组合数同量级，也就是O(N²)。除非你实际不会用到所有合法输入，但如果要覆盖所有情况，不可能把地址空间压缩到O(N)。

2. 为什么@lru_cache能正常工作？ #

你的自定义代码内存溢出的核心问题在于：
你用的是完美哈希，把每个键映射成一个超大整数——当N=1e6时，这个哈希值能达到2*(1e6)^2*10 = 2e13。如果你的myhashtable是数组，要分配能容纳这个最大值的数组完全不现实，直接内存爆炸；就算用字典，若误解哈希表逻辑也可能做了不必要的操作。

而lru_cache的实现逻辑和你完全不同：

• 它内部用Python字典存储缓存，直接把参数元组(a,b,c)作为键，而非你生成的超大整数。Python字典会对元组计算哈希值，但这个哈希值只是用来快速定位桶的位置，字典不会为哈希值的范围预先分配连续空间——它用链式地址法处理冲突，内存占用只和实际缓存的键值对数量成正比，和理论上的最大哈希值无关。
• Python对元组的哈希计算高效，会结合每个元素的哈希值生成一个整数，但这个整数的大小不影响内存，因为字典的桶数量是动态调整的，只会根据实际存储的元素数量扩容，不会预先申请巨大空间。

简单说，你自己的代码如果用数组当哈希表，必然因需要超大空间溢出；如果用字典还溢出，可能是缓存了太多不必要的条目，但lru_cache只存实际用到的键，所以能正常运行。

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