---
# System prepended metadata

title: 706. Design HashMap
tags: [Leetcode, python, c++, hash, easy, design]

---

###### tags: `Leetcode` `easy` `design` `hash` `python` `c++`

# 706. Design HashMap

## [題目連結:] https://leetcode.com/problems/design-hashmap/description/

## 題目:
Design a HashMap without using any built-in hash table libraries.

Implement the ```MyHashMap``` class:

* ```MyHashMap()``` initializes the object with an empty map.
* ```void put(int key, int value)``` inserts a ```(key, value)``` pair into the HashMap. If the ```key``` already exists in the map, update the corresponding ```value```.
* ```int get(int key)``` returns the ```value``` to which the specified ```key``` is mapped, or ```-1``` if this map contains no mapping for the ```key```.
* ```void remove(key)``` removes the ```key``` and its corresponding ```value``` if the map contains the mapping for the ```key```.
 
**Example 1:**
```
Input
["MyHashMap", "put", "put", "get", "get", "put", "get", "remove", "get"]
[[], [1, 1], [2, 2], [1], [3], [2, 1], [2], [2], [2]]
Output
[null, null, null, 1, -1, null, 1, null, -1]

Explanation
MyHashMap myHashMap = new MyHashMap();
myHashMap.put(1, 1); // The map is now [[1,1]]
myHashMap.put(2, 2); // The map is now [[1,1], [2,2]]
myHashMap.get(1);    // return 1, The map is now [[1,1], [2,2]]
myHashMap.get(3);    // return -1 (i.e., not found), The map is now [[1,1], [2,2]]
myHashMap.put(2, 1); // The map is now [[1,1], [2,1]] (i.e., update the existing value)
myHashMap.get(2);    // return 1, The map is now [[1,1], [2,1]]
myHashMap.remove(2); // remove the mapping for 2, The map is now [[1,1]]
myHashMap.get(2);    // return -1 (i.e., not found), The map is now [[1,1]]
```
## 解題想法:
* 題目為實作hashMap的資料結構，不能使用內建函式
* 題目最大長度為1000000:
    * 優化: 使用1000個長度為1000的數組代替
        * 二元數組
        * hashKey= (給的key%1000)
        * 實際位置=res[hashKey][給的key/1000]

## Python:
``` python=
class MyHashMap(object):

    def __init__(self):
        self.res=[[] for _ in range(1001)]

    def put(self, key, value):
        """
        :type key: int
        :type value: int
        :rtype: None
        """
        hashKey=key%1000
        if not self.res[hashKey]:
            self.res[hashKey]=[-1]*1001
        self.res[hashKey][key//1000]=value
        
    def get(self, key):
        """
        :type key: int
        :rtype: int
        """
        hashKey=key%1000
        if not self.res[hashKey]:
            return -1
        return self.res[hashKey][key//1000]

    def remove(self, key):
        """
        :type key: int
        :rtype: None
        """
        hashKey=key%1000
        if self.res[hashKey]:
            self.res[hashKey][key//1000]=-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)
```

## C++:
``` cpp=
class MyHashMap {
public:
    MyHashMap() {
        //size key Id:0~1000
        res.resize(1001, vector<int>());
    }
    
    void put(int key, int value) {
        int hashKey=key%1000;
        if (res[hashKey].empty())
            res[hashKey].resize(1001,-1);
        res[hashKey][key/1000]=value;     
    }
    
    int get(int key) {
        int hashKey=key%1000;
        if (res[hashKey].empty())
            return -1;
        return res[hashKey][key/1000];
    }
    
    void remove(int key) {
        int hashKey=key%1000;
        if (!res[hashKey].empty())
            res[hashKey][key/1000]=-1;
    }
private:
    vector<vector<int>> res;
};

/**
 * 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);
 */
```