c++ - 函数的完美哈希函数生成器

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怎么办只想内存f1和 f2 (所以 F={f1,f2} )，而 u2只想内存f3 (所以F={f3})？一个矫枉过正的解决方案可能是枚举程序中定义的所有函数，但这会产生巨大的内存浪费。

Answer 1

好吧，也许这不是您想听到的，但考虑一下:既然您谈论的函数很少，少于 50 个，那么哈希查找应该可以忽略不计，即使存在冲突。您是否实际分析过并发现查找很关键？

所以我的建议是将精力集中在其他事情上，完美的哈希函数很可能不会为您的情况带来任何改进的性能。

我要更进一步说，我认为对于少于 50 个元素的平面 map (好的 ol'vector)会有类似的性能(或者由于缓存可能更好)地区)。但同样，需要进行测量。