开放地址法（Open Addressing，如线性探测、二次探测等）

开放地址法（Open Addressing，如线性探测、二次探测等）

概述

开放地址法，也被称为开放寻址或闭散列，是哈希表处理冲突的一种方法。当哈希函数计算出的哈希地址被占用时，开放地址法会按照一定的策略在线性存储空间上探测其他位置，直到找到一个空位置来存储数据。以下是关于开放地址法的详细解释和几种常见的探测方法：

1. 基本概念：

开放地址法：通过系统的方法找到数组的一个空位，并把这个元素填进去，发生在无法使用哈希函数获得的数组下标情况下。 装填因子λ：通常建议开放定址法的装填因子λ应该低于0.5，以保证哈希表的性能。

2. 探测方法：

线性探测法： 线性探测的增量序列为di = 1, ..., m - 1。 当发生冲突时，从当前位置开始，逐个探测每个单元（必要时可以绕回）以查找出一个空单元。 例如，如果哈希函数计算的原始下标是x，则探测过程为x+1, x+2, x+3...直到找到空位置。 二次探测法： 为了解决线性探测可能带来的聚集问题，二次探测探测相距较远的单元，而不是和原始位置相邻的单元。 探测的过程是x+1, x+4, x+9, x+16...到原始位置的距离是步数的平方。 再散列法： 由于二次聚集的原因，每次移动的长度有规律，解决方法是找到一种依赖于关键字的探测序列。 把关键字通过不同的哈希函数再做一遍哈希化，用这个结果作为步长，每次移动步长个距离。 为了实现想要的效果，第二个哈希函数必须和第一个哈希函数不同，且不能输出0。

3.简单实现

在开放地址法中，处理哈希表的空键主要涉及哈希表的插入和查找操作。以下是关于如何处理哈希表中空键的详细解释： 插入操作 计算哈希地址： 使用哈希函数H(key)计算键key的哈希地址。 检查初始位置： 在哈希表中检查计算出的哈希地址对应的位置是否为空。 如果为空，则直接将键值对插入该位置。 处理冲突： 如果初始位置不为空（即发生冲突），则使用开放地址法中的探测策略（如线性探测、二次探测等）来查找下一个空位置。 探测策略通常涉及在哈希表中按照一定的增量序列查找空闲位置。 线性探测中，增量序列为di = 1, 2, 3, ..., m-1（其中m为哈希表长度）。 二次探测中，增量序列为di = ±i^2, ±2i^2, ...（其中i为探测次数）。 插入键值对： 当找到一个空位置时，将键值对插入该位置。 查找操作 计算哈希地址： 同样使用哈希函数H(key)计算键key的哈希地址。 检查初始位置： 在哈希表中检查计算出的哈希地址对应的位置是否存储了与查询键匹配的键值对。 如果匹配，则返回对应的值。 处理冲突： 如果初始位置为空或存储的键不匹配，则使用与插入操作相同的探测策略在哈希表中查找下一个可能的位置。 逐个检查每个探测到的位置，直到找到匹配的键值对或确定表中没有该键为止。 返回结果： 如果找到匹配的键值对，则返回对应的值。 如果表中没有该键，则返回表示“未找到”的值（如None或特定错误标识）。 删除操作：在开放地址法中，删除操作需要特别小心。直接删除一个键值对可能会破坏哈希表的完整性，导致后续的查找操作出现错误。因此，通常的做法是设置一个特殊标记（如“已删除”）来表示该位置已经空闲，但并不真正移除键值对。这样可以在不影响哈希表结构的情况下支持后续的插入和查找操作。 装载因子：开放地址法的性能受装载因子（即哈希表中已存储的元素数量与哈希表总容量的比值）的影响。当装载因子过高时，哈希表的性能会下降，因为冲突的概率会增加，导致需要更多的探测次数来找到空闲位置或匹配的键值对。因此，在使用开放地址法时，需要合理地选择哈希表的大小，并适时进行扩容或缩容操作来维持合适的装载因子。

4. 注意事项：

开放地址法需要比分离链接更大的表规模，因为所有数据都需要放在同一块空间内。 当哈希表太满时，插入数据可能需要频繁的探测插入位置，这会影响性能。 总的来说，开放地址法是一种有效的哈希表冲突处理方法，通过在线性存储空间上探测其他位置来解决冲突。不同的探测方法有不同的特点和适用场景，可以根据实际需求选择适合的探测方法。

本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。 原始发表：2024-05-28，如有侵权请联系 cloudcommunity@tencent 删除前往查看存储数据数组系统性能