P11615 【模板】哈希表 题解

· · 题解

前言

在 THUWC2025 D1T2 中，作者的 \mathcal O(n\log n) 做法拼尽全力卡常 3h 无法战胜 n=500000 的数据。后来发现其中有一个只需查 16n 次哈希表的 subtask 都没有通过。于是有了这道题用来警示后人记得使用较为高速且不容易被卡的哈希表，同时提供一道哈希表测速题。

HACKS

这里讲一下 hack 是怎么造的以及大概原理，想要了解更多，推荐阅读深度好文 Blowing up unordered_map, and how to stop getting hacked on it。

unordered_map

unordered_map 使用的是将键值模一个质数的哈希方式，其中质数来自一个质数表 __prime_list，发现其中只有 256 个质数。

但是据说在不同的地方选的质数不一样，那不管你选啥质数了，直接造四组数据，每组数据选其中的 64 个，插入其倍数即可卡掉。

gp_hash_table/cc_hash_table

这两个比较难绷，哈希方式是模 2^{16}，所以直接造一堆模 2^{16} 同余的数即可卡掉。

如何避免被卡？

unordered_map

这个比较简单，直接把所有键值异或上一个随机数即可破坏 hack 数据的同余性质。

mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
struct Hsh{
    ull operator ()(const ull&x)const{
        static const ull r=rnd();
        return x^r;
    }
};
unordered_map<ull,ull,Hsh>f;

但是 unordered_map 还有一个缺陷就是跑得太慢，在本题要跑 2s 以上，虽然本题不卡常，但是我们总会在某个时候需要更快的哈希表。

gp_hash_table/cc_hash_table

这两个因为本来就是模 2^{16}，相当于取二进制后 16 位，所以异或一个随机数并不改变 hack 数据模 2^{16} 同余的性质。

在 CF 上的那篇文章里作者使用了 splitmix64 作为哈希函数：

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

但是这里的三个神秘数字有点难背，有什么更好记的写法吗？

有的兄弟，有的。我们直接用随机数替代神秘数字：

mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
struct Hsh{
    ull operator ()(ull x)const{
        static const ull s1=rnd(),s2=rnd(),s3=rnd();
        x+=s1;
        x=(x^(x>>33))*s2;
        x=(x^(x>>30))*s3;
        return x;
    }
};
gp_hash_table<ull,ull,Hsh>f;

实测这样和 splitmix64 效果差不多。

这样修改过的 gp_hash_table 在本题跑了 1s 左右，而 cc_hash_table 却跟 unordered_map 效率一样。

手写哈希表

有时我们需要更小的常数，这个时候就需要手写哈希表，这里就不多介绍了。

const int LEN=(1<<23);
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
struct HashMap {
    inline ull F(ull x) {
        static const ull s1=rnd(),s2=rnd(),s3=rnd();
        x+=s1;
        x=(x^(x>>33))*s2;
        x=(x^(x>>30))*s3;
        return x;
    }
    bitset<LEN+5>hav;
    ull key[LEN+5];
    ull value[LEN+5];
    int gt(const ull&x) {
        int i=F(x)&(LEN-1);
        while(hav[i]&&key[i]!=x)i=(i+1)&(LEN-1);
        hav[i]=1,key[i]=x;
        return i;
    }
    ull& operator[](const ull&x) {
        return value[gt(x)];
    }
}f;

但是我写的好像比较烂，只比 gp_hash_table 快了 100ms 左右，欢迎大家分享自己更快的哈希表！

结语

愿世界上没有卡常题。