我有一组C++函数。我想在哈希表中映射这个函数,例如:unordered_map<function<ReturnType (Args...)> , SomethingElse>
,其中SomethingElse
与此问题无关。
这组函数以前是已知的,小(比如说小于 50(和静态(不会改变(。
由于查找性能至关重要(应该在O(1)
中执行(,我想定义一个完美的哈希函数。
对于这种情况,是否存在完美的哈希函数生成器?
我知道存在完美的哈希函数生成器(如 GPERF 或 CMPH(,但由于我从未使用过它们,我不知道它们是否适合我的情况。
原因:
我正在尝试设计一个框架,给定一个用C++编写的程序,用户可以选择该程序中定义的函数的子集F
。
对于属于F
的每个f
,框架实现了一个记忆策略:当我们用输入i
调用f
时,我们将(i,o)
存储在某个数据结构中。因此,如果我们要使用 i
再次调用 AGAIN f
,我们将返回o
而不再次执行(时间昂贵(计算。
"已经计算的结果"将在不同的用户之间共享(可能在云上(,因此如果用户u1
已经计算了o
,则用户u2
将节省使用i
调用f
的计算时间(使用与之前相同的注释(。
显然,我们需要将对集存储在(f,inputs_sets)
(其中inputs_sets
是我之前讨论的已经计算的结果集(,这是最初的问题:我该怎么做?
注释中提出的"枚举技巧"可能是一种解决方案,假设所有用户都使用完全相同的枚举,这可能是一个问题:假设我们的程序具有f1
,f2
,f3
如果u1
只想记住f1
和f2
(所以F={f1,f2}
(, 而u2
只想记住f3
(所以F={f3}
(?一个矫枉过正的解决方案可能是枚举程序中定义的所有函数,但这可能会导致巨大的内存浪费。
好吧,也许不是你想听到的,但请考虑一下:由于您谈论的函数少于 50,因此哈希查找应该可以忽略不计,即使发生冲突也是如此。您是否实际分析并看到查找至关重要?
所以我的建议是把你的精力集中在其他事情上,很可能一个完美的哈希函数不会在你的情况下带来任何改进的性能。
我将更进一步,说我认为对于少于 50 个元素的平面映射(良好的 ol' vector
(将具有类似的性能(或者由于缓存局部性甚至可能更好(。但同样,需要测量。