哈希集合如何发生碰撞？

Question

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

既然每个给定元素只有一个，负载因子如何成为问题？

虽然这是一项作业，但不是我做的。我正在辅导别人，我需要知道如何向他们解释。

- farm ostrich

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的负载是可以接受的，但在此之后，冲突会增加并且性能会降低。

- Luis

Answer 2

“哈希表”（其中“哈希集合”是一种变体）背后的基本思想是，你有许多包含“键”值（例如，字符串）的对象，你想将它们放入某种容器中，并能够轻松地按照其“键”值查找单个对象，而不必检查容器中的每个项。

例如，可以将这些值放入已排序的数组中，然后执行二分查找来查找值，但是如果有大量更新，则维护已排序的数组会很昂贵。

因此，对“键”值进行“哈希”。例如，可以将所有字符的ASCII值相加以创建字符串的“哈希”单个数字。（有更好的哈希计算算法，但精确算法并不重要，这是一个容易解释的算法。）

当你这样做时，你会得到一个数字，对于一个十个字符的字符串来说，它将在600到1280之间。现在，如果你将其除以500并取余数，你将得到一个介于0和499之间的值。(请注意，字符串不必是十个字符--更长的字符串将增加到更大的值，但当你除以并取余数时，你仍然得到一个介于0和499之间的数字。)

现在创建一个500个条目的数组，每次获得一个新对象时，按照上述描述计算其哈希值，并使用该值索引到数组中。将新对象放入对应于该索引的数组条目中。

但是(特别是使用上面的天真哈希算法)，你可能会有两个不同的字符串具有相同的哈希值。例如，“ABC”和“CBA”将具有相同的哈希值，并最终进入数组中的同一槽位。

为了处理这种“冲突”，有几种策略，但最常见的是在数组条目上创建一个链接列表，并将各种“哈希同义词”放入该列表中。

通常情况下，您会尝试使数组足够大（并使用更好的哈希计算算法）以最小化这种冲突，但是使用哈希方案，无法绝对防止冲突。

请注意，同义词列表中的多个条目并不相同--它们具有不同的键值--但它们具有相同的哈希值。

- Hot Licks