完美的函数哈希函数生成器

Question

我有一套C++函数.我想在哈希表中映射这些函数,例如:unordered_map<function<ReturnType (Args...)> , SomethingElse>,SomethingElse这与这个问题无关.

这组功能以前是已知的,小的(比方说小于50)和静态(不会改变).

由于查找性能至关重要(应该执行O(1)),我想定义一个完美的散列函数.

这个场景有一个完美的哈希函数生成器吗？

我知道存在完美的散列函数生成器(如GPERF或CMPH),但由于我从未使用它们,我不知道它们是否适合我的情况.

原因:

我正在尝试设计一个框架,在给定用C++编写的程序的情况下,用户可以选择F该程序中定义的函数的子集.

对于每个f属于F,框架实现了一个memoization策略:当我们f使用输入调用时i,我们存储(i,o)在一些数据结构中.所以,如果我们要再次拨打f同i,我们将返回o,而无需再次进行(时间成本)计算.

"已计算出的结果",将不同的用户(可能在云)之间共享,因此,如果用户u1已经计算o,用户u2将节省呼叫计算时间f与i(使用前的相同注释).

显然,我们需要存储一对对(f,inputs_sets)(inputs_sets我之前谈过的已计算结果集),这是最初的问题:我该怎么做？

因此,使用此方案中的意见提出了"枚举猫腻"可能是一个解决方案,假设所有用户都使用完全相同的枚举,这可能是一个问题:假设我们的方案有f1,f2,f3如果有什么u1想memoize的只f1和f2(所以F={f1,f2}),虽然u2只想记忆f3(所以F={f3})？一个过度的解决方案可能是枚举程序中定义的所有函数,但这可能会产生巨大的内存浪费.

Answer 1

好吧,也许不是你想听的但是考虑一下:既然你谈到了一些小于50的函数,那么哈希查找应该可以忽略不计,即使是碰撞也是如此.您是否真的进行过分析并发现查找至关重要？

所以我的建议是将精力集中在其他方面,很可能一个完美的哈希函数不会在你的情况下带来任何改进的性能.

我将更进一步说,我认为对于少于50个元素的平面地图(好的ol' vector)将具有相似的性能(或者由于缓存局部性可能甚至更好).但同样需要进行测量.