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

Question

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

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

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

score 3 · Accepted Answer

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

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

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

score 3 · Accepted Answer

在没有使用预处理器的外部库的情况下，在 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

score 0 · Accepted Answer

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

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

3 回答 3

Related

Reference