c - 哈希表查找 - 具有完美的哈希，在 C

Question

我有一个 C 语言应用程序，我需要在其中进行表查找。

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

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

但是，在有 10k+ 个条目的情况下，幼稚方法的查找速度是不可接受的。为 C 中的字符串提供良好的基于​​哈希表的查找性能的好方法是什么？假设我没有像 Boost/etc 这样的第 3 方商业库。我应该使用什么哈希算法？我该如何决定？

Answer 1

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

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

Answer 2

如果幼稚（我假设您的意思是线性）方法适用于 100 个条目（因此平均进行 50 次比较），那么二进制搜索对于 100,000 个条目将绰绰有余（最多需要 17 次比较）。

所以我根本不会打扰哈希，而只是在启动时对字符串表进行排序（例如使用qsort），然后使用二进制搜索（例如使用bsearch）来查找条目。

Answer 3

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

仅当您的数据没有更改时，才能构建完美的哈希。一旦它发生变化，您将不得不重新计算和重新散列，这比进行一些额外的比较要昂贵得多。