algorithm - 什么散列函数在对 n 个键进行散列时产生最大碰撞次数？

Question

我的问题与碰撞有关。散列 n 个键可能导致的最大冲突次数是多少？我相信你可以通过n-1找到它。但我不确定这是否正确。我特别想找出一个会产生那么多冲突的哈希函数。我只是很难理解这个问题的概念。任何有关该主题的帮助将不胜感激!

Answer 1

最大碰撞次数等于您散列的项目数。

---

例子:

哈希函数:h(x) = 3

所有项目都将散列到 key 3。

---

请注意，键的数量，在您的情况下为 n，不会影响答案，因为无论您有多少键，您的项目总是使用上面提供的 h(x) 在 key 3 中进行哈希处理。

---

可视化:

通常，散列看起来像这样:

但是如果我想有最大的碰撞次数，那么，通过使用上面提供的h(x)，我会得到我所有的项目(图片中的名字)都散列到改变相同的 key ，即 key 3。

所以在那种情况下，最大冲突次数是名称的数量，5。