给定整数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*N(空间，所以它不足以满足我的需要。
让我详细说明我的用例，我想要元组(a,b,c)作为哈希映射的键。基本上，a，b，c是函数的自变量，我想记住。在python中，@lru_cache完美地做到了这一点，对于N=1e6没有任何问题，但当我尝试自己编写哈希函数时，我会出现内存溢出。那么python是怎么做到的呢？
我正在处理10^6 的订单
此代码工作
@lru_cache(maxsize=None)
def myfn(a,b,c):
//some logic
return 100
但如果我自己这样写散列函数，它就不会了。那么python是如何做到的。
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)]
要直接回答是否有可能找到从大小为Θ(N^2)的集合到大小为O(N)的集合的内射哈希函数的问题：没有。从有限集合a到集合B的内射函数的存在本身就意味着CCD_。这类似于试图将{1, 2, 3}中的一个唯一数字赋予20人小组中的每个成员。
但是，请注意，散列函数do经常会发生冲突；使用它们的哈希表只是有一种解决这些冲突的方法。作为一个简单的说明示例，例如，您可以持有一个数组，以便哈希函数的每个可能输出都映射到此数组的索引，并且在每个索引处都有一个元素列表(因此，数组大小为O(N)的列表数组(，然后在发生冲突的情况下，只需检查匹配列表中的所有元素，并对它们进行比较(而不是它们的哈希值(，直到找到您想要的内容。这被称为链哈希或链接。基于哈希表的填充方式(通过其负载因子测量(，对哈希表进行一些罕见的操作(重新哈希(可以确保元素访问的O(1)的摊销时间复杂性，但如果您真的试图保持ω(N)值，这可能会随着时间的推移而增加空间复杂性，不过请注意，这是不可避免的：在没有任何额外信息的情况下，您不能使用比Θ(X)更少的空间来保存Θ(X)值(例如：如果您保存1000000个无序元素，其中每个元素都是介于1和10之间的自然数，那么您可以只保存十个计数器；但在您的案例中，您描述了一整套可能的11*(N+1)*(2N+1)大小的元素，因此为Θ(N^2)(。
然而，这种方法将确保O(N+K)(相当于O(max{N,K})(的空间复杂性，其中K是您持有的元素数量；只要你不想同时持有Θ(N^2)(或者你认为数量太多(元素，它可能就足以满足你的需求。