前段时间博客迁移图片炸了已补图

以下为原文

这是啥？

我们知道，在c++11中出现了一些有用的容器，其中包括了两（三）个非常实用的容器：unordered_map & unordered_set / unordered_multiset

其实现的操作与map&set/multiset 差不多，只是我们知道map和set实现的是O(logn) 进行实现一个映射，其中内置的实现是红黑树。 多数时候已经非常优秀了，但是往往会有一些题用不到有序的序列（我们知道set内部是有序的），反而需要更快的速度。这个时候 可以选择自己打hash。但是对于yijan这种懒癌晚期患者自然想要实用 unordered_map & unordered_multiset 实现 O(1) 查询。

如果你会使用，可以直接跳过这部分

首先是定义。如果在c++11环境下，可以很方便写出来：

#include<unordered_set>
#include<unordered_map>
#include<iostream>
using namespace std;
unordered_set<int> S1;
unordered_multiset<int> S2;
unordered_map<int,int> M;
int main(){
    S1.insert(6);
    S2.insert(7);
    M[233333] = 666666;
    cout << M[233333];
}

但是我们NOIP系列竞赛显然是不滋瓷c++11 的！怎么办？

那自然是有奇技淫巧的！：（据说是没有问题的）

#include<tr1/unordered_set>
#include<tr1/unordered_map>
#include<iostream>
using namespace std;
using namespace tr1;
unordered_set<int> S1;
unordered_multiset<int> S2;
unordered_map<int,int> M;
int main(){
    S1.insert(6);
    S2.insert(7);
    M[233333] = 666666;
    cout << M[233333];
}

然后就可以在非11环境用了！（比如luoguide 选择c++不选11就能跑！）

好了，说了那么多，下面进入正题（（

下面我们要！ 卡掉 unordered_map ！

但是说的简单，如何卡掉？首先我们知道，只要是hash函数，如果多次碰撞，自然速度O(n) -> O(n^2)

如果对探索过程不敏感可以跳过这一段

首先，让我们去unorderedmap的源文件：On github

我们得知道这个东西的实现原理，里面我们可以看到这一句话，这个hashtable 显然调用了 _Mod_range_Hashing 和 _Prime_rehash_policy从这里我们就可以大概知道这个东西的实现过程：首先hash这个数据，然后对这个hash值取模放入unordered_map。

对_Prime_rehash_policy的探索（hashtable_c++0x.cc）我们可以发现一个数组：__prime_list。并且此时你又可以摸清其中的一部分实现：当这个map过大的时候，它就会resize其本身。当抛开这个我们先把这个质数表找到。

然后呢 打开了（ hashtable-aux.cc）里面就可以看到这个数组了！

好了，我们现在找到了这个数组，以及掌握了基本实现。但是我们还是应当搞清楚内置hash实现是什么。事实上是使用了std::hash在cppreference里写到：

无序关联容器 std::unordered_set 、 std::unordered_multiset 、 std::unordered_map 、 std::unordered_multimap 以该模板 std::hash 的特化为默认哈希函数。

到这里，我们就可以卡掉它了。并不是所有的质数都能做到这一点，而只有特殊的一两个。由于博主实在懒得花时间去寻找这个质数，下面引用cf博文一句话：

for gcc 6 or earlier, 126271 does the job, and for gcc 7 or later, 107897 will work.

我们现在使用的编译器多位6or earlier 所以 126271 是一个非常合适的质数。

真正卡掉一个代码

luogu有一个题P1102 A-B数对这是一个普通map都能ac的水题。我们来对比一下unordered_set & unordered_map

这是份AC代码：

然后下图中，上面的是采用map，下面的采用unordered_map

可以看到，无论空间和时间都是unordered后优秀。

Hack It！

我们用前面说过的那个卡掉代码的质数来做输入文件。输入的数字为126271的1～200000倍。然后分别使用map和unordered_map 来跑。看看结果怎样？(在其他oj创建的题目，速度应该也差不多）
测试数据下载：input_file

没错，你没有看错，足足跑了4s！

不被hack？

自己写一个hash函数！

当然我相信多数时候是不会有人刁难hack你unordered_map的。。除非是cf比赛。。。（ccf造这种数据那我也没啥办法了）

具体自己写hash函数可以自己参考我发的资料。在此不再累赘。

总结

unordered_map/set 确实是个好东西！

如果noip中发现复杂度没错，

尽量使用map

毕竟ccf啥都能卡（已经死了个shortest path fake algorithm）

下场cf别忘了去hack别人哦

关于卡掉hash 参考了 cf 的文章： neal's blog（已经获得博主关于转载的许可）

noip考场上自然还有很多这样的可以拿来骗分用的STL容器。关于可持久平衡树也可以参考我的一篇题解可持久平衡树四十行实现（板子题MLE）

当然，pbds党肯定认为hash这种东西直接调啊QWQ那我也没办法了。。

广告：

yijan's blog: yihan.ac.cn 欢迎互换友链