HashTables如何处理冲突？

Question

我在我的学位课程中听说，HashTable如果新的Key条目与另一个碰撞，则a 将在“下一个可用”存储桶中放置一个新条目。HashTable如果使用碰撞键向后退时发生碰撞，仍然如何返回正确的值？我假设Keysare String类型，并且hashCode()返回说Java生成的默认值。如果我实现自己的哈希函数并将其用作查找表的一部分（即a HashMap或Dictionary），那么存在哪些处理冲突的策略？我什至看到与质数有关的注释！Google搜索中的信息不太清楚。

Answer 1

哈希表以两种方式之一处理冲突。

选项1：让每个存储桶包含散列到该存储桶的元素的链表。这就是为什么无效的哈希函数会使哈希表中的查询变得非常慢的原因。

选项2：如果哈希表条目都已满，则哈希表可以增加其拥有的存储桶数，然后重新分配表中的所有元素。哈希函数返回一个整数，哈希表必须采用哈希函数的结果，并针对表的大小对其进行修改，以确保可以将其存储到存储桶中。因此，通过增加大小，它将重新哈希并运行取模运算，如果幸运的话，可能会将对象发送到不同的存储桶。

Java在其哈希表实现中同时使用了选项1和2。

Answer 2

有多种技术可用于处理碰撞。我会解释一些

链接： 在链接中，我们使用数组索引存储值。如果第二个值的哈希码也指向同一索引，则我们用链接列表替换该索引值，并且所有指向该索引的值都存储在链接列表中，而实际数组索引指向链接列表的开头。但是，如果只有一个哈希码指向数组的索引，则该值将直接存储在该索引中。检索值时应用相同的逻辑。在Java HashMap / Hashtable中使用它来避免冲突。

线性探测：当表中的索引多于要存储的值时，将使用此技术。线性探测技术适用于不断增加直到找到空插槽的概念。伪代码如下所示：

index = h(k) 

while( val(index) is occupied) 

index = (index+1) mod n

双重哈希技术：在这项技术中，我们使用两个哈希函数h1（k）和h2（k）。如果h1（k）处的时隙被占用，则第二个哈希函数h2（k）用于增加索引。伪代码如下所示：

index = h1(k)

while( val(index) is occupied)

index = (index + h2(k)) mod n

线性探测和双重哈希技术是开放式寻址技术的一部分，并且仅当可用插槽大于要添加的项数时才可以使用它。与链接相比，它占用的内存更少，因为这里没有使用额外的结构，但是由于移动过多而导致速度变慢，直到找到一个空插槽为止。同样在开放式寻址技术中，当将项目从插槽中移出时，我们放置一个墓碑以指示该项目从此处移出，这就是其为空的原因。