哈希表查找 - 与完美哈希，在C

Question

我有一个C语言应用程序，我需要做表查找。

条目是字符串，全部在运行时开始已知。该表初始化一次，然后多次查找。表格可以更改，但基本上就好像应用程序重新开始。我认为这意味着我可以使用完美哈希？可以花费一些时间进行散列表初始化，因为它只发生一次。

将会有3到100,000个条目，每个条目都是唯一的，我估计80％的案例将少于100个条目。在这些情况下，简单朴素的查找“足够快”。 （==没有人抱怨）

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

Answer 1

生成一个完美的散列并不是一个简单的问题。有专门负责这项任务的图书馆。 在这种情况下，最流行的可能是CMPH。尽管如此，我还没有使用它，所以无法帮助。 gperf是另一个工具，但它需要在编译时知道字符串（你可以通过编译.so和加载来解决它，但有点矫枉过正）。

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

Answer 2

如果一个天真的（我认为你的意思是线性的）方法对于100个条目是可以的（所以50个比较平均完成），那么二进制搜索对于100,000个条目就足够了（它最多需要17次比较）。

所以我不打扰哈希，但只是在启动时（例如使用qsort）对二进制搜索进行排序（例如使用bsearch）来查找条目。

Answer 3

如果（最大）表的大小是已知的，则带有链接的纯哈希表很容易实现。大小开销每个项目只有两个整数。使用合理的散列函数平均只需要每个查询1.5个探针，这对于100％加载的表来说是这样。

构建一个完美的散列只有在你的数据没有改变时才是可行的。一旦它发生变化，你将不得不重新计算和重新组合，这比做一些额外的比较要昂贵得多。