由一道CF题浅谈unordered_map

unordered_map是c++11引入的引入的新型容器。存储时是根据key的hash值判断元素是否相同,即unordered_map内部元素是无序的,而map中的元素是按照二叉搜索树存储,进行中序遍历会得到有序遍历。

unordered_map的优势在于其内部的hash使得值查找速度非常快,所以我们在做一些如果有大量访问map而且可能卡常数的题目的时候,可以考虑一下unordered_map(因为例如count、find元素的操作复杂度从O(log(n))减少到了O(1) )。今天我们要谈一下这种情况可能的问题.

看一下这道CF题,题目本身很简单。我们很容易地发现就是寻找3个数A, B, C使得 C-B = B-A 并且差是一个2次幂。没有的就找两个数的差是二次幂的。否则就是一个数。

所以我们只需要按照某种方式存储好每个数,然后查询它+2^x和它加上2^(x+1)是否存在就ok了。问题就是我们按照什么存呢,由于之前吃过亏,所以这次我索性就直接unordered_map。但是我发现却FST(failed system test)了,既然是TLE那么我发现改成map竟然不超时。

很懵圈了有没有

直到我在首页的帖子中发现了这个:

You need to understand that unordered_set works based on hashes and therefore, if somebody knows the hashing algorithm used, they can handcraft a test case for which the hashes will have many collisions.

One popular technique to avoid this is to add a random seed to your hash function. That way, the hash function is different every time and it is very difficult to generate a bad test.

大意就是如果有人知道了这个unordered_map的hash算法,那么我们就可以通过手动做数据来hack掉这种做法。天哪很恶意有没有,不过鉴于CodeForces的Hack属性,这个也无可厚非。所以该怎么破呢?他也指明了方法,就是对于我们的hash算法增加异或一个大数的机制并加上随机种子。此时想hack就有如登天了。我加上下面的代码试了后,果然不TLE了。

用unorder_map的时间在630ms左右,而map则在1900ms左右。此外,如果要用set记得是用v.find(x)而不是find(v.begin(), v.end(), x)因为前者是log后者是O(n)。而如果是vector的find的话只有find(v.begin(), v.end(), x)这种写法且始终是O(n)。如果再vector里查找可以用upper_bound,它是log的。

最后再叨叨一句,不要再犯想要在unordered_map中查询直接写if (mp[x] > 0) 这种写法了,明明就是一个查找操作偏偏要多一个附加建立节点mp[x]=0的操作。

总结,对于大量查找元素的map,我们在C++中可以考虑使用unordered_map,它其中的元素没有按照其 Key 值与映射值的任何顺序进行排序 ,而是根据它们的 Hash 值组织成桶,允许它们通过其 Key 值直接快速访问单个元素(通常具有常数等级的平均时间复杂度)。unordered_map 容器与 map 容器相比,通过 Key 值访问各个元素的速度更快,然而通过其元素子集进行范围迭代的效率通常较低。以及为了防止codeforces的恶意hack操作,我们可能需要将每个值异或一个随机化的大数塞进map里。

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注