【2024.04.15】LeetCode每日一题·设计哈希映射

2024年04月15日 14时03分

标签： LeetCode 哈希表 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^6
最多调用 10^4 次 add、remove 和 contains
````

#### 来源

> 来源：力扣（LeetCode）
> 
> 链接：[706. 设计哈希映射](https://leetcode.cn/problems/design-hashmap/description/)

## 解题思路
思路和[705. 设计哈希集合](https://www.vison307.cn/109/)一致，只不过这里链地址法中每一个节点存储的不再是单一的值`key`，而是一个键值对`(key, value)`，键值对使用结构体自行实现或者使用STL中的`pair<int, int>`均可。

## 代码
````cpp
struct P{
    int key;
    int value;
    P(int key, int value){
        this->key = key;
        this->value = value;
    }
};

class MyHashMap {
private:
    vector<list<P>> hashmap;
    const int MOD = 10007;

public:
    MyHashMap() {
        hashmap.resize(MOD);
    }
    
    void put(int key, int value) {
        int idx = key % MOD;
        list<P>& l = hashmap[idx];
        for(auto iter = l.begin(); iter != l.end(); iter++){
            int k = iter->key;
            if(k == key){
                iter->value = value;
                return;
            }
        }
        l.push_back(P(key, value));
    }
    
    int get(int key) {
        int idx = key % MOD;
        list<P>& l = hashmap[idx];
        for(auto iter = l.begin(); iter != l.end(); iter++){
            int k = iter->key;
            if(k == key){
                return iter->value;
            }
        }
        return -1;
    }
    
    void remove(int key) {
        int idx = key % MOD;
        list<P>& l = hashmap[idx];
        for(auto iter = l.begin(); iter != l.end(); iter++){
            int k = iter->key;
            if(k == key){
                l.erase(iter);
                return;
            }
        }
    }
};

/**
 * Your MyHashMap object will be instantiated and called as such:
 * MyHashMap* obj = new MyHashMap();
 * obj->put(key,value);
 * int param_2 = obj->get(key);
 * obj->remove(key);
 */
````

### 用时和内存
> 执行用时：103 ms，在所有C++提交中击败了64.26%的用户
>
> 内存消耗：64.51 MB，在所有C++提交中击败25.56%的用户
>

所有评论

暂无评论

新增评论

邮箱

邮箱仅作验证使用

图形验证码

邮箱验证码

目录

【2024.04.15】LeetCode每日一题·设计哈希映射

所有评论

暂无评论

新增评论