提前知道字符串的完美哈希函数

Question

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

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

然而，这样做效率非常低。有更好的方法吗？

- bambi kirkayak

---

如果您事先知道所有字符串，您确定需要对它们进行哈希吗？ - NPE

我需要将一个图存储为邻接表，所以我猜需要使用哈希表。@NPE - bambi kirkayak

哈希是处理如此多字符串的最有效的方法，如果您对您的字符串有先验信息，可以使用类似于gperf的东西创建良好的哈希函数。 - computador7

Answer 1

gperf是一个能够生成完美哈希函数的工具。

对于给定的字符串列表，GNU gperf会生成一个哈希函数和哈希表（以C或C++代码形式），用于根据输入的字符串查找值。哈希函数是完美的，这意味着哈希表没有冲突，并且哈希表查找仅需要进行一次字符串比较。

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

它的运作方式在Douglas C. Schmidt所写的《GPERF: A Perfect Hash Function Generator》一书中有描述。

- NPE

---

我认为这对我的应用程序来说太过复杂了，我更喜欢简单的东西。 - bambi kirkayak

我会收藏这个帖子，以便查看您的完美解决方案，它比gperf更简单。 - Hans Klünder

一个运行时解决方案可能更容易构建。这个库在内存方面显然更有效率：http://cmph.sourceforge.net/ - Victor Sergienko

Answer 2

比不做好，我相信现在终于回答了OP的问题：只需使用https://github.com/serge-sans-paille/frozen这个C++编译时（constexpr）不可变容器的库（在底层使用“完美哈希”），就可以解决问题。通过我的测试，其性能与著名的GNU's 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(n) 时间复杂度，将会在 O(1) 时间内做出回应。（假设编译器没有优化您的if链，但它可能会进行优化）

- zertyz

Answer 3

由于该问题仍未得到解答，而我正准备向我的HFT平台添加相同的功能，因此我将分享我在C ++中的完美哈希算法库存。找到一个开放的、灵活的和没有错误的实现比我想象中要困难，所以我要分享一些我还没有放弃的:

• CMPH库，提供了一组论文和相关算法 - https://git.code.sf.net/p/cmph/git
• BBHash，来自一篇论文作者的另一个实现 - https://github.com/rizkg/BBHash
• Ademakov's - 上述论文的另一种实现方式 - https://github.com/ademakov/PHF
• wahern/phf - 我目前正在检查这个库，并尝试解决处理大量键集时出现的一些分配错误 - https://github.com/wahern/phf.git
• emphf - 看起来已经不再维护了 - https://github.com/ot/emphf.git

- zertyz

Answer 4

我认为@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

然后你可以使用 gperf 命令创建一个名为 lookups.hpp 的文件，命令非常简单：

 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。

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

- Escualo