题目描述

不使用任何内建的哈希表库设计一个哈希映射

具体地说，你的设计应该包含以下的功能

• put(key, value)：向哈希映射中插入(键,值)的数值对。如果键对应的值已经存在，更新这个值。
• get(key)：返回给定的键所对应的值，如果映射中不包含这个键，返回-1。
• remove(key)：如果映射中存在这个键，删除这个数值对。

样例

MyHashMap hashMap = new MyHashMap();
hashMap.put(1, 1);          
hashMap.put(2, 2);         
hashMap.get(1);            // 返回 1
hashMap.get(3);            // 返回 -1 (未找到)
hashMap.put(2, 1);         // 更新已有的值
hashMap.get(2);            // 返回 1 
hashMap.remove(2);         // 删除键为2的数据
hashMap.get(2);            // 返回 -1 (未找到) 

注意

• 所有的值都在 [1, 1000000]的范围内。
• 操作的总数目在[1, 10000]范围内。
• 不要使用内建的哈希库。

算法1

(开地址法) $O(1)$

一般解决哈希值冲突有两种方法，一种是开地址法 (Open Addressing)，另一种是拉链法 (Chaining)。这里先介绍开地址法，在开地址法中我们使用探查 (Probing) 来解决冲突，即在哈希值映射的位置后按照某种顺序来查找其他可能的位置，直到找到key或者遇到空位置为止，当我们遇到空位置时说明哈希表里不存在当前key。而一般我们常用的探查方式是线性探查法 (Linear Probing)，即依次遍历哈希位置之后的每个位置。

以上是对于插入和查找而言，而对于删除我们有两种不同的删除策略：

1. 第一种是懒删除 (Lazy Deletion)，即我们找到要删除的key后把当前位置标记成非空但未使用，这里标记成非空是防止在该位置之后的键值对无法被查找到，回想到我们查找的时候遇到空位置就停止了，同时我们应该还把该位置标记成未被使用过，使得之后我们可以在该位置重新插入新的键值对。这种策略会减慢之后我们搜索键值对的速度。
2. 第二种是立即删除 (Eager Deletion)，当我们删除某个键值对后，为了能让该位置之后的键值对还能被查找到，我们需要将它们移动到空位上，即不断的向前移。那么我们需要移动哪些键值对呢？这个过程可以递归的描述：假如我们删除的位置是i，那么我们设j = i + 1，让j不断的往后找，假如当前j位置的哈希值hash[key]不在[i + 1, j]这个范围中，说明他要么是被映射到了i之前的位置然后因为冲突被安排到了这里，要么是被映射到了j之后的位置也是因为冲突被安排到了这里。所以我们可以把当前键值对移动到被删除的位置i来减少下次它被查找的时间，相当于把它的冲突队列的位置给向前移了。移动完当前键值对后，当前位置j就成了新的被删除的位置，我们递归的往下进行直到遇到空位置为止。这种策略虽然在删除的时候多了一些操作，但可以加快我们之后搜索的速度。

时间复杂度

根据研究，采用线性探查法对于搜索操作而言，平均复杂度为 $O(1)$，即常数。虽然对于某些key而言最坏情况下复杂度可能会达到 $O(\log n)$，不过这种情况很难达到。

另外这里给出当负载因子 (load factor) 为 $\alpha$ 时，搜索操作的期望时间估计公式：

• 一次成功的搜索：$\frac{1}{2}(1 + \frac{1}{1 - \alpha})$
• 一次失败的搜索：$\frac{1}{2}(1 + \frac{1}{(1 - \alpha)^2})$

C++ 代码 (Lazy Deletion)

class MyHashMap {
public:
    /** Initialize your data structure here. */
    int N = 20011;
    vector<pair<int, int>> hash;
    MyHashMap() {
        hash = vector<pair<int, int>>(N, {-1, -1});
    }

    int find(int key)
    {
        int t = key % N;
        while (hash[t].first != -1 && hash[t].first != key)
            t = (t + 1) % N;
        return t;
    }
    /** value will always be non-negative. */
    void put(int key, int value) {
        int k = key % N;
        while (hash[k].first != -1 && hash[k].first != key && hash[k].first != -2)
            k = (k + 1) % N;
        hash[k] = {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) {
        int k = find(key);
        return hash[k].second;
    }


    /** Removes the mapping of the specified value key if this map contains a mapping for the key */
    void remove(int key) {
        int k = find(key);
        hash[k].first = -2;
    }
};

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

C++ 代码 (Eager Deletion)

class MyHashMap {
public:
    /** Initialize your data structure here. */
    int N = 20011;
    vector<pair<int, int>> hash;
    MyHashMap() {
        hash = vector<pair<int, int>>(N, {-1, -1});
    }

    int find(int key)
    {
        int t = key % N;
        while (hash[t].first != -1 && hash[t].first != key)
            t = (t + 1) % N;
        return t;
    }
    /** value will always be non-negative. */
    void put(int key, int value) {
        int k = find(key);
        hash[k] = {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) {
        int k = find(key);
        return hash[k].second;
    }


    /** Removes the mapping of the specified value key if this map contains a mapping for the key */
    void remove(int key) {
        int k = find(key);
        if (hash[k].first == -1) return;
        for (int j = (k + 1) % N; hash[j].first != -1; j = (j + 1) % N)
        {
            if (hash[j].first % N <= k || hash[j].first % N > j)
            {
                hash[k] = hash[j];
                k = j;
            }
        }
        hash[k] = {-1, -1};
    }
};

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

算法2

(拉链法) $O(1)$

拉链法就是每个位置看成一个链表，每个链表节点包含一个键值对，注意这里要用双链表方便删除，我们直接使用C++ STL里的双向链表list来省去自定义链表节点的麻烦。

时间复杂度

对于拉链法而言，如果哈希函数是满足随机哈希函数要求的，即对于每个key，hash[key]是在数组索引范围内均匀分布的，并且对于任意两个不同的key，它们的哈希值是独立的。那么每个操作的期望时间是 $O(1 + \alpha)$。在最坏情况下，一次搜索可能需要 $O(\frac{\log n}{\log \log n})$的时间

C++ 代码

class MyHashMap {
public:
    /** Initialize your data structure here. */
    const static int N = 20011;
    vector<list<pair<int, int>>> hash;
    MyHashMap() {
        hash.resize(N);
    }

    list<pair<int, int>>::iterator find(list<pair<int, int>>& l, int key)
    {
        auto it = l.begin();
        while (it != l.end() && it->first != key) it ++ ;
        return it;
    }

    /** value will always be non-negative. */
    void put(int key, int value) {
        int t = key % N;
        auto it = find(hash[t], key);
        if (it == hash[t].end()) hash[t].push_back({key, value});
        else *it = {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) {
        int t = key % N;
        auto it = find(hash[t], key);
        if (it == hash[t].end()) return -1;
        else return it->second;
    }

    /** Removes the mapping of the specified value key if this map contains a mapping for the key */
    void remove(int key) {
        int t = key % N;
        auto it = find(hash[t], key);
        if (it != hash[t].end()) hash[t].erase(it);
    }
};

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