跳转至

哈希表

有些 STL 数据结构有很大的常数，比如 unordered_map。其实我们可以自己通过哈希表实现 unordered_map 和 unordered_set 的效果。 首先，通过 Hash 函数（比如取模）将很大的值，映射到很小的范围内（\(10^6\)），然后建 \(10^6\) 个链表。对于操作数 \(x\)，我们在编号为 \(x\%MOD\) 的链表内插入、查找和删除 \(x\)，就能实现均摊 \(O(1)\) 查找元素，实现映射的效果。

注意事项： 为防止考试时数据卡一些特定的质数，最好自己打表选几个冷门的质数。本题使用 \(10^6+3\) 就无法通过。

例题

Y227 求好元素

本题卡常，使用 unordered_set 不能通过，必须手写哈希表。

核心代码 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
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;
}