c - C 的哈希表实现

Question

什么是 C 的好的哈希表实现？我需要将它与 mpicc 编译器一起使用。不需要删除功能。

Answer 1

glib中的那个非常好。不过，不确定它是否太大和/或可能与 glib 的其余部分隔离。

如果做不到这一点，Pearson 散列似乎是实现您自己的一个很好的起点（它是针对具有 8 位寄存器的机器优化的散列函数）。

Answer 2

如果事先知道所有键，您可以使用完美的哈希生成器来避免哈希表中隐含的空间开销。

另一方面，如果你真的需要一个完整的哈希表，我建议使用Cuckoo Hashing的变体（例如 d-ary 版本）。

我满意地使用了Hopscotch Hashing的简化版本，即使在更高的负载因子下也能很好地工作。