函数的完美哈希函数生成器
Perfect hash function generator for functions
我有一组 C++ 函数。我想将此函数映射到散列 table 中，例如：unordered_map<function<ReturnType (Args...)> , SomethingElse>，其中 SomethingElse 与此问题无关。
这组函数是以前已知的，小的（比方说少于 50）和静态的（不会改变）。
由于查找性能至关重要（应该在O(1)中执行），我想定义一个完美的哈希函数。
是否存在适合这种情况的完美哈希函数生成器？
我知道存在完美的散列函数生成器（如 GPERF or CMPH），但由于我从未使用过它们，所以我不知道它们是否适合我的情况table。
原因：
我正在尝试设计一个框架，给定一个用 C++ 编写的程序，用户可以 select 该程序中定义的函数的一个子集 F。
对于属于 F 的每个 f，框架实施了一个 memoization 策略：当我们使用输入 i 调用 f 时，我们存储 (i,o) 在一些数据结构中。因此，如果我们要用 i 调用 AGAIN f，我们将 return o 而无需再次执行（耗时的）计算。
"already computed results"将在不同用户之间共享（可能在云端），因此如果用户u1已经计算了o，用户u2将节省计算用 i 调用 f 的时间（使用与之前相同的注释）。
显然，我们需要存储对的集合(f,inputs_sets)（其中inputs_sets是我之前讲过的已经计算出的结果集），这是原题：我该怎么做？
因此，在这种情况下使用评论中提出的 "enumeration trick" 可能是一种解决方案，假设所有用户都使用 完全相同的 枚举，这可能成为一个问题：假设我们的程序有 f1、f2、f3 如果 u1 只想记忆 f1 和 f2 怎么办（所以F={f1,f2})，而 u2 只想记忆 f3（所以 F={f3}）？一个矫枉过正的解决方案可能是枚举程序中定义的所有函数，但这会产生巨大的内存浪费。
好吧，也许这不是您想听到的，但考虑一下：既然您谈论的函数很少，少于 50 个，那么哈希查找应该可以忽略不计，即使存在冲突。您是否真的分析过并看到查找很关键？
所以我的建议是将精力集中在其他事情上，完美的哈希函数很可能不会为您的情况带来任何改进的性能。
我要更进一步说，我认为对于少于 50 个元素的平面地图（好的 ol' vector）将具有类似的性能（或者由于缓存局部性可能更好） ).但同样，需要进行测量。
我有一组 C++ 函数。我想将此函数映射到散列 table 中，例如：unordered_map<function<ReturnType (Args...)> , SomethingElse>，其中 SomethingElse 与此问题无关。
这组函数是以前已知的，小的（比方说少于 50）和静态的（不会改变）。
由于查找性能至关重要（应该在O(1)中执行），我想定义一个完美的哈希函数。
是否存在适合这种情况的完美哈希函数生成器？
我知道存在完美的散列函数生成器（如 GPERF or CMPH），但由于我从未使用过它们，所以我不知道它们是否适合我的情况table。
原因：
我正在尝试设计一个框架，给定一个用 C++ 编写的程序，用户可以 select 该程序中定义的函数的一个子集 F。
对于属于 F 的每个 f，框架实施了一个 memoization 策略：当我们使用输入 i 调用 f 时，我们存储 (i,o) 在一些数据结构中。因此，如果我们要用 i 调用 AGAIN f，我们将 return o 而无需再次执行（耗时的）计算。
"already computed results"将在不同用户之间共享（可能在云端），因此如果用户u1已经计算了o，用户u2将节省计算用 i 调用 f 的时间（使用与之前相同的注释）。
显然，我们需要存储对的集合(f,inputs_sets)（其中inputs_sets是我之前讲过的已经计算出的结果集），这是原题：我该怎么做？
因此，在这种情况下使用评论中提出的 "enumeration trick" 可能是一种解决方案，假设所有用户都使用 完全相同的 枚举，这可能成为一个问题：假设我们的程序有 f1、f2、f3 如果 u1 只想记忆 f1 和 f2 怎么办（所以F={f1,f2})，而 u2 只想记忆 f3（所以 F={f3}）？一个矫枉过正的解决方案可能是枚举程序中定义的所有函数，但这会产生巨大的内存浪费。
好吧，也许这不是您想听到的，但考虑一下：既然您谈论的函数很少，少于 50 个，那么哈希查找应该可以忽略不计，即使存在冲突。您是否真的分析过并看到查找很关键？
所以我的建议是将精力集中在其他事情上，完美的哈希函数很可能不会为您的情况带来任何改进的性能。
我要更进一步说，我认为对于少于 50 个元素的平面地图（好的 ol' vector）将具有类似的性能（或者由于缓存局部性可能更好） ).但同样，需要进行测量。