是否有任何实现可以在通用哈希中选择多个哈希函数并尝试这些函数将总冲突减少到可接受的水平并以最少的冲突返回最佳结果？
如果有的话，从现有数组构建哈希表比先创建哈希表然后插入所有元素可靠得多，不是吗？
以下段落来自算法简介。
“如果恶意对手选择要通过某个固定哈希函数进行哈希处理的 key ，那么对手可以选择所有哈希到同一槽的 n 个 key ，从而产生平均检索时间 ‚.n/。任何固定哈希函数很容易受到这种可怕的最坏情况行为的影响；改善这种情况的唯一有效方法是以独立于实际要存储的 key 的方式随机选择哈希函数。这种方法称为通用哈希，可以无论对手选择哪个键，平均都会产生可证明的良好性能。
在通用哈希中，在执行开始时我们选择哈希函数 从精心设计的一类函数中随机选择。与快速排序的情况一样，随机化保证没有任何单个输入总是会引发最坏情况的行为。因为我们随机选择哈希函数，所以即使对于相同的输入，算法在每次执行时也可以表现不同，从而保证良好的结果 任何输入的平均情况性能。回到编译器的例子 符号表中，我们发现程序员对标识符的选择现在不会导致哈希性能持续不佳。仅当编译器选择随机哈希函数导致标识符集哈希效果不佳时，才会出现性能较差的情况，但这种情况发生的概率很小，并且对于任何相同大小的标识符集都是相同的。”
最佳答案
如果你事先知道 key ，可以使用 perfect hashing以避免任何碰撞。因此，如果您将所有元素都放在某处(如您的示例中的数组中)，并且不会有新的插入，那么当然，您可以做得更好。
问题是，在真实的应用程序中，按键通常会来来去去。该表不断变化。
我不了解实现，但一如既往，它归结为权衡。您试图用额外的安全性来换取快速查找，并且您将付出额外的代码复杂性和速度减慢以及潜在昂贵的插入的代价，插入将在存在大量冲突时重新创建哈希。但你真的需要那种安全感吗？如果有很多冲突，为什么不简单地增加表的大小呢？
reduce the total collisions to an acceptable level
发生大量冲突的可能性非常小(通过良好的实现可以使表不致密集)，并且您已经保护算法免受恶意输入的影响(因为攻击者不知道如何滥用 key )。对于现实生活中的应用程序，这已经比“可接受的水平”要好得多。
关于c++ - 从现有数组构建哈希表比先创建哈希表然后插入所有元素更好吗？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/33240960/