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

2021年03月14日 11时56分

标签： LeetCode 哈希表

## 题目描述
不使用任何内建的哈希表库设计一个哈希映射（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 次 put、get 和 remove 方法

#### 来源
> 来源：力扣（LeetCode）
> 链接：[题目链接](https://leetcode-cn.com/problems/design-hashmap/ "题目链接")

## 解题思路
和昨日[设计哈希集合](http://www.vison307.com/34/ "设计哈希集合")解题思路一样，只是在结构体中由原来的值变成了一个键值对。

在这里，使用C\++ STL中的**list**容器实现**双向链表**。

## 代码
```cpp
class MyHashMap {
private:
    struct node{
        int key;
        int value;
    };
    const int MOD = 769;
    vector<list<node>> HashMap;
public:
    /** Initialize your data structure here. */
    MyHashMap() {
        HashMap.resize(MOD);
    }
    
    /** value will always be non-negative. */
    void put(int key, int value) {
        list<node>& cur = HashMap[key%MOD];
        for(list<node>::iterator it = cur.begin(); it != cur.end(); ++it){
            if(it->key == key){
                it->value = value;
                return;
            }
        }
        cur.emplace_back((node){key, value});
    }
    
    /** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */
    int get(int key) {
        list<node>& cur = HashMap[key%MOD];
        for(list<node>::iterator it = cur.begin(); it != cur.end(); ++it){
            if(it->key == key){
                return it->value;
            }
        }
        return -1;
    }
    
    /** Removes the mapping of the specified value key if this map contains a mapping for the key */
    void remove(int key) {
        list<node>& cur = HashMap[key%MOD];
        for(list<node>::iterator it = cur.begin(); it != cur.end(); ++it){
            if(it->key == key){
                cur.erase(it);
                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);
 */
```

### 用时和内存
> 执行用时：116 ms，在所有 C\++提交中击败了87.61%的用户
> 内存消耗：51.7 MB，在所有 C\++提交中击败了41.50%的用户

所有评论

暂无评论

新增评论

邮箱

邮箱仅作验证使用

图形验证码

邮箱验证码

目录

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

所有评论

暂无评论

新增评论