解决哈希冲突的方式

人不走空

     🌈个人主页：人不走空      

💖系列专栏：算法专题

⏰诗词歌赋：斯是陋室，惟吾德馨

解决哈希冲突的方式有多种，以下是一些常见的方法：

1.链地址法（Separate Chaining）：

在链地址法中，每个哈希桶（槽位）都维护一个链表（或其他数据结构，如红黑树），当发生哈希冲突时，新的元素被添加到相应槽位的链表中。这样，同一个槽位上的元素形成了一个链表，可以通过链表来存储具有相同哈希值的多个元素。

以下是链地址法的基本思想：

1. 插入操作： 当需要插入一个新元素时，首先计算其哈希值，然后定位到相应的哈希桶。如果该桶为空，直接插入；如果不为空，将新元素添加到链表的末尾。
   
2. 查找操作： 查找时同样计算哈希值并定位到相应的哈希桶，然后在链表中查找目标元素。
   
3. 删除操作： 删除操作也需要先找到对应的哈希桶，然后在链表中删除目标元素。
   

这种方法的优势在于它相对简单，易于实现，而且可以有效地处理大量的哈希冲突。然而，性能取决于链表的长度，当链表变得过长时，可能会降低查找效率。在实际应用中，一些哈希表实现可能会在链表长度达到一定阈值时，转换为更高效的数据结构，如红黑树，以提高性能。

2.开放寻址法（Open Addressing）：

开放寻址法是另一种解决哈希冲突的方法，与链地址法不同，它不使用额外的数据结构（如链表），而是直接在哈希表中寻找下一个可用的槽位。

在开放寻址法中，当发生哈希冲突时，通过一系列的探测序列（probe sequence）来寻找下一个可用的槽位。这个探测序列的生成方式有多种，常见的包括线性探测、二次探测和双重散列。

以下是开放寻址法的基本思想：

1. 插入操作： 当需要插入一个新元素时，首先计算其哈希值，然后尝试将元素插入计算得到的槽位。如果槽位为空，插入成功；如果槽位被占用，根据探测序列继续寻找下一个可用的槽位，直到找到为止。
   
2. 查找操作： 查找时同样计算哈希值并尝试在计算得到的槽位查找目标元素。如果槽位为空，说明目标元素不存在；如果槽位被占用，根据探测序列继续寻找，直到找到目标元素或者遇到空槽。
   
3. 删除操作： 删除操作也需要先找到对应的哈希桶，然后在探测序列中删除目标元素。删除通常通过标记删除（如设置一个特殊标记）或者实际删除来实现。
   

不同的探测序列方式影响了开放寻址法的性能，选择适合应用场景的探测序列是重要的。线性探测、二次探测、双重散列等都是常见的探测序列方式。

线性探测再散列即依次向后查找；

二次探测再散列，即依次向前后查找，增量为1、2、3的二次方；

伪随机，顾名思义就是随机产生一个增量位移。

3.线性探测（Linear Probing）：

如果哈希冲突发生，线性探测会逐个检查下一个槽位，直到找到空槽为止。

4.双重散列（Double Hashing）：

使用第二个哈希函数来计算步长，如果发生冲突，使用第二个哈希函数计算新的槽位。

5.再哈希（Rehashing）：

当哈希表达到一定负载因子时，可以重新调整哈希表的大小，选择新的哈希函数，然后重新插入所有的元素。

不同的解决冲突方法有各自的优缺点，选择哪种方式取决于具体的应用场景和性能要求。