散列表查找 - 使用完美散列,在C中

Question

我有一个C语言应用程序,我需要进行表查找.

条目是字符串,所有在运行时开始时都是已知的.该表初始化一次,然后多次查找.该表可以更改,但它基本上就像应用程序重新开始一样.我想这意味着我可以使用完美哈希？可以花一些时间进行哈希表初始化,因为它只发生一次.

将有3到100,000个条目,每个条目都是唯一的,我估计80%的案例将少于100个条目.在这些情况下,简单的天真查找"足够快".(==没有人在抱怨)

但是,在有10k +条目的情况下,天真方法的查找速度是不可接受的.在C中为字符串提供良好的基于​​散列表的查找性能的好方法是什么？假设我没有像Boost/etc这样的第三方商业图书馆.我应该使用什么哈希算法？我该如何决定？

Answer 1

生成完美的哈希值并不是一个简单的问题。有一些图书馆专门致力于这项任务。在这种情况下，最受欢迎的可能是CMPH。我还没有使用过它，所以无法提供除此之外的帮助。gperf是另一个工具，但它要求在编译时已知字符串（您可以通过编译 .so 并加载来解决它，但有点矫枉过正）。

但坦率地说，我至少会尝试先进行二分搜索。只需使用 对数组进行排序qsort，然后使用 进行搜索bsearch（或自行滚动）。这两个都是自 C89 以来的一部分stdlib.h。