开散列法和闭散列法

散列表是一种常见的数据结构，用于实现快速查找和插入。在散列表中，数据项通过哈希函数映射到数组中的位置。然而，不同的输入可能映射到相同的位置，称为哈希冲突。为了解决哈希冲突，散列表使用两种方法：开散列法和闭散列法。

开散列法，也称为链式哈希表，使用链式存储来解决哈希冲突。当两个数据项映射到相同的数组位置时，将它们存储在同一个链表中。如图1所示，两个键值为4和9的数据项都存储在数组的第1个位置，使用链表进行连接。这个过程称为“开链”。


闭散列法，也称为开地址哈希表，使用数组来存储所有数据项。当数据项映射到数组的某个位置时，该位置被占用。如果该位置被占用，则使用特定的技术进行解决冲突，例如线性探测、二次探测和双重散列。如图2所示，键值为4和9的数据项都被分配到不同的位置，使用线性探测来解决冲突。这个过程称为“闭链”。


两种方法都有自己的优点和缺点。以下是它们的比较：

1. 内存使用：开散列法通常需要更多的内存，因为它需要存储指向链表的指针。闭散列法只需要一个数组来存储所有数据项。

2. 插入和查找时间：开散列法的插入和查找时间取决于链表长度。如果链表很长，时间会变慢。闭散列法的时间复杂度通常是O(1)。然而，在处理大量数据时，开链会更快，因为开链通常只处理小的冲突，而闭链处理所有的冲突。当给定哈希函数时，闭散列法的性能比开散列法更容易受到哈希冲突的影响。

3. 增量式哈希：闭散列法通常更适合增量式哈希，这意味着可以在哈希表中插入或删除数据项，而不需要重新哈希所有现有数据项。这是因为在闭散列法中，只有被修改的位置必须重新哈希。在开散列法中，由于链表连接，每个位置后面的数据项都必须重新哈希。

总之，开散列法和闭散列法都有它们的优点和缺点。选择哪种方法取决于特定的应用程序需求。