c++ - std::unordered_map::rehash() 函数可以减少哈希冲突吗？

Question

我遇到了一个算法问题，在 C++ 中使用 unordered_map 发生超时。

其他语言的哈希映射很好地解决了这个问题。

所以我尝试通过使用 rehash 函数来提高 unordered_map 的性能。我希望通过问题但失败了。

据我了解，rehash 函数会产生更多的桶，从而减少哈希冲突。

所以我的问题是 rehash 函数实际上可以减少碰撞。如果是这样，我可以得出结论，超时的根本原因在于该问题。

编辑============
问题是

[问题]
SUM 问题可以表述如下：给定四个整数值列表 A、B、C、D，计算有多少四元组 (a, b, c, d ) ∈ A x B x C x D 是这样的a + b + c + d = 0 。在下文中，我们假设所有列表具有相同的大小 n。

[输入格式] 输入
的第一行包含列表 n 的大小（这个值可以大到 4000）。然后我们有 n 行包含四个整数值（绝对值高达 228），它们分别属于 A、B、C 和 D。

和我的代码...

using namespace std;


#define SIZE 4000

int A[SIZE];
int B[SIZE];
int C[SIZE];
int D[SIZE];

int main(void){
    int N;
    scanf("%d", &N);

    for(int i=0; i <N;i++){
        scanf("%d %d %d %d", &A[i], &B[i], &C[i], &D[i]);
    }

    unordered_map<int, int> LeftMap; // store all result of A[i] + B[i]
    //LeftMap.rehash(1000000);
    unordered_map<int, int> RightMap; // store all result of C[i] + D[i]
    unordered_map<int, int>::iterator iter;
    unordered_map<int, int>::iterator iter2;

    int k;
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            k = A[i]+B[j];

            iter = LeftMap.find(k);
            if(iter == LeftMap.end())
                LeftMap.insert({k, 1});
            else
                iter->second++;

            k = C[i]+D[j];

            iter = RightMap.find(k);
            if(iter == RightMap.end())
                RightMap.insert({k, 1});
            else
                iter->second++;
        }
    }

    int sum =0;
    for(iter = RightMap.begin(); iter != RightMap.end(); ++iter){
        iter2 = LeftMap.find((iter->first)* -1);
        if(iter2 != LeftMap.end()){
            sum+= iter->second * iter2->second;
        }
    }

    printf("%d", sum);


    return 0;
}

标签： c++hashunordered-map