...如何优雅的使用C++ STL中unordered_map(哈希表)
发布网友
共1个回答
热心网友
起因是一道水题：Problem - C - Codeforces
题意大致为从一个数量级为2e5 的数组中查找和等于特定值的下标对数，有点类似于Leetcode第一题。
例如在[1, 2, 3, 4, 5, 6, 7] 中寻找和为8的下标对数，显然有3对 [1, 7],[2, 6],[3, 5]。
一种思路是从前往后扫描一遍，用散列表计数，时间复杂度为O(n) 。
当然也可以将数组排序，扫描数组时使用二分查找(lower_bound upper_bound)计算每个数的个数，总时间复杂度为O(nlogn) ，两种算法的复杂度都能满足题目里的要求，但是神奇的是散列表写法会TLE，而二分查找方法却可以顺利AC。
两种方法的核心代码如下
根据C++标准对unordered_map的两个常用操作count和[]复杂度的解释 .
std::unordered_map::count
Average case: linear in the number of elements counted. Worst case: linear in container size.
std::unordered_map::operator[]
Average case: constant. Worst case: linear in container size. May trigger a rehash if an element is inserted (not included in the complexity above).
在一般情况下，散列表查找的时间复杂度均摊为O(1) ，但是极端情况下会因为哈希碰撞退化到O(n)。很显然是unordered_map被出题人卡掉了。
这是因为unordered_map默认的哈希函数是std::hash是固定的，出题人可以通过哈希函数出一些会导致大量哈希碰撞的数据，从而卡掉散列表的做法。
但是如果输入的数量级在大一些，例如来到1e7级别的 数据，这时O(nlogn)的做法会TLE。 此时我们就必须使用散列表。
为了防止散列表被特殊数据卡掉，这时候就需要自定义哈希函数。
这里给出来自codeforces博客上的一种自定义哈希函数的方法。
代码如下
其主要思路是通过给与哈希函数随机性，以防止被特别设计的数据制造出大量的哈希碰撞。自定义哈希函数后，就可以愉快的AC掉这道题啦。
结论
在数据量能够满足O(nlogn)要求的情况下，尽量使用二分查找的方法，因为二分查找的算法复杂度比较稳定,二分查找本身常数也比较小。如果数据量较大的情况下必须使用散列表，为了防止卡unordered_map，最好自定义哈希函数。
补充：unordered_map复杂度退化的具体原因
unordered_map复杂度的退化是因为哈希碰撞。经查阅资料，unordered_map 是使用拉链法实现的，每个哈希值对应的数都用链表存储，因此大量的如果散列表中存在大量相同的键时，查找的复杂度就会退化成链表的查找复杂度为O(n) 。
在Java中拉链的size 大于8后，会改为使用红黑树map存储，这样最坏的时间复杂度也只会退化到O(logn)。但是C++标准中没有关于这样的规定，大部分编译器对于unordered_map的实现没有包括这一部分。
