预先知道的字符串的完美哈希函数

Question

我有4000个字符串,我想用这些字符串创建一个完美的哈希表.字符串是事先知道的,所以我的第一个想法是使用一系列if语句:

 if (name=="aaa")
      return 1;
 else if (name=="bbb")
      return 2;
        .
        .
        .
 // 4000th `if' statement

但是,这将是非常低效的.有没有更好的办法？

Answer 1

迟到总比不到好，我相信这现在终于回答了OP的问题：

只需使用https://github.com/serge-sans-paille/frozen —— C++ 的不可变容器的编译时 (constexpr) 库（在底层使用“完美哈希”）。

在我的测试中，它与著名的 GNU 的gperf完美哈希 C 代码生成器配合使用。

根据您的伪代码术语：

#include <frozen/unordered_map.h>
#include <frozen/string.h>

constexpr frozen::unordered_map<frozen::string, int, 2> olaf = {
    {"aaa", 1},
    {"bbb", 2},
    .
    .
    .
    // 4000th element
};

return olaf.at(name);

将在O(1)时间内响应，而不是 OP 的O(n) - O(n) 假设编译器不会优化你的 if 链，它可能会这样做）

Answer 2

gperf 是一个完全相同的工具:

GNU gperf是一个完美的哈希函数生成器.对于给定的字符串列表,它以C或C++代码的形式生成散列函数和散列表,用于根据输入字符串查找值.散列函数是完美的,这意味着散列表没有冲突,并且散列表查找只需要单个字符串比较.

根据文档,gperf用于为GNU C,GNU C++,GNU Java,GNU Pascal,GNU Modula 3和GNU缩进中的词法分析器生成保留关键字识别器.

它的工作方式在GPERF中描述:道格拉斯C.施密特的完美哈希函数发生器.

Answer 3

由于这个问题仍然没有答案，并且我即将向我的 HFT 平台添加相同的功能，因此我将分享我的C++ 完美哈希算法清单。找到一个开放、灵活且无错误的实现比我想象的要困难，所以我分享了我还没有放弃的实现：

• CMPH 库，包含论文和此类算法的集合 - https://git.code.sf.net/p/cmph/git
• BBHash，论文作者的另一个实现 - https://github.com/rizkg/BBHash
• Ademakov 的——上述论文的另一个实现——https: //github.com/ademakov/PHF
• wahern/phf ——我目前正在检查这个并试图解决它在处理大型键集上的 C++ 字符串时存在的一些分配错误——https: //github.com/wahern/phf.git
• emphf——似乎无人管理——https: //github.com/ot/emphf.git