哈希表
unordered_map
和 unordered_set
具有很大的常数。其实我们可以自己实现一个飞快的哈希表。
| struct hash_table {
static const int MOD = 1e6 + 171;
struct Node {
int key, v, next;
} pool[N];
int nn, head[MOD];
inline hash_table() {
nn = 0;
for(int i = 0; i < MOD; i++) head[i] = 0;
}
int &insert(int key, int v) {
// assert(nn < N - 1);
pool[++nn] = {key, v, head[key % MOD]};
head[key % MOD] = nn;
return pool[nn].v;
}
bool count(int key) {
for(int i = head[key % MOD]; i; i = pool[i].next) {
if(pool[i].key == key) return true;
}
return false;
}
int &operator[](int key) {
for(int i = head[key % MOD]; i; i = pool[i].next) {
if(pool[i].key == key) return pool[i].v;
}
return insert(key, 0);
}
};
|
本题卡常,使用 unordered_set
不能通过,必须手写哈希表。
核心代码
| const int MOD = 1E6 + 171;
vector<int> mp[MOD];
void insert(int x) {
x += 2e9;
mp[x % MOD].push_back(x);
}
bool find(int x) {
x += 2e9;
int tmp = x % MOD;
for(auto i : mp[tmp]) {
if(i == x) return true;
}
return false;
}
|