手把手带你手撕HashMap

HashMap的优缺点

优点

• 增删查找时间复杂度o(1)

缺点

• key不能重复，在数据很多相同的时候不适合
• 里面的内容是随机的不是有序的，所以面对有序的处理不行，比如说顺序输出
• 还有就是要知道数组开辟的大小，如果开辟小了，hash冲突的很严重那么链表查询的时候时间就会增加，这时候就要扩容，那么里面所有的hash都需要重新进行hash存储了

怎么解决hash冲突

• 开放地址法 （冲突了往下找）
• 链表法 （数组里面放的是链表，这也是我们手撕的）
• 公共溢出区法
• 再hash法（就是在hash一次）

手撕hashmap

其实就是里面有一个数组(指针数组)，里面放的是双向链表，双向链表里面放的是一个pair,pair里放的是key,value，单向的也可以(单向的删除要找的是删除元素的上一个，双向的找对应的就好)

class MyHashMap {
public:

   static int hsah(int key) {
        return key%size;
    }

    /** Initialize your data structure here. */
    MyHashMap():mymap_(size) {
    }
    
    /** value will always be non-negative. */
    void put(int key, int value) {
        int index = hsah(key);
        // cout<<"put"<<endl;
        // cout<<"index: "<<index<<endl;
        auto iter = mymap_[index].begin();
        while(iter!=mymap_[index].end()) {
            if(iter->first==key) {
                iter->second=value;
                return;
            }
            iter++;
        }
        mymap_[index].insert(mymap_[index].end(),{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) {
        // cout<<"get: "<<key<<endl;

        int index = hsah(key);
        // for(auto i = mymap_[index].begin();i!=mymap_[index].end();i++) {
        //     cout<<i->first<<" "<<i->second<<" | ";
        // }
        // cout<<endl;

        auto iter = mymap_[index].begin();
        for(;iter!=mymap_[index].end();iter++) {
            if(iter->first==key) {
                return iter->second;
            }
        }
        return -1;

    }
    
    /** Removes the mapping of the specified value key if this map contains a mapping for the key */
    void remove(int key) {
        // cout<<"remove"<<endl;

        int index = hsah(key);
        for( auto iter = mymap_[index].begin();iter!=mymap_[index].end();iter++) {
            if(iter->first==key) {
                iter=mymap_[index].erase(iter); // 后面的迭代器虽然不会失效但是不能用++了
                // iter--;
                return;
            }
        }
    }


private:
    vector<list<pair<int,int>>> mymap_;
    static const int size = 572;


};

/**
 * 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);
 */
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76