哈希算法题目：设计一个哈希映射，使用开放地址法（线性探测）解决冲突

字数 1564 2025-11-08 23:00:34

哈希算法题目：设计一个哈希映射，使用开放地址法（线性探测）解决冲突

题目描述

设计一个哈希映射（HashMap），支持以下操作：

put(key, value)：插入键值对。若键已存在，则更新对应的值。
get(key)：返回键对应的值；若键不存在，返回 -1。
remove(key)：删除键值对。

要求：

使用开放地址法（线性探测）解决哈希冲突。
哈希表需支持动态扩容（当负载因子超过阈值时，容量翻倍）。
假设键和值均为非负整数（简化问题）。

解题步骤

步骤1：理解开放地址法

开放地址法的核心思想是：当发生哈希冲突时，按某种规则（如线性探测）在哈希表中寻找下一个空闲位置。

线性探测：若当前位置 index 被占用，则依次检查 index+1, index+2, ... 直到找到空位。
查找和删除时需遵循相同的探测规则。

步骤2：设计数据结构

定义两个数组：
- keys[]：存储键。
- values[]：存储值。
- 初始容量设为 INIT_CAPACITY（例如 16）。
定义负载因子 LOAD_FACTOR（例如 0.75），当 元素数量 ≥ 容量 × 负载因子 时触发扩容。
特殊标记 DELETED（例如 -1）表示已删除的槽位，避免查找中断。

步骤3：哈希函数

使用简单的取模哈希：

hash(key) = key % capacity

步骤4：实现 `put` 操作

计算初始索引 index = key % capacity。
从 index 开始线性探测：
- 若遇到空槽（值为 null 或 DELETED），插入键值对。
- 若遇到相同键，更新值。
插入后检查负载因子，触发扩容若需。

细节：

需跳过 DELETED 标记的槽位，但允许在 DELETED 位置插入新键。
扩容时需重新插入所有有效键值对（因哈希函数依赖容量）。

步骤5：实现 `get` 操作

计算 index = key % capacity。
从 index 开始线性探测，直到遇到空槽（非 DELETED）停止：
- 若找到键，返回值。
- 若遇到空槽（从未使用过），说明键不存在。

步骤6：实现 `remove` 操作

类似 get 操作找到键所在位置。
将对应槽位的键标记为 DELETED，值设为 -1（避免影响后续探测）。

步骤7：动态扩容

当 size ≥ capacity × LOAD_FACTOR 时：
- 新容量 = 旧容量 × 2。
- 创建新数组 newKeys[] 和 newValues[]。
- 遍历旧数组，将有效键值对重新插入新数组（忽略 DELETED）。

关键问题与解决方案

删除操作导致查找中断：
- 使用 DELETED 标记已删除位置，查找时跳过但插入时可复用。
扩容的重新哈希：
- 因 hash(key) 依赖容量，必须重新计算每个键的位置。
线性探测的聚集问题：
- 线性探测可能导致连续占用槽位，降低性能。可考虑二次探测或双重哈希（本题要求线性探测）。

示例演示

假设初始容量为 4，插入以下键值对：

put(1, 10) → 索引 1：插入 (1,10)。
put(5, 20) → 索引 1 冲突，探测索引 2：插入 (5,20)。
get(5) → 索引 1 找到键 1（不匹配），索引 2 找到键 5，返回 20。
remove(1) → 索引 1 标记为 DELETED。
put(9, 30) → 索引 1 为 DELETED，直接插入 (9,30)。

总结

开放地址法通过线性探测解决冲突，节省指针空间但需处理删除标记和扩容。动态扩容保证效率，删除标记避免断链。实际应用中需权衡负载因子以平衡空间和性能。

哈希算法题目：设计一个哈希映射，使用开放地址法（线性探测）解决冲突题目描述设计一个哈希映射（HashMap），支持以下操作： put(key, value) ：插入键值对。若键已存在，则更新对应的值。 get(key) ：返回键对应的值；若键不存在，返回 -1 。 remove(key) ：删除键值对。要求：使用开放地址法（线性探测）解决哈希冲突。哈希表需支持动态扩容（当负载因子超过阈值时，容量翻倍）。假设键和值均为非负整数（简化问题）。解题步骤步骤1：理解开放地址法开放地址法的核心思想是：当发生哈希冲突时，按某种规则（如线性探测）在哈希表中寻找下一个空闲位置。线性探测：若当前位置 index 被占用，则依次检查 index+1, index+2, ... 直到找到空位。查找和删除时需遵循相同的探测规则。步骤2：设计数据结构定义两个数组： keys[] ：存储键。 values[] ：存储值。初始容量设为 INIT_CAPACITY （例如 16）。定义负载因子 LOAD_FACTOR （例如 0.75），当元素数量 ≥ 容量 × 负载因子时触发扩容。特殊标记 DELETED （例如 -1 ）表示已删除的槽位，避免查找中断。步骤3：哈希函数使用简单的取模哈希：步骤4：实现 put 操作计算初始索引 index = key % capacity 。从 index 开始线性探测：若遇到空槽（值为 null 或 DELETED ），插入键值对。若遇到相同键，更新值。插入后检查负载因子，触发扩容若需。细节：需跳过 DELETED 标记的槽位，但允许在 DELETED 位置插入新键。扩容时需重新插入所有有效键值对（因哈希函数依赖容量）。步骤5：实现 get 操作计算 index = key % capacity 。从 index 开始线性探测，直到遇到空槽（非 DELETED ）停止：若找到键，返回值。若遇到空槽（从未使用过），说明键不存在。步骤6：实现 remove 操作类似 get 操作找到键所在位置。将对应槽位的键标记为 DELETED ，值设为 -1 （避免影响后续探测）。步骤7：动态扩容当 size ≥ capacity × LOAD_FACTOR 时：新容量 = 旧容量 × 2。创建新数组 newKeys[] 和 newValues[] 。遍历旧数组，将有效键值对重新插入新数组（忽略 DELETED ）。关键问题与解决方案删除操作导致查找中断：使用 DELETED 标记已删除位置，查找时跳过但插入时可复用。扩容的重新哈希：因 hash(key) 依赖容量，必须重新计算每个键的位置。线性探测的聚集问题：线性探测可能导致连续占用槽位，降低性能。可考虑二次探测或双重哈希（本题要求线性探测）。示例演示假设初始容量为 4，插入以下键值对： put(1, 10) → 索引 1：插入 (1,10) 。 put(5, 20) → 索引 1 冲突，探测索引 2：插入 (5,20) 。 get(5) → 索引 1 找到键 1（不匹配），索引 2 找到键 5，返回 20。 remove(1) → 索引 1 标记为 DELETED 。 put(9, 30) → 索引 1 为 DELETED ，直接插入 (9,30) 。总结开放地址法通过线性探测解决冲突，节省指针空间但需处理删除标记和扩容。动态扩容保证效率，删除标记避免断链。实际应用中需权衡负载因子以平衡空间和性能。