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

Question

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

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

然而，这将是非常低效的。有没有更好的办法？

Answer 1

gperf是一个可以做到这一点的工具：

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

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

它的工作方式在GPERF: A Perfect Hash Function Generator by Douglas C. Schmidt 中进行了描述。

Answer 2

由于这个问题仍未得到解答，并且我即将在我的 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

Answer 3

我相信@NPE 的回答非常合理，我怀疑这对您的应用程序来说太过分了，正如您所暗示的那样。

考虑以下示例：假设您的“引擎”逻辑（即：您的应用程序的功能）包含在名为 的文件中engine.hpp：

// this is engine.hpp
#pragma once
#include <iostream>
void standalone() {
  std::cout << "called standalone" << std::endl;
}
struct Foo {
  static void first() {
    std::cout << "called Foo::first()" << std::endl;
  }
  static void second() {
    std::cout << "called Foo::second()" << std::endl;
  }  
};
// other functions...

并假设您想根据地图调度不同的功能：

"standalone" dispatches void standalone()
"first" dispatches Foo::first()
"second" dispatches Foo::second()
# other dispatch rules...

您可以使用以下 gperf 输入文件（我称之为“lookups.gperf”）来做到这一点：

%{

#include "engine.hpp"

struct CommandMap {
    const char *name;
    void (*dispatch) (void);
};

%}

%ignore-case
%language=C++
%define class-name Commands
%define lookup-function-name Lookup
struct CommandMap

%%
standalone, standalone
first, Foo::first
second, Foo::second

lookups.hpp然后你可以使用 gperf使用一个简单的命令来创建一个文件：

 gperf -tCG lookups.gperf > lookups.hpp

一旦我有了它，以下main子例程将根据我输入的内容调度命令：

#include <iostream>
#include "engine.hpp" // this is my application engine
#include "lookups.hpp" // this is gperf's output

int main() {

  std::string command;

  while(std::cin >> command) {
    auto match = Commands::Lookup(command.c_str(), command.size());
    if(match) {
      match->dispatch();
    } else {
      std::cerr << "invalid command" << std::endl;
    }
  }
}

编译它：

 g++ main.cpp -std=c++11

并运行它：

$ ./a.out
standalone
called standalone
first
called Foo::first()
Second
called Foo::second()
SECOND
called Foo::second()
first
called Foo::first()
frst
invalid command

请注意，一旦您生成lookups.hpp了应用程序，在 gperf 中就没有任何依赖关系。

免责声明：我从这个网站获得了这个例子的灵感。

Answer 4

Better later than never, I believe this now finally answers the OP question:

Simply use https://github.com/serge-sans-paille/frozen -- a Compile-time (constexpr) library of immutable containers for C++ (using "perfect hash" under the hood).

On my tests, it performed in pair with the famous GNU's gperf perfect hash C code generator.

On your pseudo-code terms:

#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);

Will respond in O(1) time rather than OP's O(n) -- O(n) assuming the compiler wouldn't optimize your if chain, which it might do)