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

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 is a perfect hash function generator. For a given list of strings, it produces a hash function and hash table, in form of C or C++ code, for looking up a value depending on the input string. The hash function is perfect, which means that the hash table has no collisions, and the hash table lookup needs a single string comparison only.

GNU gperf is highly customizable. There are options for generating C or C++ code, for emitting switch statements or nested ifs instead of a hash table, and for tuning the algorithm employed by gperf.