处理冲突

处理散列表中的冲突主要有两种方法：开放寻址法（Open Addressing）和链地址法（Separate Chaining）。以下是这些方法的详细介绍：

开放寻址法（Open Addressing）

开放寻址法是在发生冲突时，通过某种探测技术在散列表中寻找下一个空闲位置来存储元素的方法。主要的探测技术包括：

1. 线性探测（Linear Probing）：

   • 探测函数：$hash(k, i) = (hash_1(k) + i) \mod N$
   • 其中 $hash_1(k)$ 是原始散列函数，$i$ 是探测次数。
   • 线性探测通过在数组中线性地寻找下一个空闲位置。

2. 二次探测（Quadratic Probing）：

   • 探测函数：$hash(k, i) = (hash1(k) + c1 \cdot i + c_2 \cdot i^2) \mod N$
   • 其中 $c_1$ 和 $c_2$ 是常数，$i$ 是探测次数。
   • 二次探测通过二次函数增加探测点的间隔，以减少聚集现象。

3. 双重散列（Double Hashing）：

   • 探测函数：$hash(k, i) = (hash1(k) + i \cdot hash2(k)) \mod N$
   • 其中 $hash_1(k)$ 和 $hash_2(k)$ 是两个不同的散列函数，$i$ 是探测次数。
   • 双重散列通过使用第二个散列函数来改变探测序列，以避免聚集。

链地址法（Separate Chaining）

链地址法是将每个数组位置（或称为“槽”）与一个链表（或其他数据结构）关联起来的方法。当发生冲突时，元素会被添加到相应的链表中。

1. 每个数组槽存储一个链表：

   • 当插入一个新元素时，根据散列函数计算出其索引位置，然后将元素添加到该索引位置的链表中。
   • 这种方法的优点是，即使多个元素映射到同一个索引，它们也可以通过链表存储，不会丢失。

2. 删除操作：

   • 在链地址法中，删除元素相对简单，只需从对应的链表中移除即可。

3. 优点：

   • 不会出现“表满”的情况，因为新元素总是可以添加到链表的末尾。
   • 删除操作不会影响其他元素。

4. 缺点：

   • 需要额外的内存空间来存储链表结构。
   • 如果链表过长，查找效率会降低。

课件中还提到了当散列表满时的处理方法，即分配一个更大的散列表，并将所有元素从较小的散列表重新散列到较大的散列表中，然后删除旧表。这是一种动态调整散列表大小以减少冲突和提高性能的方法。