完美哈希函数生成器适用于函数

Question

我有一组C++函数。我想将这些函数映射到哈希表中，类似于：unordered_map<function<ReturnType (Args...)> , SomethingElse>，其中SomethingElse与此问题无关。

这组函数是预先知道的，很小（不到50个）且静态（不会改变）。

由于查找性能至关重要（应该在O(1)中执行），我想定义一个完美的哈希函数。

存在适用于此场景的完美哈希函数生成器吗？

我知道存在完美哈希函数生成器（如GPERF或CMPH），但由于我从未使用过它们，我不知道它们是否适合我的情况。

原因：

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

对于每个属于F的f，该框架实现了一种记忆化策略：当我们使用输入i调用f时，我们将(i，o)存储在某些数据结构中。因此，如果我们要再次使用i调用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}）怎么办？一个过度解决方案可能是枚举程序中定义的所有函数，但这可能会浪费大量内存。

- justHelloWorld

---

如果只是声明一个枚举类型（每个函数对应一个枚举值）和一个常量函数数组，并将你的“查找”操作作为数组查找，使用枚举值作为键，这样做是否被视为作弊？我认为这将完全避免哈希问题并给出最佳性能。 - Jeremy Friesner

你打算如何使用你的映射表？我的意思是-你的查找是仅通过显式名称执行的吗，例如map.lookup(foo)，其中foo是实际函数名，还是有一些运行时函数指针传递为参数？如果是前者，你可能希望哈希也在编译时执行，这样它就不再是时间关键性任务了。 - CygnusX1

@MikeMB 二分查找需要相等性，但std::function没有实现（正如@Tony所建议的）。@hvd 我从未谈论过字符串。 - justHelloWorld

@MikeMB 实际上，任何能够唯一标识函数的解决方案都应该可以。因此，我们甚至可以将函数头作为字符串使用，但这样做非常丑陋（而且我认为也不太有效率）。我认为使用 std::function 应该更安全、更高效。 - justHelloWorld

是的，这非常关键 - 因为第一直觉是要对函数地址进行某些操作 - 这在不同的运行和编译中可能会有所不同。因此，第一个问题应该是如何获得任何类型的一致ID，无论是否用于哈希。 - CygnusX1

Answer 1

好的，也许这不是你想听到的，但请考虑一下：由于你提到的函数很少，少于50个，即使有冲突，哈希查找的开销应该可以忽略不计。你是否实际进行了分析并发现查找是关键问题？

因此，我的建议是将精力集中在其他方面，对于你的情况，完美哈希函数可能不会带来任何性能改进。

我要更进一步地说，我认为对于少于50个元素，一个平面映射（好老式的vector）可能具有类似的性能（或者甚至更好，因为它具有缓存局部性）。但是，需要进行测量。

- bolov

---

这并不意味着这个问题不有趣。对于确实需要解决的情况和寻找解决方案的乐趣，应该有一个实际的解决方案。我只是认为在你的特定情况下，这并不合理。 - bolov

我还没有进行过性能分析。所以你建议我尝试使用一个简单的向量并对其进行线性搜索？ - justHelloWorld

@justHelloWorld 是的.. 你也可以尝试使用boost flat_mat，它可以保持排序并具有log n搜索复杂度。还要进行性能分析！如果没有性能分析，谈论优化几乎没有意义。找到热点和瓶颈，然后优化那部分！在程序运行时间仅占0.1％的代码部分进行优化是毫无意义的。 - bolov