哈希表的冲突解决策略：线性探测法（Linear Probing） 一、问题描述 哈希表是一种通过哈希函数将键映射到数组索引的数据结构，但在实际应用中，不同的键可能映射到相同的索引位置，这种现象称为"哈希冲突"。线性探测法是开放定址法（Open Addressing）中最基础的冲突解决策略，其核心思想是：当发生冲突时，系统按顺序检查哈希表中的下一个槽位（通常是下一个相邻位置），直到找到一个空槽位来存放待插入的键值对。 二、线性探测法的基本原理 哈希函数 ：首先使用哈希函数计算键的初始索引位置，即 index = hash(key) % table_size 。 冲突处理 ：如果该位置已被占用（且键不同），则线性地检查下一个位置 (index + 1) % table_size ，若仍被占用，继续检查 (index + 2) % table_size ，以此类推，直到找到空槽或遍历整个表。 查找操作 ：查找时，从初始索引开始线性探测，直到遇到目标键（成功）或空槽（失败）。注意：遇到空槽才停止，因为被删除的键可能留下"墓碑"标记（后续说明）。 删除操作 ：直接删除键值对会导致查找链断裂（后续键无法被探测到），因此通常用特殊标记（如"墓碑"）替代实际删除，标记此槽位可被新键覆盖，但查找时需跳过。 三、操作步骤详解 插入流程 ： 计算初始索引 i = hash(key) % size 。 从索引 i 开始，逐个检查槽位： 若槽位为空或标记为"墓碑"，插入键值对。 若槽位键与待插入键相同，更新值（若允许重复键则另处理）。 若槽位被其他键占用，继续检查 (i + 1) % size 。 若表已满，需扩容并重新哈希所有键值对。 查找流程 ： 计算初始索引 i = hash(key) % size 。 从 i 开始线性探测，遇到目标键则返回对应值；遇到空槽（非墓碑）则说明键不存在；若遍历整个表未找到，同样返回失败。 删除流程 ： 先执行查找操作定位键所在槽位。 将该槽位标记为"墓碑"（而非直接置空），保留查找链的连续性。 四、性能分析 优点 ： 实现简单，无需额外数据结构（如链地址法中的链表）。 数据局部性好，缓存命中率较高（连续探测相邻内存位置）。 缺点 ： 聚集现象 ：连续被占用的槽位形成"主聚集"（初始冲突键扎堆）或"次聚集"（不同初始索引的键争夺同一区域），导致探测路径变长。 负载因子（已用槽位比例）需控制在较低水平（通常 < 0.7），否则性能急剧下降。 删除操作需特殊处理，增加复杂度。 五、优化策略 二次探测 ：避免线性探测的聚集问题，按平方步长跳跃检查（如 index + 1², index + 2² ）。 双重哈希 ：使用第二个哈希函数计算步长，进一步减少聚集。 动态扩容 ：当负载因子超过阈值时，扩容哈希表并重新分布键值对。 六、示例说明 假设哈希表大小为 7，哈希函数为 hash(key) = key % 7 ，依次插入键 [10, 20, 30, 40] ： 插入 10： 10 % 7 = 3 → 槽位 3 为空，直接插入。 插入 20： 20 % 7 = 6 → 槽位 6 为空，直接插入。 插入 30： 30 % 7 = 2 → 槽位 2 为空，直接插入。 插入 40： 40 % 7 = 5 → 槽位 5 为空，直接插入。 此时表状态为 [-, -, 30, 10, -, 40, 20] （ - 表示空）。若再插入 17（ 17 % 7 = 3 ）： 槽位 3 已被 10 占用 → 探测槽位 4（空），插入成功。 线性探测法通过简单的"顺序找空位"策略解决了哈希冲突，但需注意聚集问题和删除处理，在实际应用中需结合负载因子控制与扩容机制保证效率。