如何创建高效的静态哈希表？

Question

我需要从中创建中小型静态哈希表。通常，这些条目将包含 5-100 个条目。创建哈希表时，所有键哈希值都是预先已知的（即键已经是哈希值）。目前，我创建一个 HashMap，对键进行排序，这样我就可以进行 O(log n) 查找，其中 3-5平均查找我关心的尺寸。 Wikipedia 声称带有链接的简单哈希表平均会导致整个表进行 3 次查找，因此对我来说这还不值得麻烦（即将 hash%n 作为第一个条目并进行链接。）鉴于此我预先知道所有哈希值，似乎应该有一种简单的方法来获得快速、静态的完美哈希值——但我找不到一个好的指针。 IE。摊销 O(1) 访问，没有（很少？）额外开销。我应该如何实现这样的静态表？

内存使用很重要，所以我需要存储的数据越少越好。

编辑：请注意，如果我必须手动解决一次碰撞左右，那也没关系。 IE。例如，如果我可以做一些平均具有直接访问和最坏情况 3 个间接访问的链接，那很好。这并不是说我需要一个完美的哈希值。

Answer 1

对于 C 或 C++，您可以使用 gperf

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

GNU gperf 是高度可定制的。有一些选项可用于生成 C 或 C++ 代码、发出 switch 语句或嵌套 ifs 而不是哈希表，以及调整 gperf 使用的算法。

Answer 2

使用预处理器在没有外部库的情况下，在 C 中也可以实现小型哈希，例如：

swich (hash_string(*p))
{
case HASH_S16("test"):
    ...
    break;
case HASH_S256("An example with a long text!!!!!!!!!!!!!!!!!"):
    ...
    break;
}

查看代码@ http://www.heeden.nl/statichashc.htm

Answer 3

您可以使用 Sux4j 在 Java 或 C++ 中生成最小完美哈希。 （我不确定您是否使用 Java，但您提到了 HashMap，所以我假设。）对于 C，您可以使用 cmph 库。