Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

[LeetCode] 706. Design HashMap #706

Open
grandyang opened this issue May 30, 2019 · 0 comments
Open

[LeetCode] 706. Design HashMap #706

grandyang opened this issue May 30, 2019 · 0 comments

Comments

@grandyang
Copy link
Owner

@grandyang grandyang commented May 30, 2019

 

Design a HashMap without using any built-in hash table libraries.

To be specific, your design should include these functions:

  • put(key, value) : Insert a (key, value) pair into the HashMap. If the value already exists in the HashMap, update the value.
  • get(key): Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key.
  • remove(key) : Remove the mapping for the value key if this map contains the mapping for the key.

Example:

MyHashMap hashMap = new MyHashMap();
hashMap.put(1, 1);          
hashMap.put(2, 2);         
hashMap.get(1);            // returns 1
hashMap.get(3);            // returns -1 (not found)
hashMap.put(2, 1);          // update the existing value
hashMap.get(2);            // returns 1 
hashMap.remove(2);          // remove the mapping for 2
hashMap.get(2);            // returns -1 (not found) 

Note:

* All keys and values will be in the range of `[0, 1000000]`.
* The number of operations will be in the range of `[1, 10000]`.
* Please do not use the built-in HashMap library.

 

这道题让我们设计一个HashMap的数据结构,不能使用自带的哈希表,跟之前那道 Design HashSet 很类似,之前那道的两种解法在这里也是行得通的,既然题目中说了数字的范围不会超过 1000000,那么就申请这么大空间的数组,只需将数组的初始化值改为 -1 即可。空间足够大了,就可以直接建立映射,移除时就将映射值重置为 -1,由于默认值是 -1,所以获取映射值就可以直接去,参见代码如下:

 

解法一:

class MyHashMap {
public:
    MyHashMap() {
        data.resize(1000000, -1);
    }
    void put(int key, int value) {
        data[key] = value;
    }
    int get(int key) {
        return data[key];
    }
    void remove(int key) {
        data[key] = -1;
    }

private:
    vector<int> data;
};

 

我们可以来适度的优化一下空间复杂度,由于存入 HashMap 的映射对儿也许不会跨度很大,那么直接就申请长度为 1000000 的数组可能会有些浪费,其实可以使用 1000 个长度为 1000 的数组来代替,那么就要用个二维数组啦,实际上开始只申请了 1000 个空数组,对于每个要处理的元素,首先对 1000 取余,得到的值就当作哈希值,对应申请的那 1000 个空数组的位置,在建立映射时,一旦计算出了哈希值,将对应的空数组 resize 为长度 1000,然后根据哈希值和 key/1000 来确定具体的加入映射值的位置。获取映射值时,计算出哈希值,若对应的数组不为空,直接返回对应的位置上的值。移除映射值一样的,先计算出哈希值,如果对应的数组不为空的话,找到对应的位置并重置为 -1。参见代码如下:

 

解法二:

class MyHashMap {
public:
    MyHashMap() {
        data.resize(1000, vector<int>());
    }
    void put(int key, int value) {
        int hashKey = key % 1000;
        if (data[hashKey].empty()) {
            data[hashKey].resize(1000, -1);
        } 
        data[hashKey][key / 1000] = value;
    }
    int get(int key) {
        int hashKey = key % 1000;
        if (!data[hashKey].empty()) {
            return data[hashKey][key / 1000];
        } 
        return -1;
    }
    void remove(int key) {
        int hashKey = key % 1000;
        if (!data[hashKey].empty()) {
            data[hashKey][key / 1000] = -1;
        } 
    }

private:
    vector<vector<int>> data;
};

 

Github 同步地址:

#706

 

类似题目:

Design HashSet

 

参考资料:

https://leetcode.com/problems/design-hashmap

https://leetcode.com/problems/design-hashmap/discuss/152746/Java-Solution

https://leetcode.com/problems/design-hashmap/discuss/184764/Easy-C%2B%2B-Solution-beats-98.01(52-msec)-using-array-of-vectors

 

LeetCode All in One 题目讲解汇总(持续更新中...)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
1 participant
You can’t perform that action at this time.