设计哈希映射

难度: Easy

不使用任何内建的哈希表库设计一个哈希映射（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 <= 10⁶
最多调用 10⁴ 次 put、get 和 remove 方法

Submission

运行时间: 105 ms

内存: 19.4 MB

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

Explain

该题解使用了一个非常直接的方法来实现哈希映射。它利用一个固定大小（1000001）的数组来存储键值对。数组的索引代表键（key），数组的值代表对应的值（value）。这种方法的优点在于其简单性和直接性，对于操作如插入、查找和删除，都可以直接通过数组索引来完成，从而实现快速的访问和修改。

时间复杂度: O(1)

空间复杂度: O(N)

class MyHashMap:
    def __init__(self):
        # 初始化一个固定大小的数组，所有值设为-1表示空
        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:
        # 将键对应的数组索引位置的值设为-1表示删除
        self.data[key] = -1

Explore

数组大小选择为1000001是一种预设的设计决策，主要基于实现简便性和避免冲突。1000001是一个大于一百万的素数，使用素数作为数组长度可以在某种程度上减少哈希冲突的可能性，尤其是在哈希函数设计得较为简单时。此外，选择一个稍大于常用范围的数可以确保覆盖大多数实际应用中的键值需求。

在当前实现中，由于直接使用键作为数组索引，理论上不会出现冲突——每个键直接映射到一个固定的数组位置。然而，在更一般的哈希表实现中，如使用模运算的哈希函数，键值冲突是常见的问题。常见的解决冲突的策略包括链地址法（使用链表处理冲突的索引）和开放寻址法（找到空闲的数组位置）。当前问题的实现方法实际上避免了冲突的可能性，前提是键值的范围必须严格控制在数组的索引范围之内。

在这个设计中，使用-1来表示数组位置为空（即没有存储任何键值对的状态）。这种设计确实会带来一个问题：如果要存储值为-1的键值对，则无法区分这个位置是真的存储了值为-1的键值对，还是该位置为空。解决这个问题的一种方法是使用更复杂的数据结构来存储每个位置的状态，例如每个数组项可以是一个更丰富的对象或者结构体，包含值和一个表示该位置是否被占用的标志。