LeetCode 题解工作台
设计哈希映射
不使用任何内建的哈希表库设计一个哈希映射（HashMap）。 实现 MyHashMap 类： MyHashMap() 用空映射初始化对象 void put(int key, int value) 向 HashMap 插入一个键值对 (key, value) 。如果 key 已经存在于映射中，则更新其…
5
题型
5
代码语言
3
相关题
当前训练重点
简单 · 数组·哈希·扫描
答案摘要
直接创建一个大小为 的数组，初始时数组中的每个元素都为 ，表示哈希表中不存在该键值对。 调用 `put` 方法时，将数组中对应的位置赋值为 `value`；调用 `get` 方法时，返回数组中对应的位置的值；调用 `remove` 方法时，将数组中对应的位置赋值为 。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
不使用任何内建的哈希表库设计一个哈希映射（HashMap）。
实现 MyHashMap 类：
MyHashMap()用空映射初始化对象void put(int key, int value)向 HashMap 插入一个键值对(key, value)。如果key已经存在于映射中，则更新其对应的值value。int get(int key)返回特定的key所映射的value；如果映射中不包含key的映射，返回-1。void remove(key)如果映射中存在key的映射，则移除key和它所对应的value。
示例：
输入： ["MyHashMap", "put", "put", "get", "get", "put", "get", "remove", "get"] [[], [1, 1], [2, 2], [1], [3], [2, 1], [2], [2], [2]] 输出： [null, null, null, 1, -1, null, 1, null, -1] 解释： MyHashMap myHashMap = new MyHashMap(); myHashMap.put(1, 1); // myHashMap 现在为 [[1,1]] myHashMap.put(2, 2); // myHashMap 现在为 [[1,1], [2,2]] myHashMap.get(1); // 返回 1 ，myHashMap 现在为 [[1,1], [2,2]] myHashMap.get(3); // 返回 -1（未找到），myHashMap 现在为 [[1,1], [2,2]] myHashMap.put(2, 1); // myHashMap 现在为 [[1,1], [2,1]]（更新已有的值） myHashMap.get(2); // 返回 1 ，myHashMap 现在为 [[1,1], [2,1]] myHashMap.remove(2); // 删除键为 2 的数据，myHashMap 现在为 [[1,1]] myHashMap.get(2); // 返回 -1（未找到），myHashMap 现在为 [[1,1]]
提示：
0 <= key, value <= 106- 最多调用
104次put、get和remove方法
解题思路
方法一：静态数组实现
直接创建一个大小为 的数组，初始时数组中的每个元素都为 ，表示哈希表中不存在该键值对。
调用 put 方法时，将数组中对应的位置赋值为 value；调用 get 方法时，返回数组中对应的位置的值；调用 remove 方法时，将数组中对应的位置赋值为 。
以上操作，时间复杂度均为 。
class MyHashMap:
def __init__(self):
self.data = [-1] * 1000001
def put(self, key: int, value: int) -> None:
self.data[key] = value
def get(self, key: int) -> int:
return self.data[key]
def remove(self, key: int) -> None:
self.data[key] = -1
# Your MyHashMap object will be instantiated and called as such:
# obj = MyHashMap()
# obj.put(key,value)
# param_2 = obj.get(key)
# obj.remove(key)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity varies: naive array scanning is O(n) per operation, bucketed hashing averages O(1) per operation, and direct-indexing array is O(1). Space complexity ranges from O(n) for linked-list buckets to O(maxKey) for direct-index arrays. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Candidate discusses handling collisions explicitly with linked lists or arrays.
- question_mark
Candidate suggests hash function or modulus operation to distribute keys across buckets.
- question_mark
Candidate considers update behavior and removal edge cases carefully.
常见陷阱
外企场景- error
Forgetting to update an existing key rather than adding a duplicate entry.
- error
Not handling removal correctly, leaving stale entries in buckets.
- error
Using inefficient scanning without buckets, causing timeouts on larger input sizes.
进阶变体
外企场景- arrow_right_alt
Design HashMap with chaining using balanced BSTs instead of linked lists for buckets.
- arrow_right_alt
Implement HashMap with open addressing and linear probing to resolve collisions.
- arrow_right_alt
Create a generic HashMap supporting string keys using the same array scanning plus hash lookup pattern.