如果哈希集合中只包含任何不同元素的一个实例,那么在这种情况下如何发生冲突?
既然每个给定元素只有一个,负载因子如何成为问题?
虽然这是一项作业,但不是我做的。我正在辅导别人,我需要知道如何向他们解释。
当你这样做时,你会得到一个数字,对于一个十个字符的字符串来说,它将在600到1280之间。现在,如果你将其除以500并取余数,你将得到一个介于0和499之间的值。(请注意,字符串不必是十个字符--更长的字符串将增加到更大的值,但当你除以并取余数时,你仍然得到一个介于0和499之间的数字。)
现在创建一个500个条目的数组,每次获得一个新对象时,按照上述描述计算其哈希值,并使用该值索引到数组中。将新对象放入对应于该索引的数组条目中。
但是(特别是使用上面的天真哈希算法),你可能会有两个不同的字符串具有相同的哈希值。例如,“ABC”和“CBA”将具有相同的哈希值,并最终进入数组中的同一槽位。
为了处理这种“冲突”,有几种策略,但最常见的是在数组条目上创建一个链接列表,并将各种“哈希同义词”放入该列表中。
通常情况下,您会尝试使数组足够大(并使用更好的哈希计算算法)以最小化这种冲突,但是使用哈希方案,无法绝对防止冲突。