1+ /*
2+ Design a HashMap without using any built-in hash table libraries.
3+
4+ Designing a hash table using the chaining method, where a vector holds a list of pairs representing the key-value mappings.
5+
6+ Time: O(n)
7+ Space: O(n)
8+ */
9+
10+ class MyHashMap {
11+ public:
12+ const int N =10010 ;
13+ vector<list<pair<int ,int >>> h;
14+
15+ /* * Initialize your data structure here.*/
16+ MyHashMap () {
17+ h = vector<list<pair<int ,int >>>(N);
18+ }
19+
20+ list<pair<int ,int >>::iteratorfind (int key) {
21+ int t = key % N;
22+ for (auto it = h[t].begin (); it != h[t].end (); it ++ ) {
23+ if (it->first == key)
24+ return it;
25+ }
26+ return h[t].end ();
27+ }
28+
29+ /* * value will always be non-negative.*/
30+ void put (int key,int value) {
31+ auto t = key % N;
32+ auto it =find (key);
33+ if (it == h[t].end ()) h[t].push_back ({key, value});
34+ else it->second = value;
35+ }
36+
37+ /* * Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key*/
38+ int get (int key) {
39+ auto t = key % N;
40+ auto it =find (key);
41+ if (it != h[t].end ())return it->second ;
42+ return -1 ;
43+ }
44+
45+ /* * Removes the mapping of the specified value key if this map contains a mapping for the key*/
46+ void remove (int key) {
47+ auto t = key % N;
48+ auto it =find (key);
49+ if (it != h[t].end ()) h[t].erase (it);
50+ }
51+ };
52+
53+ /* *
54+ * Your MyHashMap object will be instantiated and called as such:
55+ * MyHashMap* obj = new MyHashMap();
56+ * obj->put(key,value);
57+ * int param_2 = obj->get(key);
58+ * obj->remove(key);
59+ */