java - 哈希集如何发生冲突？

Question

如果哈希集只包含任何不同元素的一个实例，在这种情况下如何发生冲突？

加载因子怎么可能成为问题，因为任何给定元素只有一个？

虽然这是作业，但不适合我。我正在辅导某人，我需要知道如何向他们解释。

Answer 1

假设您有一个整数 HashSet，并且您的哈希函数是 mod 4。如果您尝试插入整数 0、4、8、12、16 等，它们都会发生冲突。 (mod 4 是一个糟糕的哈希函数，但它说明了这个概念)

假设功能正常，负载因子与发生碰撞的可能性相关；请注意，我说的是相关而不是相等，因为这取决于您用来处理冲突的策略。通常，高负载系数会增加碰撞的可能性。假设你有 4 个槽并且你使用 mod 4 作为散列函数，当加载因子为 0(空表)时，你不会发生冲突。当你有一个元素时，发生碰撞的概率是 0.25，这显然会降低性能，因为你必须解决碰撞。

现在，假设您使用线性探测(即在发生碰撞时，使用下一个可用条目)，一旦达到表中的 3 个条目，发生碰撞的概率为 0.75，如果发生碰撞，则最好的情况你会去下一个条目，但在最坏的情况下，你将不得不通过 3 个条目，所以冲突意味着你需要平均线性搜索而不是直接访问，平均 2 个项目.

当然，您有更好的策略来处理碰撞，通常，在非病态情况下，0.7 的负载是可以接受的，但之后碰撞会激增，性能会下降。