C++11 Unordered_map & set 你真的了解了吗？

前段时间[博客](http://yihan.ac.cn)迁移图片炸了已补图 ---- 以下为原文 # 这是啥？ 我们知道，在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环境下，可以很方便写出来： ```cpp #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 的！怎么办？ 那自然是有奇技淫巧的！：（~~据说是没有~~问题的） ```cpp #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](https://github.com/gcc-mirror/gcc/blob/5bea0e90e58d971cf3e67f784a116d81a20b927a/libstdc%2B%2B-v3/include/bits/unordered_map.h) 我们得知道这个东西的实现原理，里面我们可以看到这一句话，这个hashtable 显然调用了 ```_Mod_range_Hashing``` 和 ```_Prime_rehash_policy```从这里我们就可以大概知道这个东西的实现过程：首先hash这个数据，然后对这个hash值取模放入unordered_map。 对```_Prime_rehash_policy```的探索（[hashtable_c++0x.cc](https://github.com/gcc-mirror/gcc/blob/5bea0e90e58d971cf3e67f784a116d81a20b927a/libstdc%2B%2B-v3/src/c%2B%2B11/hashtable_c%2B%2B0x.cc)）我们可以发现一个数组：```__prime_list```。并且此时你又可以摸清其中的一部分实现：当这个map过大的时候，它就会resize其本身。当抛开这个我们先把这个质数表找到。 然后呢 打开了（[ hashtable-aux.cc](https://github.com/gcc-mirror/gcc/blob/5bea0e90e58d971cf3e67f784a116d81a20b927a/libstdc%2B%2B-v3/src/shared/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数对](https://www.luogu.org/problemnew/show/P1102)这是一个普通map都能ac的水题。我们来对比一下unordered_set & unordered_map 这是份AC代码： 然后下图中，上面的是采用map，下面的采用unordered_map  可以看到，无论空间和时间都是unordered后优秀。 #### Hack It！ 我们用前面说过的那个卡掉代码的质数来做输入文件。输入的数字为126271的1～200000倍。然后分别使用map和unordered_map 来跑。看看结果怎样？(在其他oj创建的题目，速度应该也差不多） 测试数据下载：[input_file](https://codgi.cc:2/problem/1637/testdata/download)   没错，你没有看错，足足跑了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](http://codeforces.com/blog/entry/62393)（已经获得博主关于转载的许可） noip考场上自然还有很多这样的可以拿来~~骗分~~用的STL容器。关于可持久平衡树也可以参考我的一篇题解[可持久平衡树四十行实现（板子题MLE）](https://www.luogu.org/blog/yihan/solution-p3835) 当然，pbds党肯定认为hash这种东西直接调啊QWQ那我也没办法了。。 ## 广告： yijan's blog: yihan.ac.cn 欢迎互换友链