题目

设计一个hashmap，要求有以下methods

• put(key, value): 放置一个key-value对
• get(key): 取得key键所对应的值
• remove(key): 删除key键所对应的值

简单方法

可以使用一个数组作为hashmap，数组的位置当作key，数组某一个元素的值当作value，这是比较简单也很容易理解的方法，代码如下：

class MyHashMap {
public:
    /** Initialize your data structure here. */
    MyHashMap() {
        memset(hashMap, -1, 1000000);
    }
    
    /** value will always be non-negative. */
    void put(int key, int value) {
        hashMap[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) {
        return hashMap[key];
    }
    
    /** Removes the mapping of the specified value key if this map contains a mapping for the key */
    void remove(int key) {
        hashMap[key] = -1;
    }
private:
    int hashMap[1000000]; // 使用数组作为hashmap
};

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

高级方法

至少在我现在的知识范围内属于高级方法。
思想：题目中键值对的数量是100万个，但是构造一个长度100万的数组非常浪费内存，所以我们构造一个长度为20007的数组来作为键值对，具体为，一个长度为20007的键数组，一个长度为20007的值数组。

• find(): find函数非常重要，在这种方法中，可能会出现两个key对应同一个基本key的情况，也就是多对一，但一个键值对的位置只能存放一个键值对，所以如果出现重复，可以采取往后延的方法，直到找到一个空的键值对位置，将数据存入。

class MyHashMap {
public:
    /** Initialize your data structure here. */
    MyHashMap() {
        memset(hashKey, -1, sizeof(hashKey));
    }
    
    /** Find the right place for a new key */
    int find(int key) {
        int p = key % N;
    
        while(hashKey[p] != key && hashKey[p] != -1) {
            p = (p + 1) % N;
        }
        return p;
    }
    
    /** value will always be non-negative. */
    void put(int key, int value) {
        int p = find(key);
        hashKey[p] = key;
        hashValue[p] = 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) {
        int p = find(key);
        if (hashKey[p] == -1) {
            return -1;
        } else {
            return hashValue[p];
        }
    }
    
    /** Removes the mapping of the specified value key if this map contains a mapping for the key */
    void remove(int key) {
        int p = find(key);
        if (hashKey[p] != -1) {
            hashKey[p] = -2;
        }
    }
private:
    const static int N = 20007;
    int hashKey[N];
    int hashValue[N];
};

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

• 关于N：如果N过小，将会在“延后”这一步上耽误太多的时间，即程序为新的键值对找到位置将会耽误大量的时间，而N过大则会占用太多的内存，所以将N设置在20007（这个方法的作者将其设置为20007，我也不清楚为什么是20007这个数，我只能定性分析，或许定量分析会算出20007这个数字）
• 在remove()函数里有一句hashKey[p] = -2，这是为了表示这个地方曾经存过数据，不管删没删掉，都要有个痕迹，不能跟新的一样，这样才会正确找到每一个数据的位置，否则会出现错误。