-
Notifications
You must be signed in to change notification settings - Fork 108
/
HashMap.cpp
76 lines (61 loc) · 1.77 KB
/
HashMap.cpp
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
#include <bits/stdtr1c++.h>
#define clr(ar) memset(ar, 0, sizeof(ar))
#define read() freopen("lol.txt", "r", stdin)
#define dbg(x) cout << #x << " = " << x << endl
#define ran(a, b) ((((rand() << 15) ^ rand()) % ((b) - (a) + 1)) + (a))
using namespace std;
struct hashmap{
int t, sz, hmod;
vector <int> id;
vector <long long> key, val;
inline int nextPrime(int n){
for (int i = n; ;i++){
for (int j = 2; ;j++){
if ((j * j) > i) return i;
if ((i % j) == 0) break;
}
}
return -1;
}
void clear(){t++;}
inline int pos(unsigned long long x){
int i = x % hmod;
while (id[i] == t && key[i] != x) i++;
return i;
}
inline void insert(long long x, long long v){
int i = pos(x);
if (id[i] != t) sz++;
key[i] = x, val[i] = v, id[i] = t;
}
inline void erase(long long x){
int i = pos(x);
if (id[i] == t) key[i] = 0, val[i] = 0, id[i] = 0, sz--;
}
inline long long find(long long x){
int i = pos(x);
return (id[i] != t) ? -1 : val[i];
}
inline bool contains(long long x){
int i = pos(x);
return (id[i] == t);
}
inline void add(long long x, long long v){
int i = pos(x);
(id[i] == t) ? (val[i] += v) : (key[i] = x, val[i] = v, id[i] = t, sz++);
}
inline int size(){
return sz;
}
hashmap(){}
hashmap(int m){
srand(time(0));
m = (m << 1) - ran(1, m);
hmod = nextPrime(max(100, m));
sz = 0, t = 1;
id.resize(hmod + 0x1FF, 0);
key.resize(hmod + 0x1FF, 0), val.resize(hmod + 0x1FF, 0);
}
};
int main(){
}