c++ - 恒定大小的字符串的有效哈希图

我需要将大小恒定的字符串(仅包含字母数字值(A-Z，0-9，不包含小写字母))映射到其他字符串。 unordered_map变得非常大(数千万个键)，而映射的值来自数千个字符串。分析后，我发现大部分时间都花在了将新值插入映射中(operator [])，并且清除映射也花费了很长时间。

std::unordered_map<std::string, std::string> hashMap;
while (...){
    ...
    hashMap[key] = value;  // ~50% of program time is spent here
    ...
}

hashMap.clear();  // Takes a very long time, at this point hashMap.size() > 20,000,000

我的想法是，字符串分配/取消分配非常缓慢，而且会散列和插入到映射中。
有什么优化建议吗？请记住， key 大小是恒定的，并且其内容限制为一组36个字符，并且映射值来自一组有限的字符。我愿意使用除字符串和unordered_map之外的其他容器/数据类型。

更新

遵循Baum Mit Augen的建议，我将 key 类型更改为unsigned long long，并创建了一个将基数36转换为十进制的函数:

unsigned long long ConvertBase36(const char* num)
{
    unsigned long long retVal = 0;

    for (int i = 0; i < 12; i++)
    {
        unsigned int digit = 0;
        char currChar = num[i];
        if (currChar <= '9')
        {
            digit = currChar - '0';
        }
        else
        {
            digit = currChar - 'A' + 10;
        }

        retVal *= 36;
        retVal += digit;
    }

    return retVal;
}

这使我整个程序运行时的性能提高了约10％。
然后，我再次尝试使用unordered_map保留函数，以查看它是否有所不同，是否没有影响。
尝试使用map而不是unordered_map的情况要差大约10％，所以我恢复了这一更改。
最后，将字符串值替换为unsigned int会使事情变得更快。

最佳答案

两个不相关的建议，但都与 std::unordered_map::reserve 有关。

首先，由于您的无序映射包含10M的元素，因此在插入时可能会进行许多重新分配/重新混合。开始时，您可能想保留10M的条目。

自从



您应该能够将值本身存储在第二个unordered_set中，首先将reserve d存储到足够大的值，以确保没有迭代器在insert s上无效-请参见invalidation guarantees for unordered associative containers。

然后，您的(主要)unordered_map可以将string映射到std::unordered_set::const_iterator。