c++ - 从现有数组构建哈希表是否比先创建哈希表然后插入所有元素更好？

Question

是否有任何实现可以在通用哈希中选择多个哈希函数并尝试使用这些函数将总冲突减少到可接受的水平并返回冲突最少的最佳结果？

如果有，从现有数组构建哈希表比先创建哈希表然后插入所有元素可靠得多，不是吗？

以下段落来自算法简介。

“如果恶意对手选择要通过某个固定散列函数进行散列的键，那么对手可以选择 n 个键，这些键都散列到同一个槽中，平均检索时间为 ‚.n/。任何固定散列函数很容易受到这种可怕的最坏情况行为的影响；改善这种情况的唯一有效方法是以独立于实际要存储的 key 的方式随机选择散列函数。这种称为通用散列的方法可以无论对手选择哪个键，平均都能产生可证明的良好性能。

在通用哈希中，在开始执行时我们选择哈希函数从精心设计的函数类中随机抽取。与快速排序的情况一样，随机化保证没有单一输入总是会引起最坏情况的行为。因为我们随机选择哈希函数，所以算法在每次执行时都会有不同的表现，即使对于相同的输入，保证良好任何输入的平均情况下的性能。回到编译器的例子符号表，我们发现程序员对标识符的选择现在不会导致始终较差的散列性能。只有当编译器选择了一个导致标识符集合的哈希值很差的随机哈希函数时，才会出现性能不佳的情况，但这种情况发生的概率很小，并且对于任何相同大小的标识符集合都是相同的。”

Answer 1

如果你事先知道 key ，你可以使用perfect hashing以避免任何碰撞。因此，如果您将所有元素都放在某个地方(如您的示例中的数组中)，并且不会有新的插入，那么当然，您可以做得更好。

问题是，在实际应用中，按键通常来来去去。表格在不断变化。

我不知道实现，但一如既往地归结为权衡。您正试图用额外的安全性来换取快速查找，并且您将付出额外的代码复杂性和速度减慢以及可能昂贵的插入，该插入将在发生大量冲突时重新创建哈希。但你真的需要那种安全感吗？如果你有很多冲突，为什么不简单地增加表的大小？

reduce the total collisions to an acceptable level

很多冲突的可能性真的很小(有一个很好的实现可以使表不致密)并且您已经保护算法免受恶意输入(因为攻击者不知道如何滥用 key )。对于现实生活中的应用，这已经比“可接受的水平”好得多。