如果哈希集只包含任何不同元素的一个实例,在这种情况下如何发生冲突?
加载因子怎么可能成为问题,因为任何给定元素只有一个?
虽然这是作业,但不适合我。我正在辅导某人,我需要知道如何向他们解释。
最佳答案
假设您有一个整数 HashSet,并且您的哈希函数是 mod 4。如果您尝试插入整数 0、4、8、12、16 等,它们都会发生冲突。 (mod 4 是一个糟糕的哈希函数,但它说明了这个概念)
假设功能正常,负载因子与发生碰撞的可能性相关;请注意,我说的是相关而不是相等,因为这取决于您用来处理冲突的策略。通常,高负载系数会增加碰撞的可能性。假设你有 4 个槽并且你使用 mod 4 作为散列函数,当加载因子为 0(空表)时,你不会发生冲突。当你有一个元素时,发生碰撞的概率是 0.25,这显然会降低性能,因为你必须解决碰撞。
现在,假设您使用线性探测(即在发生碰撞时,使用下一个可用条目),一旦达到表中的 3 个条目,发生碰撞的概率为 0.75,如果发生碰撞,则最好的情况你会去下一个条目,但在最坏的情况下,你将不得不通过 3 个条目,所以冲突意味着你需要平均线性搜索而不是直接访问,平均 2 个项目.
当然,您有更好的策略来处理碰撞,通常,在非病态情况下,0.7 的负载是可以接受的,但之后碰撞会激增,性能会下降。
关于java - 哈希集如何发生冲突?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/8220535/