【LeetCode】设计哈希映射

韩旭051

发布于 2020-06-23 11:22:26

2980

发布于 2020-06-23 11:22:26

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

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

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]范围内。不要使用内建的哈希库。在真实的面试中遇到过这道题？

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/design-hashmap

单纯用数组存储就可以直接过

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

看答案有老哥提供了一些适合大数据的方法

可以研究一下

class MyHashMap {
public:
    //拉链法，比用数组 省很多空间，利用hash函数 key%N  即最多N条链，相当于分类，这样其实如果分类得好，每条链都很短的
    const static int N = 20011; //%一个素数 比较好
    vector<list<pair<int, int>>> hash;
    /** Initialize your data structure here. */
    MyHashMap() {
        hash = vector<list<pair<int, int>>>(N);
    }
    list<pair<int, int>>::iterator find (int key) {
        int k = key % N; //定位到 k链
        auto it = hash[k].begin();
        for (; it != hash[k].end(); it++) {
            if (it->first == key)//存在
                break;
        }
        return it;
    }
    /** value will always be non-negative. */
    void put(int key, int value) {
        int k = key % N;
        auto it = find(key);
        //存在两种情况，一就是it就是k链的end()  即还不存在  二就是找到了
        if (it != hash[k].end())
            it->second = value;
        else 
            hash[k].push_back(make_pair(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 = key % N;
        auto it = find(key);
        //其实对于链表，我找到了it 是可以O1删除的，不过我们也可以标记它 
        if (it == hash[k].end())
            return -1;
        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 k = key % N;
        auto it = find(key);
        if (it != hash[k].end())
            hash[k].erase(it);
    }
};

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2019-12-14 ，如有侵权请联系 cloudcommunity@tencent.com 删除

网站