hash - 完美的哈希函数？

Question

在阅读 Wikipedia 上的鸽巢原理时，我遇到了 - “在哈希表中冲突是不可避免的，因为可能的键数超过了数组中的索引数。没有哈希算法，无论多么聪明，都可以避免这些冲突”。但是gperf不正是这样做的吗？

请赐教。

Answer 1

gperf根据预定义的字符串列表创建哈希函数和哈希表。

因此，在我看来，gperf创建散列的时间足够长，以便有足够的可能性。
只有当您预先知道所有可能的密钥时，您才能做到这一点 - 这是一个假设，维基百科条目中的描述并不成立，这显然与“非常量”哈希表有关。

Answer 2

来自 gperf 的网站：“对于给定的字符串列表，它会生成一个哈希函数和哈希表，......” - 这意味着它必须事先知道所有字符串才能准备一个没有冲突的函数。

您在一般编程语言中使用的常用哈希函数能够将任何字符串作为输入一个接一个地处理（列表不是一次给出的），因此它们可能会产生冲突。